数据布局学习条记——排序

排序

1. 排序相干概念

稳定性：关键字雷同的数据记录，排序后相对顺序仍保持稳定

例如，两个25，在排序完后，有*的25仍在后方，阐明该排序算法是稳定的
内部排序：数据元素全部放在内存中的排序
外部排序：数据元素太多不能同时放在内存中，根据排序过程的要求不停地在表里存之间移动数据的排序
2. 常见排序算法及实现

2.1 插入排序

直接插入排序

直接插入排序是一种简朴的插入排序法，其根本头脑是：把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列
简朴来说，待排序数据如下

排序轮次如下

每一轮排好一个数，下一轮新拿出来的数，插入到原来已排好的序列中，直到所有数都排好
直插特性总结：

• 元素聚集越接近有序，算法的时间效率越高
  
• 时间复杂度：O(N^2)
  
• 空间复杂度：O(1)
  
• 算法稳定
  

代码示例：

1. // 插入排序
2. void InsertSort(int* a, int n) {
3.         for (int i = 1; i < n; i++) {
4.                 int temp = a[i];
5.                 int j = i;
6.                 while (j > 0)
7.                 {
8.                         if (a[j - 1] > temp) {
9.                                 a[j] = a[j - 1];
10.                         }
11.                         else { break; }
12.                         j--;
13.                 }
14.                 a[j] = temp;
15.         }
16. }

复制代码

希尔排序（缩小增量排序）

希尔排序法的根本头脑是：先选定一个整数gap，把待排序文件中所有记录分成gap个组，所有距离为gap的记录分在同一组内，并对每一组内的记录进行排序。然后，gap取更小的值（一样寻常是gap/2），重复上述分组和排序的工作。当到达gap=1时，所有记录在同一组内排好序。
可以这么明白：

• 预排序，使数组接近有序
  
• 实行插入排序
  

看如下例子
待排序序列

取gap的值，一样寻常是n/2，所以这里取3

排序后结果如第二行所示
一样寻常来说gap /= 2后为1，但这里先取gap = 2以便明白

然后最后一趟gap = 1

希尔特性总结：

• 希尔排序是对直接插入排序的优化
  
• 当gap > 1时都是预排序，目标是让数组更接近于有序。当gap == 1时，数组已经接近有序的了，这样就会很快。这样整体而言，可以达到优化的结果
  
• 希尔排序的时间复杂度不好计算，因为gap的取值方法很多，导致很难去计算，因此在好些书中给出的希尔排序的时间复杂度都不固定
  
• 稳定性：不稳定
  

代码示例：

1. // 希尔排序
2. // 注意，如果每组各自排的话，会有四重循环（最外层gap变化，第二层不同组各自处理，最后两层为插入自带）
3. // 此处仅3层循环，使多组排序同时进行
4. void ShellSort(int* a, int n) {
5.         int gap = n / 2;
6.         while (gap)
7.         {
8.                 for (int i = gap; i < n; i++) {
9.                         int temp = a[i];
10.                         int j = i;
11.                         while (j >= gap)
12.                         {
13.                                 if (a[j - gap] > temp) {
14.                                         a[j] = a[j - gap];
15.                                 }
16.                                 else { break; }
17.                                 j -= gap;
18.                         }
19.                         a[j] = temp;
20.                 }
21.                 gap /= 2;
22.         }
23. }

复制代码

2.2 选择排序

选择排序

根本头脑：每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完
看一下示例就好明白了
初始序列

选择特性总结：

• 直接选择效率一样寻常，实际中很少使用
  
• 时间复杂度：O(N^2)
  
• 空间复杂度：O(1)
  
• 稳定性：不稳定
  

示例代码

1. // 选择排序
2. // 此为优化过的选择，每一轮分别找到一个最大值和最小值，放于开头和末尾
3. void SelectSort(int* a, int n) {
4.         int bg = 0, ed = n - 1;
5.         while (bg < ed)
6.         {
7.                 int min_idx = bg, max_idx = ed;
8.                 for (int i = bg; i <= ed; i++) {
9.                         if (a[i] > a[max_idx]) {
10.                                 max_idx = i;
11.                         }
12.                         if (a[i] < a[min_idx]) {
13.                                 min_idx = i;
14.                         }
15.                 }
16.                 int temp = a[bg];
17.                 a[bg] = a[min_idx];
18.                 a[min_idx] = temp;
19.                 temp = a[ed];
20.         // 如果发生如下情况，此时bg的值经过交换已经到了min_idx中，需要调整max_idx的值
21.                 if (bg == max_idx){ max_idx = min_idx; }
22.                 a[ed] = a[max_idx];
23.                 a[max_idx] = temp;
24.                 bg++, ed--;
25.         }
26. }

复制代码

堆排序

堆排序(Heapsort)是指利用堆积树（堆）这种数据布局所计划的一种排序算法，它是选择排序的一种。它是通过堆来进行选择数据。需要注意的是排升序要建大堆，排降序建小堆

1. // 初始序列：21,25,49, 25*,16,08

复制代码

那么初始聚集如下

调解为最大堆（或根据需求调解为最小堆）

排序过程

堆排序特性总结：

• 使用堆来选数，效率高很多
  
• 时间复杂度：O(N*logN)
  
• 空间复杂度：O(1)
  
• 稳定性：不稳定
  

示例代码

1. // 堆排序
2. void AdjustDwon(int* a, int n, int root) {
3.         int parent = root;
4.         int child = parent * 2 + 1;
5.         while (child < n) {
6.                 if (child + 1 < n && a[child + 1] > a[child]) {
7.                         ++child;
8.                 }
9.                 if (a[child] > a[parent]) {
10.                         int temp = a[child];
11.                         a[child] = a[parent];
12.                         a[parent] = temp;
13.                         parent = child;
14.                         child = parent * 2 + 1;
15.                 }
16.                 else { break; }
17.         }
18. }
19. void HeapSort(int* a, int n) {
20.         for (int i = n / 2 - 1; i >= 0; i--) {
21.                 AdjustDwon(a, n, i);
22.         }
23.         for (int i = n - 1; i >= 0; i--) {
24.                 int temp = a[0];
25.                 a[0] = a[i];
26.                 a[i] = temp;
27.                 AdjustDwon(a, i, 0);
28.         }
29. }

复制代码

2.3 互换排序

冒泡排序

根据序列中两个记录键值的比力结果来对换这两个记录在序列中的位置，逐个向后走（或者向前），把较大的放背面（或者放前面）

冒泡特性总结：

• 时间复杂度：O(N^2)
  
• 空间复杂度：O(1)
  
• 稳定性：稳定
  

示例代码

1. // 冒泡排序
2. void BubbleSort(int* a, int n) {
3.         for (int i = 0; i < n; i++) {
4.                 for (int j = 0; j < n - i - 1; j++) {
5.                         if (a[j] > a[j + 1]) {
6.                                 int temp = a[j];
7.                                 a[j] = a[j + 1];
8.                                 a[j + 1] = temp;
9.                         }
10.                 }
11.         }
12. }

复制代码

快速排序(很重要！！！)

快排在面试中常常可能会让你手撕，而且变化也不少！务必认识认识再认识
1. 快排根本知识

快速排序是Hoare于1962年提出的一种二叉树布局的互换排序方法，其根本头脑为：任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序聚集分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止

1. // 假设按照升序对array数组中[left, right)区间中的元素进行排序
2. void QuickSort(int array[], int left, int right)
3. {
4.      if(right - left <= 1)
5.          return;
6.      // 按照基准值对array数组的 [left, right)区间中的元素进行划分
7.     int div = partion(array, left, right);
8.    
9.      // 划分成功后以div为边界形成了左右两部分 [left, div) 和 [div+1, right)
10.     // 递归排[left, div)
11.      QuickSort(array, left, div);
12.    
13.     // 递归排[div+1, right)
14.      QuickSort(array, div+1, right);
15. }

复制代码

上述为快速排序递归实现的主框架，与二叉树前序遍历规则非常像，在写递归框架时可想想二叉树前序遍历规则即可快速写出来，后序只需分析如何按照基准值来对区间中数据进行划分的方式即可
将区间按照基准值划分为左右两半部门的常见方式有：

• hoare版本
  
  
  
  示例代码：
  
  1. // 快速排序hoare版本
  2. int PartSort1(int* a, int left, int right) {
  3.         int key = left;
  4.         while (right - left > 1)
  5.         {
  6.                 while (right - left > 1 && a[right - 1] >= a[key]) { right--; }
  7.                 while (right - left > 1 && a[left] <= a[key]) { left++; }
  8.                 int temp = a[left];
  9.                 a[left] = a[right - 1];
  10.                 a[right - 1] = temp;
  11.         }
  12.         int temp = a[key];
  13.         a[key] = a[left];
  14.         a[left] = temp;
  15.         return left;
  16. }

  复制代码
  霍尔版本效率不差，但是容易引发几个疑问：
  
  
  
  • 为什么能保证相遇时的值肯定比基准值小呢？
    
  • 为什么要先让右边出发，再让左边出发呢？
    
  • 如果右边或者左边不停到碰到另一方都没找到符合的值怎么办？
    
  这些疑问经过推演是可以解决的，但这使得霍尔版本有了肯定的明白门槛，于是就有了如下的挖坑法
  
  
• 挖坑法
  
  
  
  挖坑法的效率和霍尔版本是一样的，但相对来说更容易明白
  示例代码
  
  1. // 快速排序挖坑法
  2. int PartSort2(int* a, int left, int right) {
  3.         int key = a[left], flag = 1;
  4.         while (right - left > 1)
  5.         {
  6.                 if (flag) {
  7.                         if (a[right - 1] >= key) { right--; }
  8.                         else {
  9.                                 a[left] = a[right - 1];
  10.                                 flag = 0;
  11.                         }
  12.                 }
  13.                 else {
  14.                         if (a[left] <= key) { left++; }
  15.                         else {
  16.                                 a[right - 1] = a[left];
  17.                                 flag = 1;
  18.                         }
  19.                 }
  20.         }
  21.         a[left] = key;
  22.         return left;
  23. }

  复制代码
• 前后指针版
  
  
  
  这是与前两者不太一样的方法，还蛮新颖的，学校都没教
  示例代码
  
  1. // 快速排序前后指针法
  2. int PartSort3(int* a, int left, int right) {
  3.         int pre = left, cur = left + 1, key = left;
  4.         while (cur < right)
  5.         {
  6.                 if (a[cur] < a[key]) {
  7.                         pre++;
  8.                         int temp = a[pre];
  9.                         a[pre] = a[cur];
  10.                         a[cur] = temp;
  11.                 }
  12.                 cur++;
  13.         }
  14.         int temp = a[key];
  15.         a[key] = a[pre];
  16.         a[pre] = temp;
  17.         return pre;
  18. }

  复制代码

2. 快排优化

快排相对来说效率还是不错的，因为在理想状态下，每次找到的基准值都恰好是中位数，分开来的左右序列长度是差不多的，看起来就和二叉树一样，如此效率就险些能和堆排序媲美

但是，一旦碰到不理想的环境，效率就差很多了
试想，如果每次取到的基准值都是最小/最大的，那么下一组的序列长度和原来相比只小了一个单元，那么参考上图，树的高度可以达到n，复杂度将变为O(n^2)
更重要的是，作为递归调用的函数，对空间的斲丧是很高的，而快排通常运用的场景绝对都是大要量的数据，这样一来，就很容易发生诸如栈溢出的环境，这是我们所不希望看到的
那么想要优化快排，以下是比力常见的方法

• 三数取中法选key
  我们固然希望克制选到的key过大或者过小，毕竟这样总会使效率有所下降，其中之一的办法，就是取3个数，第一个，最后一个，以及中间一个，取这三个数的中间值作为key值，至少能某种程度上减小上述环境发生的概率
  固然为了较少地改动之前已写过的代码，选到的key值可以和第一个值做个互换，然后再实行之前的代码即可
  
• 递归到小的子区间时，可以考虑使用插入排序
  在数据量较小时，再使用快排，和其他排序算法（好比插入排序）相比，就没什么优势了，使用非递归的其他算法可以减少一些栈帧的开销
  
• 使用非递归方法
  单独列一个，看下方
  

3. 非递归实现快排

我们知道，函数调用时所需要的空间是由栈分配的（至少在大多数编程语言中如此）在递归的函数中，每递归一次，就会多创建一个栈帧，占用栈的一部门空间
那么我们可以考虑用数据布局——栈（注意这和上面的栈不是同一个概念！！！）来模拟实现递归的调用过程，比方说在栈中存放每组的开头和结尾，直到栈空之前循环实行，这同样能完成任务，但利益在于：

• 不会再过多的创建栈帧，降低栈溢出的风险（这里指的是调用栈或实行栈，与数据布局的栈差别！）
  
• 使用的数据布局——栈，占用的空间是动态申请的，而动态申请的空间是由堆分配的，不会占用栈的空间
  
• 堆的空间是比栈的空间大得多的，所以总体来说，空间调用的安全性更高了
  

参考代码如下

1. // 快速排序 非递归实现
2. void QuickSortNonR(int* a, int left, int right) {
3.         stack<int>stk;
4.         stk.push(left);
5.         stk.push(right);
6.         while (!stk.empty())
7.         {
8.                 right = stk.top();
9.                 stk.pop();
10.                 left = stk.top();
11.                 stk.pop();
12.                 if (right - left <= 1) { continue; }
13.                 int temp = PartSort1(a, left, right);
14.                 stk.push(left);
15.                 stk.push(temp);
16.                 stk.push(temp + 1);
17.                 stk.push(right);
18.         }
19. }

复制代码

固然既然想到了用数据布局的栈来实现非递归，就不可克制的想到能不能用队列
这固然是可以的，不外，差别组的实行顺序会有所差别，我们可以看下对比图

• 用栈实现非递归
  
  
  
  
• 用队列实现非递归
  
  
  
  

之前说过，快速排序递归实现的主框架，与二叉树前序遍历规则非常像，用栈实现的非递归也是如此，而相应的，用队列实现非递归则和层序遍历很相似，事实上，我们实现层序遍历就是利用了队列
再广义一点的说，实在树的前中后序遍历，实在都是深度优先遍历，而层序遍历，则是广度优先遍历
可以实验下树的前中后序能否用非递归来写
快排特性总结：

• 快速排序整体的综合性能和使用场景都是比力好的，所以才敢叫快速排序
  
• 时间复杂度：O(N*logN)
  
• 空间复杂度：O(logN)
  
• 稳定性：不稳定
  

2.4 归并排序

根本头脑：
归并排序（MERGE-SORT）是创建在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide andConquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。
核心步调

归并排序相应的，类似树的后序遍历
参考代码

1. // 归并排序递归实现
2. void _MergeSort(int* a, int* temp, int bg, int ed) {
3.         if (bg == ed) { return; }
4.        
5.         int mid = (bg + ed) / 2;
6.         _MergeSort(a, temp, bg, mid);
7.         _MergeSort(a, temp, mid + 1, ed);
8.        
9.         int i = bg;
10.         int bg1 = bg, ed1 = mid, bg2 = mid + 1, ed2 = ed;
11.         while (bg1 <= ed1 && bg2 <= ed2)
12.         {
13.                 if (a[bg1] < a[bg2]) {
14.                         temp[i++] = a[bg1++];
15.                 }
16.                 else {
17.                         temp[i++] = a[bg2++];
18.                 }
19.         }
21.         while (bg1 <= ed1)
22.         {
23.                 temp[i++] = a[bg1++];
24.         }
25.         while (bg2 <= ed2)
26.         {
27.                 temp[i++] = a[bg2++];
28.         }
30.         for (int j = bg; j <= ed; j++) {
31.                 a[j] = temp[j];
32.         }
33. }
34. void MergeSort(int* a, int n) {
35.         int* temp = new int[n];
36.         _MergeSort(a, temp, 0, n - 1);
37.         delete[]temp;
38.         temp = NULL;
39. }

复制代码

非递归实现归并
根据之前非递归实现快排的履历，我们可能会先想到使用栈，但实际上，由于归并和后序的相似性，对栈的空间占用就会很高（实验自己推演看）实际上，使用循环迭代的方式也可以实现
使用一个迭代变量gap，表现两组归并的长度，每一轮gap*2
在每一轮中，从左往右循环归并差别组
需要注意一下的就是越界问题
示例代码

1. void MergeSortNonR(int* a, int n) {
2.         int* temp = new int[n];
3.         int gap = 1;
4.         while (gap < n)
5.         {
6.                 for (int i = 0; i < n; i += 2 * gap) {
7.                         int bg1 = i, ed1 = i + gap - 1;
8.                         int bg2 = i + gap, ed2 = i + 2 * gap - 1;
9.                         if (bg2 >= n) { break; }
10.                         if (ed2 >= n) { ed2 = n - 1; }
11.                         int j = i;
12.                         while (bg1 <= ed1 && bg2 <= ed2)
13.                         {
14.                                 if (a[bg1] < a[bg2]) {
15.                                         temp[j++] = a[bg1++];
16.                                 }
17.                                 else {
18.                                         temp[j++] = a[bg2++];
19.                                 }
20.                         }
22.                         while (bg1 <= ed1)
23.                         {
24.                                 temp[j++] = a[bg1++];
25.                         }
26.                         while (bg2 <= ed2)
27.                         {
28.                                 temp[j++] = a[bg2++];
29.                         }
31.                         for (int k = i; k <= ed2; k++) {
32.                                 a[k] = temp[k];
33.                         }
34.                 }
35.                 gap *= 2;
36.         }
37.         delete[]temp;
38.         temp = NULL;
39. }

复制代码

归并排序特性总结

• 归并的缺点在于需要O(N)的空间复杂度，归并排序的思考更多的是解决在磁盘中的外排序问题（既可以做内排序，也可以做外排序）
  
• 时间复杂度：O(N*logN)
  
• 空间复杂度：O(N)
  
• 稳定性：稳定
  

2.5 非比力排序

常见的非比力排序有：基数排序、计数排序、桶排序，其中计数排序比力有实践意义，这里先介绍计数排序
头脑：计数排序又称为鸽巢原理，是对哈希直接定址法的变形应用。
操作步调：

• 统计雷同元素出现次数
  
• 根据统计的结果将序列采取到原来的序列中
  

计数排序特性总结

• 计数排序在数据范围会合时，效率很高，但是适用范围及场景有限（一样寻常是整数）
  
• 时间复杂度：O(MAX(N,范围))
  
• 空间复杂度：O(范围)
  
• 稳定性：稳定
  

基数排序和桶排序，看如下介绍
基数排序
基数排序是一种线性时间复杂度的排序算法，它通过依次对每一位进行排序来处置惩罚整数或字符串。这个“位”可以是指数字中的个位、十位、百位等，或者是字符串中的字符位置。基数排序通常使用计数排序或桶排序作为子步伐来对每一位进行排序。它可以按照从最低有效位到最高有效位或者从最高有效位到最低有效位的方式进行排序。
优点：对于固定长度的关键字序列，基数排序可以在 O(nk) 时间内完成排序，其中 n 是关键字的数目，k 是关键字的最大长度。
缺点：基数排序依靠于数据范例，适用于整数或字符串等离散且有固定长度的数据布局。
桶排序
桶排序是将数组分到有限数目标桶里，每个桶再单独排序（有可能再使用别的排序算法或是以递归方式继承使用桶排序）。桶排序假设输入是由一个随机过程天生的，而且均匀分布在区间 [0, 1) 上。当输入数据能够均匀分配到各个桶中时，桶排序的结果最佳。
优点：如果输入数据能均匀地分布到各个桶中，那么桶排序的时间复杂度可以达到 O(n + k)，这里 n 是元素数目，k 是桶的数目。
缺点：桶排序的性能很大程度上取决于输入数据的分布环境。如果数据不是均匀分布的，某些桶可能会包罗过多的元素，导致效率降低。

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。