👉排序的概念及其运用👈
排序的概念
排序：所谓排序，就是使一串记录，按照其中的某个或
某些关键字的大小，递增或递减的排列起来的操作。
稳定性：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次
序保持不变，即在原序列中，r[i] = r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的。
内部排序：数据元素全部放在内存中的排序。
外部排序：数据元素太多不能同时放在内存中，根据排序过程的要求不能在内外存之间移动数据的排序。
排序的运用
常见的排序算法
👉常见排序算法的实现👈
插入排序
1.基本思想
插入排序算法的基本思想是把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列。
实际中，我们玩扑克的时候，就用了插入排序的思想。
2.直接插入排序
当插入第
i (i >= 1)个元素时，前面的i - 1个元素已经排好序了，此时将i个元素依次从后向前和前面的元素相比。如果前面的元素大于第i个元素，则原来位置上的元素往后移动一位。如果前面的元素小于第i个元素，则第i个元素插入到前面元素的后面。
直接插入排序代码实现
// 插入排序 // 最坏时间复杂度为O(N^2) -- 逆序 // 最好时间复杂度为O(N) -- 顺序 void InsertSort(int* a, int n) { // [0, end]有序 插入end+1 [0, end+1]有序 for (int i = 0; i < n - 1; i++) { int end = i; int tmp = a[end + 1]; while (end >= 0) { if (a[end] > tmp) { a[end + 1] = a[end]; --end; } else { break; } } a[end + 1] = tmp; } }
当数组逆序时，插入排序的时间复杂度最坏，为O(N^2)；当数组顺序时，插入排序的时间复杂度最好，为O(N)。面对数组中的大多数数据有序的情况，插入排序是一种不错的选择，因为此时插入排序的时间复杂度为O(N)。插入排序是稳定的排序，空间复杂度为O(N)。
3.希尔排序（缩小增量排序）
希尔排序法又称缩小增量法。希尔排序法的基本思想是：先选定一个整数gap，把待排序的数组分成个gap组，每组有n / gap个元素，所有距离为gap的元素分在同一组内，并对每一组内的元素进行排序。然后缩小gap的值，去重复上述分组和排序的工作。当gap == 1时，数组就达到了有序。
通过上面的内容，相信大家对希尔排序有了一定的了解，那现在我们来看一下希尔排序的代码。
希尔排序代码实现
// 希尔排序 // 时间复杂度为O(N^1.3) void ShellSort(int* a, int n) { // [0, end]有序 插入end+gap [0, end+gap]有序 间隔为gap的数据 //int gap = n; //while (gap > 1) //{ // // 一组一组排序 // //gap /= 2; // gap = gap / 3 + 1; // for (int i = 0; i < gap; i++) // { // for (int j = 0; j < n - gap; j++) // { // int end = j; // int tmp = a[end + gap]; // while (end >= 0) // { // if (a[end] > tmp) // { // a[end + gap] = a[end]; // end -= gap; // } // else // { // break; // } // a[end + gap] = tmp; // } // } // } //} // [0, end]有序 插入end+gap [0, end+gap]有序 间隔为gap的数据 // gap > 1 预排序 // gap = 1 直接插入排序 // 多组数据并排 int gap = n; while (gap > 1) { //gap /= 2; gap = gap / 3 + 1; for (int i = 0; i < n - gap; i++) { int end = i; int tmp = a[end + gap]; while (end >= 0) { if (a[end] > tmp) { a[end + gap] = a[end]; end -= gap; } else { break; } } a[end + gap] = tmp; } } }
希尔排序的特性总结
gap /= 2和gap = gap / 3 + 1两种方式均可使gap达到1，当gap == 1时，希尔排序为直接插入排序。
gap越大，大的元素可以越快跳到数组的后面，小的元素可以越快跳到数组的前面，但数组不是很接近有序；gao越小时，跳得越慢，数组越接近有序。
希尔排序是对直接插入排序的优化。
当gap > 1时都是预排序，目的是让数组更接近于有序。当gap == 1时，数组已经接近有序的了，这样就会很快。这样整体而言，可以达到优化的效果。
希尔排序的时间复杂度不好计算，因为gap的取值方法很多，导致很难去计算，因此在好些书中给出的希尔排序的时间复杂度都不固定。我们通常认为希尔排序的时间复杂度为O(N^1.3)。
《数据结构(C语言版)》— 严蔚敏
《数据结构-用面相对象方法与C++描述》— 殷人昆
稳定性：不稳定
为什么希尔排序的时间复杂度难算？
因为gap是一个变化的值，每一次预排序过后，数组就变得有序了一点，就不能每次都按照最坏的情况来算希尔排序的时间复杂度，所以希尔排序的时间复杂度就比较难算了。
选择排序
1.基本思想
选择排序的基本思想是每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的
数据元素排完 。
2.直接选择排序
- 在元素集合
arr[i]到arr[n-1]中选择关键码最大(小)的数据元素- 若它不是这组元素中的最后一个(第一个)元素，则将它与这组元素中的最后一个（第一个）元素交换
- 在剩余的arr[i]到arr[n-2]（arr[i+1]到arr[n-1]）集合中，重复上述步骤，直到集合剩余 1 个元素。
直接选择排序代码实现
// 选择排序 // 最坏时间复杂度为O(N^2) // 最好时间复杂度为O(N^2) void SelectSort(int* a, int n) { int begin = 0; int end = n - 1; while (begin < end) { // 选出最小的放在begin位置 // 选出最大的放在end位置 int minPos = begin; int maxPos = begin; for (int i = begin + 1; i <= end; i++) { if (a[i] < a[minPos]) { minPos = i; } if (a[i] > a[maxPos]) { maxPos = i; } } Swap(&a[begin], &a[minPos]); // 修正一下maxPos if (begin == maxPos) // 最大值在最小值的位置 { maxPos = minPos; } Swap(&a[end], &a[maxPos]); ++begin; --end; } }
直接选择排序的特性总结
- 直接选择排序思考非常好理解，但是效率不是很好。实际中很少使用
- 时间复杂度：
O(N^2) - 空间复杂度：
O(1) - 稳定性：不稳定
3.堆排序
堆排序 (Heapsort) 是指利用堆这种数据结构所设计的一种排序算法，它是选择排序的一种。它是通过堆来进行选择数据。需要注意的是排升序要建大堆，排降序建小堆。
堆排序代码实现
void Swap(int* x, int* y) { int tmp = *x; *x = *y; *y = tmp; } // 向下调整算法 void AdjustDown(int* a, int size, int parent) { int maxChild = 2 * parent + 1; while (maxChild < size) { // 右孩子存在且右孩子大于左孩子 if (maxChild + 1 < size && a[maxChild + 1] > a[maxChild]) { maxChild++; } if (a[maxChild] > a[parent]) { Swap(&a[maxChild], &a[parent]); parent = maxChild; maxChild = 2 * parent + 1; } else { break; } } } // 堆排序 时间复杂度O(N*logN) void HeapSort(int* a, int n) { // 大思路：选择排序，依次选数，从后往前排 // 升序 -- 建大根堆 // 降序 -- 建小根堆 // 建堆 -- 向下调整建堆 - O(N) // 从倒数第一个非叶节点(最后一个节点的父亲)开始向下调整直到调整到根节点 for (int i = (n - 2) / 2; i >= 0; i--) { AdjustDown(a, n, i); } // 选数 N*logN int i = 1; while (i < n) { Swap(&a[0], &a[n - i]); AdjustDown(a, n - i, 0); i++; } }
对于堆排序不太了解的可以看一下这篇文章：【数据结构与算法】二叉树（上），里面详细介绍了堆排序。
堆排序的特性总结
堆排序使用堆来选数，效率就高了很多
时间复杂度：O(N*logN)
空间复杂度：O(1)
稳定性：不稳定
