【数据结构实战】一起开启数据结构有序之门
目录
说起排序，我想大家并不陌生，在我们的日常生活中到处都有他的影子。我们点外卖的时候，程序会优先推出评价高的店让我们选择，王者每周都要把每个英雄在每个地区的战力排序出来，甚至高考时，一个省几十万人的成绩也需要排序算法才能搞定。因此排序对我们生活的重要性不言而喻，我们之前学的那些数据结构，也是为了各种各样的排序算法。
一、排序的概念及应用
1.1 排序的概念
排序：所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。 稳定性：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的。
1.2 排序的应用
游戏、外卖、购物……许多地方都离不开排序
1.3 常见的排序算法
经过各位前辈大佬们的不断迭代，现在排序算法已经很成熟了，主要分为下面几种排序：
接下来我们将依次实现以上排序算法，并领悟其中的排序思想
二、插入排序
2.1 直接插入排序
2.1.1 基本思想
直接插入排序的思想很简单，就是：把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列 。（也可以理解为你正在和你的好朋友们打斗地主，现在好友正在一张一张的发牌，你就只能一次摸一张上来，再将这一张牌插入到正确的位置上，理牌的过程就是插入排序）
2.1.2 直接插入排序代码实现
// 插入排序 升序 void InsertSort(int* a, int n) { int i = 0; for (i = 1; i < n; i++) { int end = i - 1; int tmp = a[i]; while (end >= 0) { if (tmp < a[end]) { a[end + 1] = a[end]; end--; } else break; } a[end + 1] = tmp; } }2.1.3 直接插入排序的特性总结
元素集合越接近有序，直接插入排序算法的时间效率越高时间复杂度：O(N^2)空间复杂度：O(1)，它是一种稳定的排序算法稳定性：稳定
2.2 希尔排序
2.2.1 基本思想
仔细观察插入排序你就会发现，如果序列越接近有序，那么他的时间复杂度就越小，最好的情况他的时间复杂度为O(N)。那么此时聪明的人类就能想到，如果我在每次选择排序的基础上，在调整这个序列使他越来越接近有序，那他的时间复杂度是不是就会快很多。
这个思路就是希尔排序的思路：
先选定一个整数，把待排序文件中所有记录分成个组，所有距离为的记录分在同一组内，并对每一组内的记录进行排序。然后，取，重复上述分组和排序的工作。当到达=1时，所有记录在统一组内排好序。
2.2.2 希尔排序代码实现
//希尔排序 void ShellSort(int* a, int n) { int i = 0; int gap = n/2; while (gap >= 1) { for (i = 0; i < n - gap; i++) { int end = i; int tmp = a[end + gap]; while (end >= 0) { if (tmp < a[end]) { a[end + gap] = a[end]; end -= gap; } else { break; } } a[end + gap] = tmp; } gap /= 2; } } 2.2.3 希尔排序的特性总结
1. 希尔排序是对直接插入排序的优化。
2. 当gap > 1时都是预排序，目的是让数组更接近于有序。当gap == 1时，数组已经接近有序的了，这样就会很快。这样整体而言，可以达到优化的效果。我们实现后可以进行性能测试的对比。
3. 希尔排序的时间复杂度不好计算，因为gap的取值方法很多，导致很难去计算，因此在好些树中给出的希尔排序的时间复杂度都不固定（约为：O(N^1.3)）
三、选择排序
3.1 直接选择排序
3.1.1 基本思想
将数组全部遍历一遍选出最小的放到最前面，然后再继续遍历，直到有序为止。
3.1.2 直接选择排序代码实现
// 选择排序 void SelectSort(int* a, int n) { int j = 0; for (j = 0; j < n; j++) { int i = j; int tmp = j; int mini = j; for (i = j; i < n; i++) { if (a[mini] > a[i]) { maxi = i; } } swap(&a[tmp], &a[mini]); } } 这样每次都选了最小的，然后依次排序，但是这样的空间复杂度为O(N^2)，效率很低，可以在每次选择的时候都把最大的和最小的选出来，然后再排序，就能优化一些，不过时间复杂度依然是O(N^2)
// 选择排序 void SelectSort(int* a, int n) { int left = 0, right = n - 1; while(left < right) { int maxi = right, mini = left; int i = left; for(i = left; i < right; i++) { if (a[mini] > a[i]) { mini = i; } if (a[maxi] < a[i]) { maxi = i; } } swap(&a[right], &a[maxi]); if(mini ==right) { mini = maxi; } swap(&a[left], &a[mini]); left++; right--; } }3.1.3 选择排序的特性总结
1. 直接选择排序思考非常好理解，但是效率不是很好。实际中很少使用
2. 时间复杂度：O(N^2)
3. 空间复杂度：O(1)
4. 稳定性：不稳定
3.2 堆排序
巧妙地利用堆的数据结构来选择数据会有意想不到的效果，可以让时间复杂度减小到O(NlogN)，可以大大的提高选择排序的效率
3.2.1 基本思想
运用堆的数据结构，对数据建堆，然后依次出堆，就可以了
3.2.2 堆排序代码实现
//堆排序 void AdjustDwon(int* a, int n, int root) { 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) { //建堆 int i = 0; for (i = (n - 2) / 2; i >=0 ; i--) { AdjustDwon(a, n, i); } //排序 for (i = 0; i < n; i++) { swap(&a[0], &a[n - i -1]); AdjustDwon(a, n - i - 1, 0); } }3.1.3 堆排序的特性总结
有了堆的数据结构之后，选择一个数据将会变得简单很多，所以他的空间复杂度也会大大提升
1. 堆排序使用堆来选数，效率就高了很多。
2. 时间复杂度：O(N*logN)
3. 空间复杂度：O(1)
4. 稳定性：不稳定
四、交换排序
4.1 冒泡排序
4.1.1 基本思想
冒泡排序可是我们的老相识了，在学C语言的时候我们就认识过冒泡排序啦，就是将大的数像冒泡泡一样交换上去，就能得到有序序列
4.1.2 冒泡排序代码实现
//冒泡排序 void BubbleSort(int* a, int n) { int i = 0; for (i = 0; i < n - 1; i++) { bool order = 1; int j = 0; for (j = 0; j < n - i - 1; j++) { if (a[j] > a[j + 1]) { swap(&a[j], &a[j + 1]); order = 0; } } if (order) { break; } } } 4.1.3 冒泡排序的特性总结
1. 冒泡排序是一种非常容易理解的排序
2. 时间复杂度：O(N^2)
3. 空间复杂度：O(1)
4. 稳定性：稳定
4.2 快速排序
快速排序就是我们需要讲解的重点了，之所以称他为快速排序是有他的道理的，让我们一起来感受一下前辈们的智慧吧
4.2.1 基本思想
任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。
请看下买你的动图，来掌握第一种快排的思想
上面动画演示的就是第一个把基准值排到合适位置的方法，下面这个动图将会展示第二种将基准值排到恰当位置的方法（挖坑法）：
还有最后一种，前后指针法：
理解了单次排序的思路，就掌握快排思路的一半了：
先将左边第一个数字设为基准值（也可以是其他的数字，这里以左边第一个为例子）再把他放到合适的位置上面（合适的位置指的就是前面的数字比他小，后面的数字比他大）再依次重复上述步骤，直到序列有序为止
4.2.2 快速排序代码实现
这里我把三个方法都写出来给大家：
//快速排序 int FindMid(int a, int b, int c) { if (a > b) { if (b > c) return b; else if (a > c) return c; else return a; } else //a < b { if (a > c) return a; else if (b > c) return c; else return b; } } int PartSort1(int* a, int left, int right) { int mid = FindMid(a[left], a[right], a[(left + right) / 2]); if (mid != left) { swap(&a[mid], &a[left]); } int key = left; while (left < right) { while (left < right && a[right] >= a[key]) { right--; } while (left < right && a[left] <= a[key]) { left++; } swap(&a[left], &a[right]); } swap(&a[key], &a[left]); return left; } int PartSort2(int* a, int left, int right) { int mid = FindMid(a[left], a[right], a[(left + right) / 2]); if (mid != left) { swap(&a[mid], &a[left]); } int hole = left, key = a[left]; while (left < right) { while (left < right && a[right] >= a[key]) { right--; } swap(&a[right], &a[hole]); hole = right; while (left < right && a[left] <= a[key]) { left++; } swap(&a[left], &a[hole]); hole = left; } swap(&a[key], &a[left]); return left; } int PartSort3(int* a, int left, int right) { int mid = FindMid(a[left], a[right], a[(left + right) / 2]); if (mid != left) { swap(&a[mid], &a[left]); } int key = left; int prev = left, cur = left + 1; while (cur <= right) { if (a[cur] < a[key] && ++prev != cur) { swap(&a[cur], &a[prev]); } cur++; } swap(&a[key], &a[prev]); return prev; } void QuickSort(int* a, int left, int right) { if (left >= right) return; int begin = left, end = right; //小区间优化 if (end - begin + 1 <= 10) { InsertSort(a + begin, end - begin + 1); return; } //int mid = PartSort1(a, begin, end); //int mid = PartSort2(a, begin, end); int mid = PartSort3(a, begin, end); QuickSort(a, begin, mid - 1); QuickSort(a, mid + 1, end); }4.2.3 快速排序的特性总结
1. 快速排序整体的综合性能和使用场景都是比较好的，所以才敢叫快速排序
2. 时间复杂度：O(N*logN)
3. 空间复杂度：O(logN)
4. 稳定性：不稳定
结尾：排序性能对比
最后在给大家看看每个排序的对比吧（10w个数据排序，单位是ms）：
再看希尔排序、堆排序和快速排序的对比（100w个数据）：
1000w个数据：
这样我们就可以清晰地看到每个排序的不同的用法和性能差距
最后还剩下一个归并排序，下期在给大家补吧，最近期末考啦，狐狸要忙着速成捏~
886~记得给个三连QAQ
