1. 排序概要
排序： 就是将一串随机数据，按照从小到大、或者从大到小重新排列一遍，使它变成有序的数据，便于人们观察和提取数据。
常见的排序算法有：插入排序、选择排序、交换排序、归并排序。
2. 插入排序
把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列。
直接插入排序
当插入第i（i>=1）个元素时，前面的arr[0]，arr[1]…arr[i-1]已经排好序，此时用arr[i]的排序码与前面的arr进行比较，找到插入位置就将arr[i]插入，原来位置上的元素，顺序后移。
//插入排序 void InsertSort(int* a, int n) { //从头往后开始遍历 for (int i = 0; i < n - 1; i++) { int end = i; int key = a[end + 1]; //保存最后的值 while(end>=0) { //比前边小就交换 if (key < a[end]) { //前面的给后面 a[end + 1] = a[end]; } else { break; } end--; } a[end + 1] = key; } }
特性总结：
1.元素集合接近有序，直接插入排序算法时间效率越高。
2.时间复杂度：O(N^2)
3.空间复杂度：O(1)
4.稳定性：稳定
希尔排序（缩小增量排序）
先选取一个步长gap,把每隔gap长度的数据分成一个个组，所有相距为gap的数据在同一个组，并且对每组的数据进行插入排序，然后缩小gap，重复上述过程，直至gap为1，当gap为1时，所有记录在统一组内排好序。
//希尔排序 void ShellSort(int* a, int n) { int gap = n; //gap>1，预排 //gap ==1 ,插入排序 while (gap > 1) { gap = (gap / 3) + 1; for (int i = 0; i < n - gap; i++) { //单次排序调整 int end = i; int key = a[end + gap]; while (end >= 0) { if (key < a[end]) { a[end + gap] = a[end]; } else { break; } end -= gap; } a[end + gap] = key; } } }
特性总结：
1.希尔是对直接插入排序的优化。
2.当gap>1时是预排序，目的是让数组更接近有序。当gap==1时，数组已经接近有序，这样就会很快。预排序可以让大数更快的走向末尾，小数更快的走向开始。
3.时间复杂度：接近于O（N^1.3）
4.空间复杂度：O（1）
5.稳定性：不稳定
3.选择排序
每一次从待排序的元素中，找到最小（最大）的一个元素，存放在序列的起始位置，直到全部的待排序元素排序完。
直接选择排序
在元素集合0~i-1中找到最小的元素，记住数组元素的下标，若遍历完后，该数组下标的位置不是当前数组的起始位置，则该元素与起始位置交换，重复上述步骤，直到集合剩余一个元素。
//选择排序 void SelectSort(int* a, int n) { //每次选择最大和最小的 int begin = 0; int end = n - 1; while (begin < end) { int min_index = begin; int max_index = begin; for (int i = begin; i <= end; i++) { //发现更小的 if (a[min_index] > a[i]) { min_index = i; } //发现更大的 else if (a[max_index] < a[i]) { max_index = i; } } Swap(&a[begin], &a[min_index]); //防止最大的数字被换走 if (max_index == begin) { max_index = min_index;//把下标再赋回来 } Swap(&a[end], &a[max_index]); end--; begin++; } }
特性总结：
1.虽然思想很好理解，但是效率低，很少使用。
3.时间复杂度：O（N^2）
4.空间复杂度：O（1）
5.稳定性：不稳定
堆排序
堆排序是利用一种堆的数据结构来进行排序的算法，大堆排升序，小堆排降序，每次只选择堆顶的元素，作为最大值或最小值，直至堆的集合个数为1。
//堆排序(大堆) //先建堆，从后往前建堆效率更高. //向下建堆效率高，从后往前，每个结点的左右子树都建成堆 void AdjustDown(int* a, int n, int parent) { //比较左右孩子较小的一个 //如果条件满足再和父亲交换 //再看调整的孩子需不需要 int child = 2 * parent + 1; //有没有叶子结点 while (child<n) { //右孩子存在，右孩子大于左孩子 if (child + 1 < n && a[child] < a[child + 1]) { child++; } //左孩子大于父亲 if (a[child] > a[parent]) { //孩子父亲交换，并且父亲变为孩子 Swap(&a[child], &a[parent]); parent = child; child = 2*parent+1; } else { break; } } } //堆排序 void HeapSort(int* a, int n) { //1.先建堆 //2.然后交换首尾元素 //再向下调整 int parent = (n-1-1) / 2; while (parent>=0) { AdjustDown(a, n, parent); --parent; } int end = n-1; while (end > 0) { Swap(&a[0], &a[end]);//end是下标 AdjustDown(a, end, 0); //end 代表个数 --end; } }
特性总结：
1.堆排序使用堆来选数字，效率提升很大
3.时间复杂度：O（NlogN）
4.空间复杂度：O（1）循环建堆
5.稳定性：不稳定
4. 交换排序
交换，根据序列中两个记录的键值的比较来对换这两个记录在序列中的位置。交换排序的特点是：将键值较大的数字向尾部移动，将键值较小的数字向序列的前部移动。
冒泡排序
//冒泡排序 void BubbleSort(int* a, int n) { //从小冒到大 //重复 int flag = 0; for (int j = 0; j < n - 1; j++) { //每次排序完一个，将flag置0 flag = 0; for (int i = 0; i < n - 1 - j; i++) { if (a[i] > a[i + 1]) { flag = 1; Swap(&a[i], &a[i + 1]); } } if (flag == 0) { break; } } }
特性总结：
1.时间复杂度：O（N^2）
2.空间复杂度：O（1）
3.稳定性：稳定
快速排序
递归思想：按照先序递归的方法，先找基准值，然后保证左子序列全部小于基准值，右子序列的值全部大于基准值。然后再次划分，直至子序列为1即可。
快速排序框架：
// 假设按照升序对array数组中[left, right)区间中的元素进行排序 void QuickSort(int array[], int left, int right) { if(right - left <= 1) return; // 按照基准值对array数组的 [left, right)区间中的元素进行划分 int div = partion(array, left, right); // 划分成功后以div为边界形成了左右两部分 [left, div) 和 [div+1, right) // 递归排[left, div) QuickSort(array, left, div); // 递归排[div+1, right) QuickSort(array, div+1, right); }
霍尔版本（hoare）
左边作key，右边先走，找小，遇到小于key的数停下，然后左边走找大，遇到大于key的数停下，交换左右两个位置的数字，left==right。
问什么左边作key，右边先走呢？
要保证小于的位置比key小或者就是key的位置：1.R先走，R停下来，L去遇到R（因为R找的是小，R停下来的位置一定小于key）；2.R先走，R没有找到比key小的值，R去遇到了L（相遇的位置是上一轮停下来的位置，要么就是key的位置，要么比key要小）
//快速排序（霍尔法） void QuickSort_old_hoare(int* a, int begin, int end) { //左边作key,右边先走找小，找到了停下 //左边再走找大，找到停下，交换 //重复 if (begin >= end) { return; } //一次排序 int left = begin; int right = end; int keyi = begin; while (left < right) { //找小 while (left < right && a[keyi] <= a[right]) { --right; } //找大 while (left < right && a[left] <= a[keyi]) { ++left; } Swap(&a[left], &a[right]); } Swap(&a[left], &a[keyi]); keyi = left; //递归 QuickSort_old_hoare(a, begin, keyi - 1); QuickSort_old_hoare(a, keyi+1, end); }
函数分开版本：
void QuickSort(int* a, int begin,int end) { if (begin >= end) { return; } if (end-begin>10) { int keyi = Partition2(a, begin, end); QuickSort(a, begin, keyi - 1); QuickSort(a, keyi+1, end); } else { InsertSort(a + begin, end - begin + 1); } } //快排的霍尔版本 int Partition1(int* a, int begin, int end) { int left = begin; int right = end; int keyi = begin; while (left < right) { //找小 while (left < right && a[right] >= a[keyi]) { --right; } //找大 while (left < right && a[left] <= a[keyi]) { ++left; } Swap(&a[right], &a[left]); } Swap(&a[keyi], &a[left]); keyi = left; return keyi; }
