常见算法的实现
插入排序
动画演示：
思路(升序)：
从最开始前，我们取第一位数和第二位数，进行比较，如果第一位数大于，第二位数，
则将第一位数和第二位数进行交换，如果小于，则直接跳出去，此时则完成一次交换，end不断向
前挪动，不断进行比较，随着i的变化，比较的位置也发生变化
代码：
void InsertSort(int* a,int n) { for (int i=1; i < n; i++) { int end = i-1; int temp = a[i]; while (end >= 0) { if (a[end] > temp) { a[end + 1] = a[end]; --end; } else { break; } } a[end + 1] = temp; } }
直接插入排序的特性总结：
1. 元素集合越接近有序，直接插入排序算法的时间效率越高
2. 时间复杂度：O(N^2)
3. 空间复杂度：O(1)，它是一种稳定的排序算法
4. 稳定性：稳定
希尔排序
图片演示：
思路(升序)
我们对数组每隔gap个数字进行比较一次，当前数字与gap位后的数字进行比较
如果当前数字大于gap数之后的数，则将其进行调换，如果没有，则跳出循环，当外层循环进行
++操作时，则从第二个数字开始，与从第二个数字开始数gap位之后的数字，进行比较，大于交
换，小于跳出循环，同时gap也在不断发生变化，最后gap==1时，进行最后的比较
代码：
void ShellSort(int* a, int n) { int gap = n; while (gap>1) { gap =gap/ 2; for (int i = 0; i< n-gap;i++) { int end = i; int temp = a[end + gap]; while (end >= 0) { if (a[end] > temp) { a[end + gap] = a[end]; end -= gap; } else { break; } } a[end + gap] = temp; } } }
希尔排序的特性总结：
1. 希尔排序是对直接插入排序的优化。
2. 当gap > 1时都是预排序，目的是让数组更接近于有序。当gap == 1时，数组已经接近有序的了，这样就会很快。这样整体而言，可以达到优化的效果。我们实现后可以进行性能测试的对比。
3. 希尔排序的时间复杂度不好计算，因为gap的取值方法很多，导致很难去计算，因此在好些树中给出的希尔排序的时间复杂度都不固定
堆排序
堆排序(Heapsort)是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。它是通过堆来进行选择数据。需要注意的是排升序要建大堆，排降序建小堆。
思路：
首先应该建一个大堆，不能直接使用堆来实现。可以将需要排序的数组看作是一个堆，但需要将数组结构变成堆我们可以从堆从下往上的第二行最右边开始依次向下调整直到调整到堆顶，这样就可以将数组调整成一个堆，且如果建立的是大堆，堆顶元素为最大值。然后按照堆删的思想将堆顶和堆底的数据交换，但不同的是这里不删除最后一个元素。这样最大元素就在最后一个位置，然后从堆顶向下调整到倒数第二个元素，这样次大的元素就在堆顶，重复上述步骤直到只剩堆顶时停止。
图片演示：
// 堆排序 void AdjustDown(int* a, int n, int root)//向下调整 { assert(a); int parent = root; int child = parent * 2 + 1; while (child < n) { if (child + 1 < n && a[child + 1] > a[child]) { child++; } if (a[child] > a[parent]) { Swap(&a[child], &a[parent]); parent = child; child = parent * 2 + 1; } else { break; } } } void HeapSort(int* a, int n) { assert(a); //建堆 for (int i = (n - 1 - 1) / 2; i >= 0; i--) { AdjustDown(a, n, i); } //交换 for (int i = n - 1; i > 0; i--) { Swap(&a[i], &a[0]); AdjustDown(a, i, 0); } }
选择排序
思路(升序)：
第一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始(末尾)位置，然后选出次小(或次大)的一个元素，存放在最大(最小)元素的下一个位置，重复这样的步骤直到全部待排序的数据元素排完 。
代码：
void SelectSort(int* arr, int n) { //保存参与单趟排序的第一个数和最后一个数的下标 int begin = 0, end = n - 1; while (begin < end) { //保存最大值的下标 int maxi = begin; //保存最小值的下标 int mini = begin; //找出最大值和最小值的下标 for (int i = begin; i <= end; ++i) { if (arr[i] < arr[mini]) { mini = i; } if (arr[i] > arr[maxi]) { maxi = i; } } //最小值放在序列开头 Swap(&arr[mini], &arr[begin]); //防止最大的数在begin位置被换走 if (begin == maxi) { maxi = mini; } //最大值放在序列结尾 Swap(&arr[maxi], &arr[end]); ++begin; --end; } }
接选择排序的特性总结：
1. 直接选择排序思考非常好理解，但是效率不是很好。实际中很少使用
2. 时间复杂度：O(N^2)
3. 空间复杂度：O(1)
4. 稳定性：不稳定
冒泡排序
算法思想:
从左到右依次进行比较，升序时：如果左边大于右边则交换，从到到尾，全部进行交
换，挑选出最大的元素，放到最后，这是一次单趟排序，再进行循环选出第二大的，再循环选出第
三大的
代码实现：
//交换 void Swap(int* a,int* b) { int tmp = *a; *a = *b; *b = tmp; } //冒泡实现 void BubbleSort(int* a,int n) { for (int j =0; j<n; j++) { for (int i = 1; i < n-j; i++) { if (a[i - 1] > a[i]) { Swap(&a[i - 1], &a[i]); } } } }
冒泡排序的特性总结：
1. 冒泡排序是一种非常容易理解的排序
2. 时间复杂度：O(N^2)
3. 空间复杂度：O(1)
4. 稳定性：稳定
快速排序
1962年由Hoare提出的一种二叉树结构的交换排序的方法，其基本思想:任取待排序
元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中
所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过
程，直到所有元素都排列在相应位置上为止。
选出一个关键值key，把他放到正确的位置,我们在学习任何排序前，都应该先弄明白单
趟排序，然后再清楚整体思想即可
Hoare版本
左边做Key右边先走，如果右边做Key左边先走，将小的往左边换，把大的往右边
换，到相遇位置，停下，此时左边全是比中间位置小的，右边全是比中间位置大的，相遇位
一定比Key小
Hoare一次排序其实本质是在排一个数据
void QuickSort(int* a,int left ,int right) { if (left >= right) { return; } int begin = left, end = right; int keyi = left; while (left < right) { //右边先走找小 while (a[right] >= a[keyi] && left < right) { --right; } //左边找大 while (a[left] <= a[keyi] && left < right) { ++left; } Swap(&a[left],&a[right]); } Swap(&a[keyi],&a[left]); QuickSort(a,begin,keyi-1); QuickSort(a,keyi+1,end); }
注：但其有个致命特点，如果keyi在最左边时，而数组为有序，这样排序时，需要不断
创建新的栈帧，其时间复杂度，直接为n*logn，我们可以将Keyi的位置进行随机排放
随机选Keyi
我们将keyi进行随机处理，就可以解决上面的问题
void QuickSort(int* a, int left, int right) { // ... 返回条件 if (left >= right) { return; } int begin = left, end = right; int randi = left + (rand() % (right - left)); Swap(&a[left],&a[randi]); int keyi = left; while (left < right) { // 右边找小 while (left < right && a[right] >= a[keyi]) --right; // 左边找大 while (left < right && a[left] <= a[keyi]) ++left; Swap(&a[left], &a[right]); } Swap(&a[keyi], &a[left]); keyi = left; // [begin, keyi-1] keyi [keyi+1, end] // 递归 QuickSort(a,begin,keyi-1); QuickSort(a,keyi+1,end); }
三数取中
有序情况下，三数取中对时间复杂度的优化，其极其明显
void QuickSort(int* a, int left, int right) { // ... 返回条件 if (left >= right) { return; } int begin = left, end = right; int midi = GetMidNumi(a,left,right); Swap(&a[midi],&a[left]); /*int randi = left + (rand() % (right - left)); Swap(&a[left],&a[randi]);*/ int keyi = left; while (left < right) { // 右边找小 while (left < right && a[right] >= a[keyi]) --right; // 左边找大 while (left < right && a[left] <= a[keyi]) ++left; Swap(&a[left], &a[right]); } Swap(&a[keyi], &a[left]); keyi = left; // [begin, keyi-1] keyi [keyi+1, end] // 递归 QuickSort(a,begin,keyi-1); QuickSort(a,keyi+1,end); }
挖坑法
int QuickSort(int* a, int left, int right) { // ... 返回条件 if (left >= right) { return; } int begin = left, end = right; int midi = GetMidNumi(a,left,right); if(midi != left) Swap(&a[midi],&a[left]); int key = a[left]; int hole = key; while (left < right) { // 右边找小 while (left < right && a[right] >= key) --right; a[hole] = a[right]; hole = right; // 左边找大 while (left < right && a[left] <= key) ++left; a[hole] = a[left]; hole = left; } a[hole] = key; // [begin, keyi-1] keyi [keyi+1, end] // 递归 } void QuickSort1(int* a, int left, int right) { if (left >= right) { return; } int keyi = QuickSort(a,left,right); QuickSort1(a,left,keyi-1); QuickSort1(a,keyi+1,right); }
前后指针版本
1.cur找到比key小的值，++prev，cur和prev位置的值交换,++cur
2.cur找到比key大的值，++cur
说明
1.prev要么紧跟着cur
2.prev跟cur中间间隔着比key大的一段值区间
思路：
通过创建两个指针，prev指针指向数组序列首元素位置，cur指向prev的下一个位置，cur通过遍历去寻找比key基准值小的，若找到了，还得看prev的下一个位置是否为cur所处的位置，若prev的下一个位置确实为cur所处位置，则将cur指向的值与prev指向的值进行互换，若prev的下一个位置不是cur所处位置，则cur继续往后遍历，直到cur遍历结束，最后要将key基准值与prev指向的值进行互换，最终确认基准值处于数组序列的中间位置。
//交换函数 void Swap(int* p1, int* p2) { int tmp = *p1; *p1 = *p2; *p2 = tmp; } //三数取中 int GetMidIndex(int* arr, int left, int right) { int mid = (right - left) / 2 + left; if (arr[left] < arr[mid]) { if (arr[mid] < arr[right]) { return mid; } else if (arr[left] > arr[right]) { return left; } else { return right; } } else { //arr[left]>=arr[mid] if (arr[mid] > arr[right]) { return mid; } else if (arr[left] < arr[right]) { return left; } else { return right; } } } //前后指针法 int PartSort(int* arr, int left, int right) { int mid = GetMidIndex(arr, left, right); Swap(&arr[left], &arr[mid]); int keyi = left; //基准值下标放在最左侧 int prev = left; int cur = left + 1; while (cur<=right) { if (arr[cur] < arr[keyi] && ++prev != cur) { Swap(&arr[prev], &arr[cur]); } ++cur; } Swap(&arr[keyi], &arr[prev]); return prev; }
归并排序
思路：
从下往上的归并排序：将待排序的数列分成若干个长度为1的子数列，然后将这些数列两两合并；得到若干个长度为2的有序数列，再将这些数列两两合并；得到若干个长度为4的有序数列，再将它们两两合并；直接合并成一个数列为止，从上往下的归并排序：它与"从下往上"在排序上是反方向的。
代码:
//辅助归并排序递归的子函数 void _MergeSort(int* a, int* tmp, int begin, int end) { if (begin >= end) return;//单个或者不存在其区间就结束递归 //类似于后序： int middle = (begin + end) / 2; int begin1 = begin; int end1 = middle; int begin2 = middle + 1; int end2 = end; _MergeSort(a, tmp, begin1, end1); _MergeSort(a, tmp, begin2, end2); //此时认为 [begin1, end1] 和 [begin2, end2]两段区间上有序 //归并算法 int i = begin; while (begin1 <= end1 && begin2 <= end2) { if (a[begin1] <= a[begin2]) { tmp[i++] = a[begin1++]; } else { tmp[i++] = a[begin2++]; } } while (begin1 <= end1) { tmp[i++] = a[begin1++]; } while (begin2 <= end2) { tmp[i++] = a[begin2++]; } memcpy(a + begin, tmp + begin, sizeof(int) * (end - begin + 1)); } //归并排序 递归版本 void MergeSort(int* a, int n) { //首先malloc一个数组 int* tmp = (int*)malloc(sizeof(int) * n); if (tmp == NULL) { printf("未能申请到内存\n"); exit(-1); } //第一次传入 0 和 n - 1 传入闭区间 _MergeSort(a, tmp, 0, n - 1); free(tmp); }
