文章目录
插入排序
直接插入排序
概念
将一个数据插入到一个有序数列中的合适位置，使新的序列仍然有序。
插入排序方法
我们可将数组中的第一个元素看成一个有序数列，然后将后面的数据依次插入，直至整个数列有序。
图解：
代码：
void InsertSort(int arr[],int l) { for (int i = 0; i < l - 1; i++) { int end = i; int tmp = arr[end + 1]; while (end >= 0) { if (tmp < arr[end]) { arr[end + 1] = arr[end]; end--; } else { break; } } arr[end + 1] = tmp; } }
时间复杂度：O(n^2)
希尔排序
概念
希尔排序属于插入类排序,是将整个有序序列分割成若干小的子序列分别进行插入排序。
思想
希尔排序，又称缩小增量法。其基本思想是：
1.先选定一个小于N的整数gap作为第一增量，然后将所有距离为gap的元素分在同一组，并对每一组的元素进行直接插入排序。然后再取一个比第一增量小的整数作为第二增量，重复上述操作…
2.当增量的大小减到1时，就相当于整个序列被分到一组，进行一次直接插入排序，排序完成。
图解
代码
//希尔排序 void ShellSort(int arr[],int l) { int gap = l; while (gap > 1) { gap = gap / 2; for (int i = 0; i < l - gap; i++) { int end = i; int tmp = arr[end + gap]; while (end >= 0) { if (tmp < arr[end]) { arr[end + gap] = arr[end]; end -= gap; } else { break; } } arr[end + gap] = tmp; } } }
选择排序
直接选择排序
概念
通过循环遍历，选出数组中最小的数放在数列开头(选出最大的数放在数列末尾)，重复这个步骤直至数列有序。
图解
代码：
void SelectSort(int arr[],int L) { int begin = 0; while (begin<L-1) { int mini = begin; for (int i = begin; i < L ; i++) { if (arr[mini] > arr[i]) { mini = i; } } Swap(&arr[mini],&arr[begin]); begin++; } }
代码优化
我们在一次循环中同时选出一个最大的和一个最小的，将最小的放最前面，将最大的放最后面，这样代码的效率会将近提高一倍。
void SelectSort(int arr[],int L) { int begin = 0; int end = L - 1; while (begin < end) { int maxi = begin; int mini = begin; for (int i = begin; i <= end; i++) { if (arr[i] > arr[maxi]) { maxi = i; } if (arr[i] < arr[mini]) { mini = i; } } int max = arr[maxi]; int min = arr[mini]; Swap(&arr[maxi], &arr[end]); if (mini == end) { mini = maxi; } Swap(&arr[mini], &arr[begin]); end--; begin++; } }
时间复杂度：O(n^2)
堆排序
概念
堆排序是利用堆这种数据结构而设计的一种排序算法，堆排序是一种选择排序。
堆的两个特性
结构性:堆是用数组表示的完全二叉树,我们可以用数组下标来表示父子结点的关系。
这里随便给出一个数组：
将数组以完全二叉树的形式表示出来：
我们可以推出父子结点与二叉树的关系:
LeftChild = Parent* 2 - 1
RightChild = Parent* 2 - 2
Parent = (Chird - 1) / 2
有序性:
- 任意一个结点的值都大于或者等于左右子树的结点的值(或者左右结点不存在)，称为 “最大堆(MaxHeap)”
,也称大顶堆。
- 任意一个结点的值都小于或等于左右子树的结点的值((或者左右结点不存在))，称为 “最小堆(MinHeap)”
,也称小顶堆。
堆排序中的三个操作 - 向下调整算法
- 建立最小(最大)堆
- 堆排序
向下调整算法
当一个结点的左右子树都是小堆(大堆)时，可以使用向下调整算法。
上图中，初始时，27的左右子树都是最小堆，我们就可以使用向下调整算法，将27放在合适的位置，首先选出左右子树中较小的那一个，和27比较，如果比27小就进行交换，然后继续往下调，如果比27大，说明已经找到了27合适的位置，不需要继续往下调。
如果是最小堆，经过向下调整算法，根结点会是堆中最小的值；
如果是最大堆，经过向下调整算法，根节点会是堆中最大的值。
代码：
//最小堆的向下调整算法 void Adjustdown(int arr[],int L,int root) { int parent = root; int child = parent * 2 + 1;//先默认child是左孩子 while (child < L) { //选左右孩子中较小的一个 //若child >= L-1说明右孩子不存在 if (child < L-1 && arr[child + 1] > arr[child]) { child += 1; } if (arr[parent] < arr[child]) { Swap(&arr[parent], &arr[child]); parent = child; child = parent * 2 + 1; } else { break; } } }
建立最小(最大)堆
有了向下调整算法，我们就可以将一个无序数组变成最小(最大)堆。向下调整算法使用条件是左右子树必须是最小(最大)堆，一个无序数组构成的满二叉树如果从根节点出发的肯定不满足，但是满二叉树的叶子结点的父节点一定满足(即从叶子结点出发)。
最后一个叶子结点下标就是数组的最后一个元素L - 1，它的父节点就是 [(L - 1) -1] / 2 , 然后依次向上建堆。
图解：
a.假定给定无序序列如下：
b.由最后一个叶子结点的父节点开始，自下而上，自左而右的进行向下调整算法。
此时，我们成功的建立了一个最大堆
代码：
void HeapGreat(int arr[], int L) { for (int i = (L - 2) / 2; i >= 0; i--) { Adjustdown(arr, L, i); } }
若数组为 arr[ ] = { 9 , 8 , 7 , 6 , 5 , 4 , 3 , 2 , 1}
建堆之后的结果为：
堆排序
我们可以通过建最大堆找到数组中最大的元素，通过建最小堆找到数组中最小的元素。
如果要将无序数组排成升序的化，我们需要建最大堆，因为建最大堆可以找到最大的元素，我们可以将找到的最大元素与数组末尾的元素交换位置，然后不在将这个数看入堆中。重复以上操作，直至堆中只剩一个元素，这时数组已经有序。
代码：
void HeapSort(int arr[],int L) { //建堆 for (int i = (L - 2) / 2; i >= 0; i--) { Adjustdown(arr, L, i); } int newL = L; // while (newL > 0) { Swap(&arr[0], &arr[newL-1]); newL--; Adjustdown(arr, newL, 0); } }
时间复杂度
建堆复杂度：O(N)
排序复杂度：O(logN)
总复杂度：O(logN)
交换排序
冒泡排序
动图演示
代码
void BubbleSort(int arr[],int L) { int Flag = 1; for (int i = 0; i < L&&Flag; i++) { Flag = 0; for (int j = 1; j < L - i; j++) { if (arr[j] < arr[j - 1]) { Swap(&arr[j], &arr[j - 1]); Flag = 1; } } } }
注意：程序中标记变量Flag的作用，如果某趟所有相邻的数都不需要交换，则Flag置为0，表示所有的数都已全部有序，后面不需要进行，冒泡排序可以提起结束。
快速排序
基本思想
任取待排序元素序列中的某元素作为基准值，按照该基准值将待排序列分为两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后左右序列重复该过程，直到所有元素都排列在相应位置上为止。
挖坑法
挖坑法的单趟排序的基本步骤如下：
1、选出一个数据（一般是最左边或是最右边的）存放在key变量中，在该数据位置形成一个坑。
2、还是定义一个L和一个R，L从左向右走，R从右向左走。（若在最左边挖坑，则需要R先走；若在最右边挖坑，则需要L先走）。
3、在走的过程中，若R遇到小于key的数，则将该数抛入坑位，并在此处形成一个坑位，这时L再向后走，若遇到大于key的数，则将其抛入坑位，又形成一个坑位，如此循环下去，直到最终L和R相遇，这时将key抛入坑位即可。（选取最左边的作为坑位）
经过一次单趟排序，最终也使得key左边的数据全部都小于key，key右边的数据全部都大于key。
然后也是将key的左序列和右序列再次进行这种单趟排序，如此反复操作下去，直到左右序列只有一个数据，或是左右序列不存在时，便停止操作。
动态演示
代码
void QuickSort(int arr[],int L,int R ) { if (L >= R) { return; } int begin = L; int end = R; int Pivot = begin; int key = arr[Pivot]; while(begin < end) { //右边找小 //这里的 = 不能去掉，不然如果arr[end] = arr[begin]就不会进入内循环但也出不了外面循环 while(end > begin && arr[end] >= key) { end--; } //将小的放到左边的坑里，自己形成新的坑 arr[Pivot] = arr[end]; Pivot = end; //左边找大 while (end > begin && arr[begin] <= key) { begin++; } //将大的放到右边的坑里，自己形成新的坑 arr[Pivot] = arr[begin]; Pivot = begin; } //begin与end相遇，将key放到坑里 arr[Pivot] = key; QuickSort(arr,0,Pivot-1); QuickSort(arr,Pivot+1,R); }
左右指针法
思路如下：
1.选择一个值作为基准值key(一般选最左边或最右边，在这里选最左边)。
2.定义L，R（分别为待排序序列最左边与最右边元素的下标)，L从左往右走，R从右往左走(若选最左边为key，R先走；选最右边为key，L先走)。
3.R从右往左走遇到比key小的停下来，接着L从左往右走，遇到比key大的停下来。然后交换R，L对应数组中的值。
4.重复上一步操作，直至L，R二者相遇。将相遇点对应的值与key对应的值交换，此时相遇点左边的值均小于相遇点所对应的值，右边的值均大于相遇点所对应的值。
5.相遇点将待排序序列分为两个子序列，用递归的方式重复上述操作。
6.当左右序列只有一个元素的时候排序完成。
动态演示
代码
void QuickSort(int arr[],int L,int R) { if (L >= R) return; int begin = L; int end = R; int key = L; while (end > begin) { while (end > begin && arr[end] >= arr[key]) { end--; } while (end > begin && arr[begin] <= arr[key]) { begin++; } Swap(&arr[begin], &arr[end]); } Swap(&arr[key], &arr[begin]); QuickSort(arr,L,begin-1); QuickSort(arr,begin+1,R); }
前后指针法
动态演示
代码
void QuickSort(int arr[],int L,int R) { if (L >= R) return; int key = L; int cur = L+1; int prev = L; while (cur <= R) { if (arr[cur] < arr[key]) { prev++; Swap(&arr[cur],&arr[prev]); } cur++; } Swap(&arr[key], &arr[prev]); QuickSort(arr,L,prev-1); QuickSort(arr,prev+1,R); }
非递归法
上面的三种方法都是使用递归的方式实现的快速排序，但是递归也有着明显的缺陷，栈帧深度太深，栈空间不够用，可能会溢出。
我们可以使用一种叫栈的数据结构，来模拟递归。
思路：
- 将待排序序列的第一个数和最后一个数的下标入栈。
- 获取栈中的第一个元素®然后让它出栈，再获取栈中一个元素(L)然后让它出栈，进行一次单趟排序，然后判断左右两个子序列是否需要排序，若需要再将该序列的第一个数下标和最后一个数的下标入栈。
- 重复以上操作，直至栈为空。
代码
void QuickSort(int arr[],int L) { //如果序列长度小于2，不需要进行排序 if(L<2) return; Stack ps;//定义了一个栈 StackInit(&ps);//初始化栈 StackPush(&ps,0);//数组中第一个数的下标入栈 StackPush(&ps,L-1);//数组中最后一个数的下标入栈 //当栈不为空时进行循环 while (!StackEmpty(&ps)) { //获得栈顶元素 int end = StackTop(&ps); //弹栈 StackPop(&ps); int Right = end; //获得栈顶元素 int begin = StackTop(&ps); //弹栈 StackPop(&ps); int Left = begin; int key = begin; //快排的单趟排序 while (begin < end) { while (begin < end && arr[end] >= arr[key]) { end--; } while (begin < end && arr[begin] <= arr[key]) { begin++; } Swap(&arr[end], &arr[begin]); } Swap(&arr[key], &arr[begin]); //如果左序列元素个数大于1，左序列首尾下标入栈 if ( Left< begin-1) { StackPush(&ps, Left); StackPush(&ps, begin-1); } //如果左序列元素个数大于1，左序列首尾下标入栈 if (begin+1 < Right) { StackPush(&ps, begin+1); StackPush(&ps, Right); } } StackDestory(&ps); }
优点
递归的方法它会占用一个名为栈的空间，一般计算机中栈的空间很小，当递归次数过多时，就有可能栈溢出。如果我们自己模拟实现栈，在循环中占用的是堆空间，堆要比栈大很多。
快排优化
快排最理想的情况下，每次选key都能选到大小排在数列中间的数，这样快排的时间复杂度就是 O(NlogN) 。最坏的情况就是每次选key都是序列中最大的，或者是最小的，这样时间复杂度就上升到O(N^2)，为了避免这种最坏的情况，尽量接近最好的情况，我们在key时可以采用三数取中的方式。
三数取中
//三数取中 int GetMidIndex(int arr[],int L,int R) { int Mid = (L + R) >> 1; if (arr[L] > arr[R]) { if (arr[Mid] > arr[L]) return L; else if (arr[Mid] < arr[R]) return R; else return Mid; } else { if (arr[Mid] > arr[R]) return R; else if (arr[Mid] < arr[L]) return L; else return Mid; } }
优化代码
void QuickSort(int arr[],int L,int R ) { if (L >= R) { return; } Swap(&arr[L],&arr[GetMidIndex(arr,L,R)]); int begin = L; int end = R; int Pivot = begin; int key = arr[Pivot]; while(begin < end) { //右边找小 while(end > begin && arr[end] > key) { end--; } //将小的放到左边的坑里，自己形成新的坑 arr[Pivot] = arr[end]; Pivot = end; //左边找大 while (end > begin && arr[begin] < key) { begin++; } //将大的放到右边的坑里，自己形成新的坑 arr[Pivot] = arr[begin]; Pivot = begin; } //begin与end相遇，将key放到坑里 arr[Pivot] = key; QuickSort(arr,0,Pivot-1); QuickSort(arr,Pivot+1,R); }
小区间优化
快速排序在排数量较大的序列时效率很高，但是随着递归的深入，递归次数也呈2
的倍数增长。
比如说通过快速排序排列100w(约等于2^20)个数时，要经过 200w（2^20 + 2^19 + …… + 2^0)次递归，快排的最后一层要进行100w次递归，倒数第二层要进行50w次递归，倒数第三层要进行25w次递归，倒数第四层要进行12.5w次递归，刚最后四组递归加起来已经187.5w次，占了总递归次数的绝大多数。为了减少递归次数，我们可以进行小区间优化，当进入快排这个函数的序列长度小于10时，我们就可以采用其他的排序方式，短序列排序我们可以使用直接插入排序。
优化代码
void QuickSort(int arr[],int L,int R ) { if (L >= R) { return; } Swap(&arr[L],&arr[GetMidIndex(arr,L,R)]); int begin = L; int end = R; int Pivot = begin; int key = arr[Pivot]; while(begin < end) { //右边找小 while(end > begin && arr[end] > key) { end--; } //将小的放到左边的坑里，自己形成新的坑 arr[Pivot] = arr[end]; Pivot = end; //左边找大 while (end > begin && arr[begin] < key) { begin++; } //将大的放到右边的坑里，自己形成新的坑 arr[Pivot] = arr[begin]; Pivot = begin; } //begin与end相遇，将key放到坑里 arr[Pivot] = key; if (Pivot - L <= 10) { InsertSort(arr + L, Pivot - L); } else { QuickSort(arr, L, Pivot - 1); } if (R - Pivot <= 10) { InsertSort(arr+Pivot+1,R-Pivot); } else { QuickSort(arr, Pivot + 1, R); } }
归并排序
归并排序是建立在归并操作上的一种有效，稳定的排序算法，该算法是采用分治（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；
归并排序可以大致分为两个步骤：分解序列至子序列有序，合并子序列得到新的有序数列。如下图：
动态演示
代码
void _MergeSort(int arr[],int Left,int Right ,int tmp[]) { if (Left >= Right) { return; } int Mid = (Left + Right) / 2; _MergeSort(arr, Left, Mid, tmp); _MergeSort(arr, Mid + 1, Right, tmp); int begin1 = Left; int end1 = Mid; int begin2 = Mid+1; int end2 = Right; int cur = Left; while (begin1 <= end1&&begin2 <= end2) { if (arr[begin1] > arr[begin2]) { tmp[cur++] = arr[begin2++]; } else { tmp[cur++] = arr[begin1++]; } } while (begin1 <= end1) { tmp[cur++] = arr[begin1++]; } while (begin2 <= end2) { tmp[cur++] = arr[begin2++]; } for (int i = Left; i <= Right; i++) { arr[i] = tmp[i]; } } void MergeSort(int arr[],int L) { int* tmp = (int*)malloc(sizeof(int) * L); _MergeSort(arr,0,L-1,tmp); free(tmp); }
时间复杂度：O( NlogN ) 空间复杂度：O(N)
