[数据布局] 万字分析排序算法

快速排序

快速排序（Quick Sort）是一种高效的排序算法，它利用分治法将一个数组分成两个子数组，然后递归地对这两个子数组举行排序。在快速排序的每一趟排序中，焦点步调是单趟循环，这一步调将数组分成两分，一部分的全部元素都小于即是一个特定的“基准值”（pivot），另一部分的全部元素都大于基准值。
双指针法

快速排序逻辑如下GIF：

由此可得，快速排序的单次逻辑代码实现为：

1. if (left >= right)
2.         {
3.                 return;
4.         }
6.         int keyi = left;
7.         int begin = left;
8.         int end = right;
10.         while (begin < end)
11.         {
12.                 // 左边找大
13.                 // a[end] >= a[keyi] 防止两个位置相同时一直交换，陷入无限循环
14.                 while (begin < end && a[end] >= a[keyi])
15.                 {
16.                         --end;
17.                 }
19.                 // 右边找小
20.                 while (begin < end && a[begin] <= a[keyi])
21.                 {
22.                         ++begin;
23.                 }
25.                 /*if (begin < end)
26.                 {
27.                         Swap(&a[begin], &a[end]);
28.                 }*/
30.                 Swap(&a[begin], &a[end]);
32.         }
34.         Swap(&a[keyi], &a[begin]);

复制代码

设置最左边为keyi，开始从左边向右找比keyi大的数据，从右边向左找比keyi小的数据，实行逻辑：右边先辈行向左查找小数据，找到后停顿在小数据位置，左边再向右查找大数据，找到后停顿。交换找到的两个位置的数据，继承循环查找然后交换。当两个指针指向位置类似时将相遇位置与keyi位置交换（此时的相遇位置肯定是比keyi小的数据）。
通太过治的头脑来举行分组排序。在单趟排序后keyi作为中心值换到了两个指针上一轮相遇位置，从keyi位置二分数组，将两个数组的最左边元素设置为keyi，继承举行循环，继承分治，云云末了即到达了团体次序的目的。
团体排序过程整理

选择基准值（Pivot）

快速排序的第一步是从数组中选择一个基准值（pivot）。基准值的选择可以有多种战略，比方选择第一个元素、末了一个元素、中心的元素，大概随机选择。基准值的选择会影响算法的性能，但不会影响其精确性。
单趟分别（Partitioning）

在单趟分别过程中，数组中的元素被重新排序，使得基准值左边的全部元素都小于即是基准值，右边的全部元素都大于即是基准值。这个过程可以形貌如下：
   

• 初始化指针：设定两个指针 begin 和 end，分别从数组的两端开始。
  
• 探求逆序对：从右向左移动 end 指针，直到找到一个小于基准值的元素；从左向右移动 begin 指针，直到找到一个大于基准值的元素。
  
• 交换元素：交换这两个指针指向的元素。
  
• 重复：重复上述过程，直到 begin 和 end 相遇。
  

  此时，基准值应插入到数组中心某个位置，使得其左边的元素全都小于即是它，右边的元素全都大于即是它。
递归分治（Divide and Conquer）

单趟分别完成后，基准值被放置到其终极位置，且数组被分为两部分。然后，对这两部分递归地举行快速排序：

• 对左部分排序：对基准值左边的子数组递归调用快速排序。
  
• 对右部分排序：对基准值右边的子数组递归调用快速排序。
  

递归的制止条件是子数组的巨细为零或一，即 left >= right。
制止条件

递归过程终极会将全部子数组排序完成，此时整个数组已经排序完成。
归并

快速排序本质上不必要显式的归并步调，由于在递归的每个步调中，基准值的左右子数组已经各自有序，整个数组的排序结果天然也就完成了。
团体代码实现

1. // 简朴快排void QuickSort(int* a, int left, int right){        if (left >= right)
2.         {
3.                 return;
4.         }
6.         int keyi = left;
7.         int begin = left;
8.         int end = right;
10.         while (begin < end)
11.         {
12.                 // 左边找大
13.                 // a[end] >= a[keyi] 防止两个位置相同时一直交换，陷入无限循环
14.                 while (begin < end && a[end] >= a[keyi])
15.                 {
16.                         --end;
17.                 }
19.                 // 右边找小
20.                 while (begin < end && a[begin] <= a[keyi])
21.                 {
22.                         ++begin;
23.                 }
25.                 /*if (begin < end)
26.                 {
27.                         Swap(&a[begin], &a[end]);
28.                 }*/
30.                 Swap(&a[begin], &a[end]);
32.         }
34.         Swap(&a[keyi], &a[begin]);
35.         // 现在的begin位置是之前的keyi位置的数据，以是更新        keyi = begin;        QuickSort(a, left, keyi - 1);        QuickSort(a, keyi + 1, right);}

复制代码

为什么相遇位置肯定是小值？

情况 1: 右指针j找到了小于key的元素

   

• 右指针j移动：从右向左移动，找到第一个小于key的元素，停下。
  
• 左指针i移动：接着，左指针i从左向右移动，找到第一个大于key的元素，停下。
  
  
  
  • 假如i < j，交换i和j指向的元素，然后继承移动两个指针。
    
  • 假如i >= j，制止移动，举行下一步操纵。
    
  
  

  在此情况下，当两个指针相遇（i == j）时，此位置的元素是末了一个j找到的小于key的值。由于j停在了小于key的元素上，而i在移动过程中没有再向右移动（由于i >= j），因此相遇位置的元素肯定小于即是key。
情况 2: 右指针j没有找到小于key的元素

   

• 右指针j移动：从右向左移动，直到与key相遇（即j移动到数组的开始位置）。
  
• 左指针i移动：假如j已经与key相遇，那么i也会在开始位置停下。
  

  在这种情况下，j没有找到任何小于key的元素，意味着全部元素都大于即是key。因此，当i和j相遇时，他们都在数组的起始位置，这时key本身与本身交换，整个数组大概是已经排序的大概全部元素都相当。
总结

   在快速排序的每一次循环中，无论哪种情况，当i和j相遇时，这个位置的元素都是小于即是key的。这是由于j指针的职责是找到小于key的元素，并在找到后停下。假如j在没有找到小于key的元素前就与i相遇，那么分析这部分元素都大于即是key，相遇点天然也是小于即是key（在情况2中，key与本身交换）。如许，基准元素key可以在每轮循环竣事时与相遇点的元素交换，确保key左边的元素不大于它，右边的元素不小于它，完成一次分区操纵。
  挖坑法

1. int Partition(int* arr, int low, int high) {
2.     int pivot = arr[low];  // 选择第一个元素作为基准值
3.     while (low < high) {
4.         while (low < high && arr[high] >= pivot) {
5.             high--;
6.         }
7.         arr[low] = arr[high];  // 用比基准小的记录替换低位记录
9.         while (low < high && arr[low] <= pivot) {
10.             low++;
11.         }
12.         arr[high] = arr[low];  // 用比基准大的记录替换高位记录
13.     }
14.     arr[low] = pivot;  // 基准值归位
15.     return low;  // 返回基准值的位置
16. }
18. void QuickSort(int* arr, int low, int high) {
19.     if (low < high) {
20.         int pivotPos = Partition(arr, low, high);  // 划分操作，将数组分为两部分
21.         QuickSort(arr, low, pivotPos - 1);  // 递归处理左子序列
22.         QuickSort(arr, pivotPos + 1, high);  // 递归处理右子序列
23.     }
24. }

复制代码

挖坑法的根本逻辑

   

• 选择基准值：从待排序数组中选择一个基准值，通常选择第一个元素作为基准值。
  
• 挖坑填数：通过一趟排序将待排序数组分割成独立的两部分，分别是比基准值小的元素和比基准值大的元素。这一过程中，利用挖坑的方式举行元素交换，即通过不绝移动元素，将基准值挖成一个坑，然后通过交换操纵，将小于基准值的元素填入这个坑中。
  
• 递归处置处罚：对左右两部分分别递归举行上述操纵，直到整个序列有序。
  

  为什么末了的坑位肯定是key这个中心值

在挖坑法中，末了的坑位置放置基准值（key）的过程包管了左侧的元素均小于即是基准值，右侧的元素均大于即是基准值。这是由于挖坑填数过程中，每次我们都是先从右侧开始查找小于基准值的元素，然后填入左侧的坑中，接着从左侧开始查找大于基准值的元素，填入右侧的坑中，直到左右指针相遇。
当左右指针相遇时，这个位置的元素肯定是小于即是基准值的，由于末了一次填坑操纵是从右侧填入左侧的坑，然后左右指针相遇。由于左指针在遇到右指针之前只移动到小于即是基准值的位置，以是末了的坑位置肯定是中心值，即小于即是基准值的元素。
因此，挖坑法包管了基准值放置在终极排序后的精确位置，同时确保了左右两侧的元素满意快速排序的要求，实现了快速排序的分别过程。
前后指针法

1. void QuickSort(int* a, int left, int right)
2. {
3.         if (left >= right)
4.                 return;
6.         int keyi = left;
8.         int prev = left;
9.         int cur = prev + 1;
10.         while (cur <= right)
11.         {
12.                 if (a[cur] < a[keyi] && ++prev != cur)
13.                         Swap(&a[prev], &a[cur]);
15.                 cur++;
16.         }
18.         Swap(&a[prev], &a[keyi]);
20.         keyi = prev;
22.         // [left, keyi-1] keyi [keyi+1, right]
23.         QuickSortt(a, left, keyi - 1);
24.         QuickSort(a, keyi + 1, right);
25. }

复制代码

前后指针法的根本逻辑

   

• 基准值选取：
  
  
  
  • 通过三数取中的方法选择基准值，将数组中的左端、右端和中心位置的元素举行比力，选取中心值作为基准值。
    
  • 将选取的基准值与数组中的第一个元素交换，以便后续比力。
    
  
  
• 前后指针交换：
  
  
  
  • 利用前后指针方法，前指针prev初始指向基准值，后指针cur初始指向基准值的下一个位置。
    
  • cur用来找比基准值小的值，cur作为比基准值大的数据前的分割指针。
    
  • 每次cur先走：
    
    
    
    • 当cur指向大于基准值时，prev先不走，cur继承向后走。
      
    • 当cur指向小于基准值时，prev向后走一次，并与cur交换位置（由于上一轮cur遇到大的会直接走，prev会停顿，以是prev + 1肯定是比基准值大的数据）。
      
    
    
  • 连续循环，当a[cur] < a[keyi]时，将cur指向的元素与prev后一个位置的元素交换，同时prev向后移动一位。
    
  • 继承移动cur指针，直到遍历完备个数组，cur指向数组末了一个数据后即循环竣事。
    
  
  
• 基准值归位：
  
  
  
  • 单趟循环竣过后，此时的prev指向的肯定是比基准值小的数值，以是将基准值a[keyi]与a[prev]交换，将基准值放置在精确的位置。
    
  
  
• 递归处置处罚：
  
  
  
  • 基准值被换到上一趟末了prev的位置，作为中心值，用基准值将数组分为左右两部分，分别为[left, keyi-1]和[keyi+1, right]，对这两部分分别举行递归快速排序。
    
  • 递归竣事条件是left >= right，即子数组只有一个元素或为空时竣事递归。
    
  
  

  递归优化：三数取中与小区间优化

三数取中 （Median of Three）

缘故起因

三数取中的缘故起因在于快速排序的性能与枢轴选择密切干系。假如选择的枢轴可以或许将数组匀称地分为两部分，递归的条理会镌汰，从而进步服从。而非常的枢轴选择会导致递归深度增长，进而导致性能降落。
   **非常情况：**假如排序的是一个有序的序列（left不停是当前分组最小值），每一次从右往左找小时都会到left，如许的话每一次分区间也是从最左侧开始，会造成递归深度过深，大概造成栈溢出。
  

优化点

在选择枢轴（pivot）时，利用三数取中方法，即选择数组的左端点、右端点和中点三个元素中的中心值作为枢轴。这一战略重要有以下优化点：
   

• 镌汰非常情况的概率： 传统的快速排序假如总是选择最左或最右的元素作为枢轴，当数组已经靠近有序时，大概导致最坏情况下的时间复杂度退化为 O(n2) O(n^2) O(n2)。三数取中镌汰了这种情况发生的概率，由于它克制了非常的最小或最大元素作为枢轴。
  
• 更匀称的分别： 通过选择中心值，三数取中方法倾向于产生更匀称的分别，进而镌汰递归深度，保持算法的时间复杂度在 O(nlog⁡n) O(n \log n) O(nlogn) 范围内。
  

1. int GetMidi(int* a, int left, int right)
2. {
3.         int midi = (left + right) / 2;
5.         if (a[left] < a[midi])
6.         {
7.                 if (a[midi] < a[right])
8.                 {
9.                         return midi;
10.                 }
11.                 else if (a[right] > a[left])
12.                 {
13.                         return right;
14.                 }
15.                 else
16.                 {
17.                         return left;
18.                 }
19.         }
20.         else // a[midi]< a[left]
21.         {
22.                 if (a[midi] > a[right])
23.                 {
24.                         return midi;
25.                 }
26.                 else if (a[left] < a[right])
27.                 {
28.                         return left;
29.                 }
30.                 else
31.                 {
32.                         return right;
33.                 }
34.         }
35. }

复制代码

优化后团体代码为：

1. void GetMidQuickSort(int* a, int left, int right)
2. {
3.         if (left >= right)
4.         {
5.                 return;
6.         }
8.         int midi = GetMidi(a, left, right);
9.         Swap(&a[left], &a[midi]);
11.         int keyi = left;
12.         int begin = left;
13.         int end = right;
15.         while (begin < end)
16.         {
17.                 // 左边找大
18.                 // a[end] >= a[keyi] 防止两个位置相同时一直交换，陷入无限循环
19.                 while (begin < end && a[end] >= a[keyi])
20.                 {
21.                         --end;
22.                 }
24.                 // 右边找小
25.                 while (begin < end && a[begin] <= a[keyi])
26.                 {
27.                         ++begin;
28.                 }
30.                 /*if (begin < end)
31.                 {
32.                         Swap(&a[begin], &a[end]);
33.                 }*/
35.                 Swap(&a[begin], &a[end]);
37.         }
39.         Swap(&a[keyi], &a[begin]);
41.         // 现在的begin位置是之前的keyi位置的数据，所以更新
42.         keyi = begin;
44.         QuickSort(a, left, keyi - 1);
45.         QuickSort(a, keyi + 1, right);
46. }

复制代码

小区间优化

缘故起因

小区间优化的缘故起因在于，固然快速排序均匀情况下是高效的，但在处置处罚非常小的数组时，插入排序的常数因子更低，且其性能大概优于快速排序。通过将小区间交给插入排序处置处罚，镌汰了快速排序的递归调用次数和开销，同时利用插入排序的低开销特性提拔了团体性能。
优化点

在处置处罚小区间（比方长度小于10的数组片断）时，快速排序利用插入排序代替继承递归。插入排序在小数组上每每更高效，这是由于：
   

• 镌汰递归开销： 递归的开销包罗函数调用、栈空间的利用等。当区间富足小时，这些开销大概比排序本身更耗时。插入排序的实现简朴，没有递归开销。
  
• 插入排序在小数据量时的服从： 插入排序对于小数据量的排序服从高于其他复杂的排序算法（如快速排序、归并排序等），特殊是在数据靠近有序的情况下。
  

1. // 当区间长度小于10时，使用插入排序处理
2. if ((right - left + 1) < 10)
3. {
4.     InsertSort(a + left, right - left + 1);
5.     return;
6. }

复制代码

优化后团体代码：

1. void InterCellGetMidQuickSort(int* a, int left, int right)
2. {
4.         if (left >= right)
5.         {
6.                 return;
7.         }
9.         // 小区间优化
10.         // right - left + 1为总个数：比如下标十个数的数组下标为  9 - 0，所以要 + 1
11.         if ((right - left + 1) < 10)
12.         {
13.                 // 加 left 为了在递归分区间后保持区间边界
14.                 InsertSort(a + left, right - left + 1);
15.         }
16.         else
17.         {
18.                 int keyi = left;
19.                 int begin = left;
20.                 int end = right;
22.                 while (begin < end)
23.                 {
24.                         // 左边找大
25.                         // a[end] >= a[keyi] 防止两个位置相同时一直交换，陷入无限循环
26.                         while (begin < end && a[end] >= a[keyi])
27.                         {
28.                                 --end;
29.                         }
31.                         // 右边找小
32.                         while (begin < end && a[begin] <= a[keyi])
33.                         {
34.                                 ++begin;
35.                         }
37.                         /*if (begin < end)
38.                         {
39.                                 Swap(&a[begin], &a[end]);
40.                         }*/
42.                         Swap(&a[begin], &a[end]);
44.                 }
46.                 Swap(&a[keyi], &a[begin]);
48.                 // 现在的begin位置是之前的keyi位置的数据，所以更新
49.                 keyi = begin;
51.                 InterCellGetMidQuickSort(a, left, keyi - 1);
52.                 InterCellGetMidQuickSort(a, keyi + 1, right);
53.         }
54. }

复制代码

递归快速排序的完备优化实当代码

1. void InterCellGetMidQuickSort(int* a, int left, int right)
2. {
4.         if (left >= right)
5.         {
6.                 return;
7.         }
9.         // 小区间优化
10.         // right - left + 1为总个数：比如下标十个数的数组下标为  9 - 0，所以要 + 1
11.         if ((right - left + 1) < 10)
12.         {
13.                 // 加 left 为了在递归分区间后保持区间边界
14.                 InsertSort(a + left, right - left + 1);
15.         }
16.         else
17.         {
18.                 // 三数取中
19.                 int midi = GetMidi(a, left, right);
20.                 Swap(&a[left], &a[midi]);
22.                 int keyi = left;
23.                 int begin = left;
24.                 int end = right;
26.                 while (begin < end)
27.                 {
28.                         // 左边找大
29.                         // a[end] >= a[keyi] 防止两个位置相同时一直交换，陷入无限循环
30.                         while (begin < end && a[end] >= a[keyi])
31.                         {
32.                                 --end;
33.                         }
35.                         // 右边找小
36.                         while (begin < end && a[begin] <= a[keyi])
37.                         {
38.                                 ++begin;
39.                         }
41.                         /*if (begin < end)
42.                         {
43.                                 Swap(&a[begin], &a[end]);
44.                         }*/
46.                         Swap(&a[begin], &a[end]);
48.                 }
50.                 Swap(&a[keyi], &a[begin]);
52.                 // 现在的begin位置是之前的keyi位置的数据，所以更新
53.                 keyi = begin;
55.                 InterCellGetMidQuickSort(a, left, keyi - 1);
56.                 InterCellGetMidQuickSort(a, keyi + 1, right);
57.         }
58. }

复制代码

非递归实现快速排序（栈、DFS）

非递归实现快速排序的焦颔首脑是利用栈来模仿递归调用的举动。通过显式地管理栈，可以克制体系栈溢出的题目，同时对栈的管理更加清楚明确。

1. void QuickSortNonR(int* a, int left, int right)
2. {
3.         stack<int> st;
4.         st.push(right);
5.         st.push(left);
7.         while (!st.empty())
8.         {
9.                 int begin = st.top();
10.                 st.pop();
11.                 int end = st.top();
12.                 st.pop();
14.         // 执行快排的单趟逻辑，不递归
15.                 int keyi = PartQuickSort(a, begin, end);
17.                 // 现将后面的区间入栈
18.                 // keyi + 1  :   end
19.                 if (keyi + 1 < end)
20.                 {
21.                         st.push(end);
22.                         st.push(keyi + 1);
23.                 }
25.                 if (keyi - 1 > begin)
26.                 {
27.                         st.push(keyi - 1);
28.                         st.push(begin);
29.                 }
30.         }
31. }

复制代码

代码过程明白

• 初始化阶段:
  

• 起首，将待排序数组的右边界 right 压入栈 st，然后将左边界 left 压入栈。此时，栈中的内容是 [right, left]。
  

• 第一轮循环:
  
  
  • 从栈中先弹出 begin（栈顶元素），然后弹出 end，代表当前必要处置处罚的子数组的左右边界。
    
  • 对 a[begin] 到 a[end] 这部分数组实行一次快速排序的分别操纵，找到枢轴的位置 keyi。
    
  • 根据 keyi 的位置，将右子数组（keyi + 1 到 end）的边界先后压入栈，再将左子数组（begin 到 keyi - 1）的边界先后压入栈。注意，每次先压入区间的右边界，再压入左边界，如许在后续出栈时可以或许先处置处罚左子数组。
    
  
  
• 第二轮循环及之后:
  
  
  • 从栈中再依次弹出 begin 和 end，处置处罚下一个子数组。
    
  • 实行一次分别操纵，确定新的枢轴位置 keyi。
    
  • 同样，根据 keyi 的位置，将新的子数组区间的边界按次序压入栈。
    
  
  
• 不绝重复:
  

• 反复从栈中弹出左右边界，举行子数组的分别和压栈操纵，直到栈为空。每次栈中压入的是还未排序的子数组边界，而从栈中弹出时则是准备举行排序操纵的边界。
  

• 竣事:
  

• 栈为空时，表现全部子数组均已被排序，整个数组也因此被完全排序。
  

   实行的黑白递归，但是逻辑还是递归的逻辑，还是用DFS举行遍历排序

1.          [0,9]
2.         /      \
3.      [0,4]       [5,9]
4.       /   \        /   \
5.    [0,2]  [3,4]  [5,6]   [7,9]
6.     / \      |     |  \   / \
7. [0,1] [2,2] [3,4] [5,5] [6,6] [7,8] [9,9]

复制代码

实例演示

假设初始数组为 [3, 1, 4, 1, 5, 9, 2, 6, 5, 3]，初始左右边界为 left = 0 和 right = 9。栈的初始状态是 [9, 0]。
   

• 第一轮:
  
  
  
  • 出栈：begin = 0, end = 9
    
  • 实行分别，假设 keyi = 5
    
  • 压入：[9, 6, 4, 0]
    
  
  
• 第二轮:
  
  
  
  • 出栈：begin = 0, end = 4
    
  • 实行分别，假设 keyi = 1
    
  • 压入：[9, 6, 4, 2]
    
  
  
• 第三轮:
  
  
  
  • 出栈：begin = 2, end = 4
    
  • 实行分别，假设 keyi = 3
    
  • 压入：[9, 6, 4, 4]
    
  
  
• 第四轮:
  
  
  
  • 出栈：begin = 6, end = 9
    
  • 实行分别，假设 keyi = 7
    
  • 压入：[9, 8, 6, 6]
    
  
  
• 第五轮:
  
  
  
  • 出栈：begin = 8, end = 9
    
  • 实行分别，假设 keyi = 9
    
  • 不再压入新的边界，由于子数组已经排序完成
    
  
  

  云云循环，直到栈为空。终极，整个数组被精确排序。
   这个过程通过栈布局有用地管理了必要排序的子数组区间，克制了递归带来的深度题目。每一轮循环中，都会先处置处罚左边子数组，这包管了遍历的次序和处置处罚的深度都受到控制。
  

归并排序

归并排序（Merge Sort）是一种基于分治法（Divide and Conquer）的排序算法，其焦颔首脑是将一个数组分成两个子数组，对每个子数组分别排序，然后将两个有序子数组归并成一个有序数组。归并排序具有稳固性和较好的时间复杂度，通常为 O(n log n)。

归并排序的原理

• 分治法头脑: 归并排序依照分治法的头脑，将题目分解为更小的子题目来办理，然后将子题目的结果归并，以得到最闭幕果。详细而言：
  
  
  
  • 分：将数组从中心分别为两个子数组，分别对这两个子数组举行排序。
    
  • 治：将两个已排序的子数组归并成一个有序数组。
    
  
  
• 递归过程: 归并排序通过递归实现，递归地将数组不绝分别，直到每个子数组的长度为1，此时子数组本身就是有序的。然后，归并这些有序的子数组。
  

归并排序过程分析

分别阶段（Divide）

从中心将数组分别成两个子数组，分别对两个子数组举行同样的操纵。这一步通过盘算中心位置 mid 来实现：

1. mid = (begin + end) / 2

复制代码

继承递归地对两个子数组举行同样的分别，直到每个子数组只包罗一个元素（即 begin >= end）。在这种情况下，数组本身已经是有序的。
归并阶段（Conquer）

当子数组被分别到只包罗一个元素时，开始将这些子数组两两归并。归并时，通过比力两个子数组的首元素，将较小的元素放入暂时数组（或直接放入原数组的得当位置），直到全部元素都被归并。
详细归并步调如下：
   

• 初始化两个指针分别指向两个子数组的起始位置。
  
• 比力两个指针指向的元素，将较小的元素拷贝到暂时数组，并移动相应的指针。
  
• 重复上述步调，直到一个子数组的全部元素都被拷贝到暂时数组。
  
• 将另一个子数组剩余的全部元素依次拷贝到暂时数组。
  

  递归回溯

随着递归函数的回溯，每次归并两个子数组，并在回溯竣事时，将暂时数组的内容复制回原数组对应的位置，使整个数组渐渐变为有序。
归并排序的特性

   

• 稳固性: 归并排序是一种稳固的排序算法，即类似元素的相对次序在排序后保持稳定。
  
• 时间复杂度: 归并排序在最坏、最好和均匀情况下的时间复杂度均为 O(n log n)。这是由于无论怎样分，数组总会分为 log n 层，而每层的归并过程必要 O(n) 的时间。
  
• 空间复杂度: 归并排序必要额外的空间来存储归并过程中的暂时数组，因此空间复杂度为 O(n)。
  

  归并排序的代码实现

代码

1. void _MergeSort(int* a, int* tmp, int begin, int end){        if (begin >= end)                return;        int mid = (begin + end) / 2
2. ;        // 假如[begin, mid][mid+1, end]有序就可以举行归并了        _MergeSort(a, tmp, begin, mid);        _MergeSort(a, tmp, mid + 1, end);        // 归并        int begin1 = begin, end1 = mid;        int begin2 = mid + 1, end2 = end;        int i = begin;        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++];        }        memcpy(a + begin, tmp + begin, (end - begin + 1) * sizeof(int));
3. }void MergeSort(int* a, int n){        int* tmp = (int*)malloc(sizeof(int) * n);        if (tmp == NULL)        {                perror("malloc fail");                return;        }        _MergeSort(a, tmp, 0, n - 1);        free(tmp);        tmp = NULL;}

复制代码

代码实现再分析

递归分别

制止条件: 当 begin 大于即是 end 时，子数组的元素个数小于或即是 1，此时无需再分割，直接返回。

1. if (begin >= end)
2.     return;

复制代码

分别数组: 将当前数组的范围 [begin, end] 分为两个子数组 [begin, mid] 和 [mid+1, end]，此中 mid 是中心位置。

1. int mid = (begin + end) / 2
2. ;

复制代码

递归排序子数组: 先对左子数组 [begin, mid] 举行排序，再对右子数组 [mid + 1, end] 举行排序。这里递归调用 _MergeSort，将题目不绝分解，直到满意制止条件。

1. _MergeSort(a, tmp, begin, mid);
2. _MergeSort(a, tmp, mid + 1, end);

复制代码

归并有序数组

在对两个子数组 [begin, mid] 和 [mid + 1, end] 排序后，它们分别是有序的。接下来将它们归并成一个有序的数组。
   初始化指针:
  

• begin1 和 end1 表现左子数组的范围。
  
• begin2 和 end2 表现右子数组的范围。
  
• i 用于指向暂时数组 tmp 中当前存放位置。
  

1. int begin1 = begin, end1 = mid;
2. int begin2 = mid + 1, end2 = end;
3. int i = begin;

复制代码

归并过程:
比力 a[begin1] 和 a[begin2] 的巨细，将较小的元素放入 tmp 中，并移动相应的指针。重复这一过程，直到某一子数组的元素全部放入 tmp 中。

1. while (begin1 <= end1 && begin2 <= end2)
2. {
3.     if (a[begin1] < a[begin2])
4.     {
5.         tmp[i++] = a[begin1++];
6.     }
7.     else
8.     {
9.         tmp[i++] = a[begin2++];
10.     }
11. }

复制代码

处置处罚剩余元素:
   

• 假如左子数组另有未放入 tmp 的元素，则将它们依次放入 tmp 中。
  
• 同样地，假如右子数组另有未放入 tmp 的元素，则将它们依次放入 tmp 中。
  

1. while (begin1 <= end1)
2. {
3.     tmp[i++] = a[begin1++];
4. }
6. while (begin2 <= end2)
7. {
8.     tmp[i++] = a[begin2++];
9. }

复制代码

将 **tmp** 中的元素拷贝回原数组:

• 在完成归并后，将 tmp 中的元素拷贝回原数组 a 中的对应位置，包管原数组 a 中的 [begin, end] 范围内的元素有序。
  

1. memcpy(a + begin, tmp + begin, (end - begin + 1) * sizeof(int));

复制代码

总结

归并排序通过递归地将数组分成更小的子数组，然后再归并这些有序子数组来完成排序。它的分治头脑和稳固性使其在处置处罚大规模数据时体现良好（ 特殊是对于链表排序或外部排序“数据存储在外部存储器中，如磁盘”的情况 ），但由于必要额外的存储空间（暂时数组 tmp），在空间服从上大概不如原地排序算法（如快速排序）。

计数排序

计数排序是一种 非比力排序算法，它差异于基于比力的排序算法（如快速排序、归并排序等），其时间复杂度受限于输入数据的最大值和最小值之间的范围，而不是数据本身的数量级。计数排序的焦颔首脑是 利用数组元素的值直接作为索引 来存储数据，从而克制了元素之间的比力。

代码实现

1. // 时间复杂度:O(N+range)
2. // 只适合整数/适合范围集中
3. // 空间范围度：O(range)
4. void CountSort(int* a, int n)
5. {
6.         int min = a[0], max = a[0];
7.         for (int i = 1; i < n; i++)
8.         {
9.                 if (a[i] < min)
10.                         min = a[i];
12.                 if (a[i] > max)
13.                         max = a[i];
14.         }
16.         int range = max - min + 1;
17.         //printf("%d\n", range);
19.         int* count = (int*)calloc(range, sizeof(int));
20.         if (count == NULL)
21.         {
22.                 perror("calloc fail");
23.                 return;
24.         }
26.         // 统计次数
27.         for (int i = 0; i < n; i++)
28.         {
29.                 count[a[i] - min]++;
30.         }
32.         // 排序
33.         int j = 0;
34.         for (int i = 0; i < range; i++)
35.         {
36.                 while (count[i]--)
37.                 {
38.                         a[j++] = i + min;
39.                 }
40.         }
42.         free(count);
43. }

复制代码

算法实现过程及原理

算法的步调包罗找出数组中的最大值和最小值，统计各个元素的频率，然后根据频率重新分列数组。
找到最小值和最大值

计数排序起首确定命组中元素的范围（即最大值和最小值之间的差）。这一步的目的是为了明确辅助数组（即计数数组）的巨细。假如范围过大，计数数组的巨细也会很大，导致空间浪费。因此，计数排序实用于数据范围相对会集的情况。
创建并初始化计数数组
计数数组 count 的巨细为 range = max - min + 1。数组的每个元素初始值为0，表现对应元素还未出现。
统计元素出现的次数

遍历待排序的数组 a，对于每个元素 a，在计数数组 count 中对应位置 count[a - min] 的值加1。这里的 a - min 盘算方式将数组的值映射到计数数组的索引范围 [0, range-1]。如许，计数数组的每个索引位置纪录了对应元素在数组中出现的次数。
盘算元素的累积计数

通过盘算计数数组的累积和来确定每个元素在排序后数组中的位置。累积计数实际上表现的是比当前元素值小的元素总个数加被骗前元素出现的次数，如许我们就能直接得到元素排序后在终极数组中的位置。
根据计数排序重构输出数组

根据累积计数反向遍历原数组，将每个元素放到输出数组的精确位置。必要注意的是，这一步必须从原数组的末端开始向前遍历，缘故起因是为了保持排序的稳固性（即类似元素在排序后的位置相对稳定）。
将排序结果拷贝回原数组

将排序好的元素从输出数组复制回原数组 a 中。
开释辅助空间

在算法竣事时，开释为计数数组分配的空间。这是为了防止内存走漏。
算法的时间和空间复杂度

• 时间复杂度：
  计数排序的时间复杂度为 O(n+range)O(n + \text{range})O(n+range)，此中 n 是待排序数组的元素数量，range 是元素的取值范围（即最大值与最小值之差加1）。这是由于计数排序在统计元素出现次数和重新分列元素时各遍历了两次数组 a 和 count。
  
• 空间复杂度：
  计数排序的空间复杂度为 O(range)O(\text{range})O(range)。重要是由于必要额外分配一个计数数组 count 来存储每个元素的出现次数，巨细为 range。
  

计数排序的范围性

• 数据范围题目：假如输入数据的范围 range 弘大于元素的数量 n，计数排序的空间复杂度将大大增长，以致超出实际的需求。这会导致内存的浪费。
  
• 实用场景：由于计数排序依赖于数据范围的巨细，它更实用于数据范围会集且分布较匀称的整数聚集。不适当范围特殊大大概小数的数据集。
  
• 稳固性：固然计数排序本身是稳固的，但这一点依赖于算法的详细实现方式，尤其是在重新分列元素时必须包管同值元素的相对次序稳定。