2.3 交换排序
基本思想
所谓交换，就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置,交换排序的特点是：将键值较大的记录向序列的尾部移动，键值较小的记录向序列的前部移动。
2.3.1 冒泡排序
* 比较相邻的元素。如果第一个比第二个大，就交换它们两个；
* 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数；
* 针对所有的元素重复以上的步骤，除了最后一个；
* 重复步骤1~3，直到排序完成。
代码实现:
void swap(int* a, int* b) { int temp = *a; *a = *b; *b = temp; } void bubblesort(int* a, int n) { for (int i = 0; i < n - 1; i++) { for (int j = 0; j < n - 1 - i; j++) { if (a[j] > a[j + 1]) { swap(&a[j], &a[j + 1]); } } } }
冒泡排序的特征总结:
1. 冒泡排序是一种非常容易理解的排序
2. 时间复杂度：O(N^2)
3. 空间复杂度：O(1)
4. 稳定性：稳定
2.3.2 快速排序
快速排序使用分治法来把一个串（list）分为两个子串（sub-lists）。具体算法描述如下：
* 从数列中挑出一个元素，称为 “基准”（pivot）；
* 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
* 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。
动图演示:
代码实现:
方式一:hoare版本
int getmidindex(int* a, int left, int right) { int mid = (left + right) / 2; if (a[left] < a[mid]) { if (a[mid] < a[right]) return mid; else if (a[left] > a[right]) return left; else return right; } else { if (a[left] < a[right]) return left; else if (a[mid] > a[right]) return mid; else return right; } } int partion(int* a, int left, int right) { int mini = getmidindex(a, left, right); swap(&a[mini], &a[left]); 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[left], &a[keyi]); return left; } void quicksort(int* a, int left, int right) { if (left >= right) { return; } int keyi = partion(a, left, right); quicksort(a, left, keyi - 1); quicksort(a, keyi + 1, right); }
方式二:挖坑法
int GetMidIndex(int* a, int left, int right) { //int mid = (left + right) / 2; int mid = left + ((right - left) >> 1); if (a[left] < a[mid]) { if (a[mid] < a[right]) { return mid; } else if (a[left] > a[right]) { return left; } else { return right; } } else // a[left] > a[mid] { if (a[mid] > a[right]) { return mid; } else if (a[left] < a[right]) { return left; } else { return right; } } } int Partion2(int* a, int left, int right) { // 三数取中 -- 面对有序最坏情况，变成选中位数做key，变成最好情况 int mini = GetMidIndex(a, left, right); Swap(&a[mini], &a[left]); int key = a[left]; int pivot = left; while (left < right) { // 右边找小, 放到左边的坑里面 while (left < right && a[right] >= key) { --right; } a[pivot] = a[right]; pivot = right; // 左边找大，放到右边的坑里面 while (left < right && a[left] <= key) { ++left; } a[pivot] = a[left]; pivot = left; } a[pivot] = key; return pivot; }
方式三:前后指针法
int GetMidIndex(int* a, int left, int right) { //int mid = (left + right) / 2; int mid = left + ((right - left) >> 1); if (a[left] < a[mid]) { if (a[mid] < a[right]) { return mid; } else if (a[left] > a[right]) { return left; } else { return right; } } else // a[left] > a[mid] { if (a[mid] > a[right]) { return mid; } else if (a[left] < a[right]) { return left; } else { return right; } } } int Partion3(int* a, int left, int right) { // 三数取中 -- 面对有序最坏情况，变成选中位数做key，变成最好情况 int mini = GetMidIndex(a, left, right); Swap(&a[mini], &a[left]); int keyi = left; int prev = left; int cur = prev + 1; while (cur <= right) { if (a[cur] < a[keyi] && ++prev != cur) { Swap(&a[cur], &a[prev]); } ++cur; } Swap(&a[prev], &a[keyi]); return prev; }
快速排序的特征总结:
1. 快速排序整体的综合性能和使用场景都是比较好的，所以才敢叫快速排序
2. 时间复杂度：O(N*logN)
3. 空间复杂度：O(logN)
4. 稳定性：不稳定
2.4 归并排序
归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。
* 把长度为n的输入序列分成两个长度为n/2的子序列；
* 对这两个子序列分别采用归并排序；
* 将两个排序好的子序列合并成一个最终的排序序列。
动图演示:
代码实现:
方式一:递归
void _MergeSort(int* a, int left, int right, int* tmp) { if (left >= right) { return; } int mid = (left + right) / 2; // [left, mid] [mid+1, right] 有序 _MergeSort(a, left, mid, tmp); _MergeSort(a, mid + 1, right, tmp); int begin1 = left, end1 = mid; int begin2 = mid+1, end2 = right; int i = left; 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++]; } // tmp 数组拷贝回a for (int j = left; j <= right; ++j) { a[j] = tmp[j]; } } void MergeSort(int* a, int n) { int* tmp = (int*)malloc(sizeof(int)*n); if (tmp == NULL) { printf("malloc fail\n"); exit(-1); } _MergeSort(a, 0, n - 1, tmp); free(tmp); tmp = NULL; }
方式二:非递归
void MergeSortNonR(int* a, int n) { int* tmp = (int*)malloc(sizeof(int)*n); if (tmp == NULL) { printf("malloc fail\n"); exit(-1); } int gap = 1; while (gap < n) { for (int i = 0; i < n; i += 2 * gap) { // [i,i+gap-1] [i+gap,i+2*gap-1] int begin1 = i, end1 = i + gap - 1; int begin2 = i + gap, end2 = i + 2 * gap - 1; // 核心思想：end1、begin2、end2都有可能越界 // end1越界 或者 begin2 越界都不需要归并 if (end1 >= n || begin2 >= n) { break; } // end2 越界，需要归并，修正end2 if (end2 >= n) { end2 = n- 1; } int index = i; while (begin1 <= end1 && begin2 <= end2) { if (a[begin1] < a[begin2]) { tmp[index++] = a[begin1++]; } else { tmp[index++] = a[begin2++]; } } while (begin1 <= end1) { tmp[index++] = a[begin1++]; } while (begin2 <= end2) { tmp[index++] = a[begin2++]; } // 把归并小区间拷贝回原数组 for (int j = i; j <= end2; ++j) { a[j] = tmp[j]; } } gap *= 2; } free(tmp); tmp = NULL; }
归并排序的特征总结:
1. 归并的缺点在于需要O(N)的空间复杂度，归并排序的思考更多的是解决在磁盘中的外排序问 题。
2. 时间复杂度：O(N*logN)
3. 空间复杂度：O(N)
4. 稳定性：稳定
3.排序算法复杂度及稳定性分析
以上是七大常见算法的相关知识点，有不足的地方或者对代码有更好的见解，欢迎评论区留言共同商讨，共同进步！！
