DS几大常见排序讲解和实现(中)(14)

---

媒介

  承上启下，正文开始！

---

一、希尔排序( 缩小增量排序 )

  希尔排序是一种基于插入排序的算法，通过引入增量的概念来改进插入排序的性能
基本思想

  通过预排序使得无序靠近有序序列，大体流程:先选定一个整数gap，将待排序序列中全部记录分组，全部距离为gap记录分在同一组，并对每一组记录进行排序，重复上述分组和排序的工作(gap不绝缩小)，当gap到达1，此时记录已经靠近有序，末了整体进行插入排序，使得记录排好序
   gap为1的时候，实在就已经退化为直接插入排序
  实现思路

  gap就是增量，我们发现根据当前增量，数组被分为gap个子序列，这些子序列的元素在原数组中央隔着固定的增量。对每个子序列应用插入排序，因为gap一开始很大，末了才慢慢变回1，说明一开始如果升序且小数据在后面，能被很快的移动到前面，从而达到低落时间复杂度的目标，这也是我们优化的一种表现

   在合理设置增量的条件下，一个数组一共可以分裂成增量个子序列，且每个子序列上相邻元素之差为增量
   我们以上图为例子，5个子序列分别是：
   子序列1: 9，4
子序列2: 1，8
子序列3: 2，6
子序列4: 5，3
子序列5: 7，5
   然后对每个子序列进行独立的插入排序：
   子序列1排序后：4，9
子序列2排序后：1，8
子序列3排序后：2，6
子序列2排序后：3，5
子序列3排序后：5，7
   一趟排序之后的数组：
   4 1 2 3 5 9 8 6 5 7
   我们发现走了一轮希尔排序后，数组并不是完全有序，但是已经更靠近有序了，接着就可以减小增量了！
 但是怎样减小增量？一般有两种处置惩罚方式：
   gap /= 2，包管了无论gap初始值多少，末了都能变为1，完成直接插入排序
gap = gap / 3 + 1; 因为如果gap为2的时候，在/3就直接等于0了，没有完成直接插入排序
   所以单独一个子序列排序：

1. int gap;
2. int end;
3. int tmp = a[end + gap];
4. while (end >= 0)
5. {
6.         if (a[end] > tmp)
7.         {
8.                 a[end + gap] = a[end];
9.                 end-=gap;
10.         }
11.         else
12.     {
13.                 break;
14.     }
15. }
16. a[end + gap] = tmp;

复制代码

  与直接插入代码差别的是，这里对end所加减的均为gap
如若不理解，请绘图！！
   单趟排序实现：

1. //这里for循环的条件为 i < n-gap 防止数组越界
2. int gap;
4. for (int i = 0; i < n-gap; i += gap)
5. {
6.         int end = i;
7.         int tmp = a[end + gap];
8.         while (end >= 0)
9.         {
10.                 if (a[end] > tmp)
11.                 {
12.                         a[end + gap] = a[end];
13.                         end -= gap;
14.                 }
15.                 else
16.         {
17.                         break;
18.             }
19.     }
20.         a[end + gap] = tmp;
21. }

复制代码

 全部子序列排序：

1. //外层循环（for (int j = 0; j < gap; j++)）意在对每个以gap为间隔的分组进行遍历
2. int gap;
3. for (int j = 0; j < gap; j++)
4. {
5.         for (int i = j; i < n - gap; i += gap)
6.         {
7.                 int end = i;
8.                 int tmp = a[end + gap];
9.                 while (end >= 0)
10.                 {
11.                         if (a[end] > tmp)
12.                         {
13.                                 a[end + gap] = a[end];
14.                                 end -= gap;
15.                         }
16.                         else
17.             {
18.                                 break;
19.                     }
20.        }
21.                 a[end + gap] = tmp;
22.         }
23. }

复制代码

  上述代码的三层循环着实不太美观，于是我们换一种思路，不再排完一个子序列再排别的一个子序列，因为每个子序列之间不会产生交互，于是我们把 i += gap，改为i++，并且脱去最外层的循环

1. //这时候就变成了统一排完每个子序列的同一个位置的元素后，再排下一个位置的元素
2. //比如n为10，gap为5，那么有5个子序列，这里就是统一排完5个子序列的第二个元素后，完成循环跳出
3. for (int i = 0; i < n - gap; i++)
4. {
5.         int end = i;
6.         int tmp = a[end + gap];
7.         while (end >= 0)
8.         {
9.                 if (a[end] > tmp)
10.                 {
11.                         a[end + gap] = a[end];
12.                         end -= gap;
13.                 }
14.                 else
15.         {
16.                         break;
17.             }
18.     }
19.         a[end + gap] = tmp;
20. }       

复制代码

  那么我们还要思索这个gap应该怎样取值？
   首先，还是要有这个意识：
gap越大，大的值更快调到后面，小的值更快调到前面，越不靠近有序。
gap越小，大的值更慢调到后面，小的值更慢调到前面，越靠近有序。
当gap为1，就是直接插入排序。
    因此，gap的值应该不是固定的，应该随着n的值而变革，这里我建议先计划为n，进入循环后再 gap /= 2，循环条件为gap > 1

1. void ShellSort(int* arr, int n)
2. {
3.     // 预排序，接近有序
4.     // 直接插入排序，有序
5.     // 越大的数越快跳到后面，越小的数越快跳到前面
6.     int gap = n;
7.     while (gap > 1){
8.         gap /= 2;
9.         for (int i = 0 ; i < n - gap ; i++){ // 减少for循环的个数,每次对不同组进行预排序
10.             int end = i;
11.             int tmp = arr[end + gap];
13.             while (end >= 0){
14.                 if (arr[end] > tmp){
15.                     arr[end + gap] = arr[end];
16.                     end -= gap;
17.                 }
18.                 else {
19.                     break;
20.                 }
21.                 arr[end + gap]  = tmp;
22.             }
23.         }
24.     }
25. }

复制代码

时间空间复杂度分析

  希尔排序的时间复杂度并不固定，它依靠于所选择的间隔序列（增量序列）。直到本日，已经有多种差别的间隔序列被提出来，每种都有自己的性能特点
《数据结构(C语言版)》— 严蔚敏

《数据结构-用面相对象方法与C++描述》— 殷人昆

空间复杂度为O(1)，在原数组上操作，时间复杂度为O(N^1.25) 到 O(1.6* N^1.25)
总结

• 时间复杂度：O(N²) -> 很复杂，有多种大概
  
• 空间复杂度：O(1)
  
• 稳定性：不稳定
  
• 复杂性：简朴
  

二、选择排序

基本思想

  选择排序是一种简朴直观的比力排序算法。该算法的基本思想是在每一轮中选出当前未排序部分的最小（或最大）元素，然后将其放置到未排序序列的起始位置，这个过程一直重复直至整个数组被排序

实现思路

• 从数组的当前未排序部分选择最小（或最大）的一个元素
  
• 将这个最小（或最大）元素与未排序序列的第一个元素交换位置
  
• 然后从剩余未排序的元素中继续这个过程，将每一次找到的最小（或最大）元素放到未排序序列的开始
  
• 这个过程一直进行到整个数组的全部元素都被排为有序状态
  

  实在我们还可以再优化一下，既要找到最小，又要找到最大，然后一个跟头交换，一个跟尾交换，如许能有一个常数级别的优化

1. void Swap(int* p1, int* p2)
2. {
3.         int tmp = *p1;
4.         *p1 = *p2;
5.         *p2 = tmp;
6. }
7. void SelectSort(int a[], int n)
8. {
9.         int begin = 0;
10.         int end = n - 1;
11.         while (begin < end)
12.         {
13.                 int maxi = begin;//找最大值的下标
14.                 int mini = begin;//找最小值的下标
15.                 for (int i = begin + 1; i <= end; i++)
16.                 {
17.                         if (a[i] < a[mini])
18.                         {
19.                                 mini = i;
20.                         }
21.                         if (a[i] > a[maxi])
22.                         {
23.                                 maxi = i;
24.                         }
25.                 }
26.                 Swap(&a[begin], &a[mini]);
27.                 Swap(&a[end], &a[maxi]);
28.                 begin++;
29.                 end--;
30.         }
31. }

复制代码

  

• 首先初始化两个索引begin和end，分别代表当前未排序序列的开始和结束位置。
  
• 进入一个循环，条件是begin < end，确保在数组中还有未排序的元素。
  
• 遍历一遍序列，找到最大元素和最小元素的下标。
  
• 将最小元素与序列的始端交换，最大元素与序列的尾端交换。
  
• 更新begin与end
  

  但是我们要思索如许书写会不会有问题，事实上是有的：
   因为这里我们是首先进行最小元素与首位置更换，再进行最大元素与末端更换，如果我的最大元素就在首位置就会有问题
  

  本来找到了最大值和最小值的下标，头跟最小值交换位置，最大值被交换走了，但是最大值的下标还是没变，仍然指向头，所以要加个判断，如果最大值是begin的话，我们把最大值的下标改为最小值的下标

1. void Swap(int* p1, int* p2)
2. {
3.         int tmp = *p1;
4.         *p1 = *p2;
5.         *p2 = tmp;
6. }
7. void SelectSort(int a[], int n)
8. {
9.         int begin = 0;
10.         int end = n - 1;
11.         while (begin < end)
12.         {
13.                 int maxi = begin;//找最大值的下标
14.                 int mini = begin;//找最小值的下标
15.                 for (int i = begin + 1; i <= end; i++)
16.                 {
17.                         if (a[i] < a[mini])
18.                         {
19.                                 mini = i;
20.                         }
21.                         if (a[i] > a[maxi])
22.                         {
23.                                 maxi = i;
24.                         }
25.                 }
26.                 Swap(&a[begin], &a[mini]);
27.                 //最大值的位置跟最小值重合
28.                 //mini被换到maxi位置时  原本的最大值则是mini
29.                 if (maxi == begin)
30.                         maxi = mini;
31.                 Swap(&a[end], &a[maxi]);
33.                 begin++;
34.                 end--;
35.         }
36. }

复制代码

时间空间复杂度分析

  对于时间复杂度来说，最好、均匀、最坏情况下的时间复杂度都是 O(n^2)，因为不管数组的初始顺序怎样，选择排序都必要比力全部未排序的元向来找到最小（或最大）的元素，并执行这个过程 n-1 次（对于 n 个元素的数组），每次选择操作必要比力的次数从 n-1 次淘汰到 1 次
  对于空间复杂度来说，选择排序是一种原地排序算法，除了输入数组外，它只必要有限的几个变量（比如，用于存储最小元素下标的变量和循环计数器）。因此，它的空间复杂度为常数空间O(1)
总结

• 选择排序思索非常好理解，但是服从不是很好。现实中很少使用。
  
• 时间复杂度：O(N^2)
  
• 空间复杂度：O(1)
  
• 稳定性：不稳定
  
• 复杂性：简朴
  

三、堆排序

  直接参考前文就行：
堆排序的讲解

1. void AdjustDown(int* arr, int n, int parent)
2. {
3.     // 假设法先选出大的孩子
4.     int child = parent * 2 + 1;
5.     while (child < n) {
6.         if (child + 1 < n && arr[child] < arr[child + 1]){ // child + 1 < n是为了防止右孩子越界
7.             child += 1;
8.         }
9.         if (arr[child] > arr[parent]){
10.             Swap(&arr[child], &arr[parent]);
11.             parent = child;
12.             child = parent * 2 + 1;
13.         }
14.         else {
15.             break;
16.         }
17.     }
18. }
20. void HeapSort(int* arr, int n)
21. {
22.     // 要升序，建大堆
23.     for (int i = (n - 2) / 2 ; i >= 0 ; i--){
24.         AdjustDown(arr, n, i);
25.     }
27.     int end = n - 1;
28.     while (end > 0){
29.         Swap(&arr[0], &arr[end]);
30.         AdjustDown(arr, end, 0);
31.         end--;
32.     }
33. }

复制代码

• 堆排序使用堆来选数，服从就高了许多。
  
• 时间复杂度：O(N*logN)
  
• 空间复杂度：O(1)
  
• 稳定性：不稳定
  

四、冒泡排序

基本思想

  比力两个相邻的元素，当不满足某一条件时，发生相邻元素的交换，直到整个序列有序为止

   序列中两个相邻元素进行比力，当满足条件发生交换操作，导致最小或大元素放到后面位置，不绝重复该过程，直到有序
  实现思路

  我们的目标是直到有序就停下来，但是上面的逻辑是地毯式查找，对此我们必要设置一个标识变量去标识是否有序，如果不必要交换说明有序直接退出

1. #define _CRT_SECURE_NO_WARNINGS 1
2. #include <stdio.h>
3. int main()
4. {
5.         int arr[10] = { 0 };
6.         int sz = sizeof(arr) / sizeof(arr[0]);
7.         for (int i = 0; i < sz; i++)
8.         {
9.                 scanf("%d ", &arr[i]);///输入数据
10.         }
11.         int tap = 0;
12.         for (int i = 0; i < sz - 1; i++)
13.         {
14.         int flag=1;
15.                 for (int j = 0; j < sz - 1 - i; j++)
16.                 {
18.                         if (arr[j] > arr[j + 1])
19.                         {
20.                                 tap = arr[j];
21.                                 arr[j] = arr[j + 1];
22.                                 arr[j + 1] = tap;
23.                 flag=0;
24.                         }
25.                 }
26.         if(flag==1)
27.         {
28.           break;
29.         }
30.         }
31.         for (int i = 0; i < sz; i++)
32.         {
33.                 printf("%d ", arr[i]);//打印数据
34.         }
35.         return 0;
36. }

复制代码

总结

• 冒泡排序是一种非常容易理解的排序
  
• 时间复杂度: O (N2)
  
• 空间复杂度: O(1)
  
• 稳定性：稳定
  

五、归并排序

基本思想

  归并排序(MERGE-SORT)是创建在归并操作上的一种有效的排序算法，该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。将已有序的子序列归并，得到完全有序序列即先使每个子序列有序，再使子序列间有序。若加你个两个有序表归并成一个有序表，称为二路归并

实现思路

  实在你猜一下就知道这里肯定还要运用到递归~哈哈！
  归并排序重要是通过已有序的子序列归并，得到完全有序的序列。那么将已有序的左右子树得到完全有序的根序列，完成这项操作还必要借助一块空间完成归并，再使用内存函数复制或转移到原本序列中，所以先要排好左边和右边，实在是一种后序

1. void _MergeSort(int* arr, int left, int right, int* tmp)
2. {
3.     if (left >= right){
4.         return ;
5.     }
7.     int mid = (left + right) >> 1;
8.     _MergeSort(arr, left, mid, tmp);                 //排好了左边
9.     _MergeSort(arr, mid + 1, right, tmp);        //排好了右边
11.     // 归并
12.     int begin1 = left, end1 = mid;
13.     int begin2 = mid + 1, end2 = right;
14.     int index = left;
16.     while (begin1 <= end1 && begin2 <= end2){
17.         if (arr[begin1] < arr[begin2]){
18.             tmp[index++] = arr[begin1++];
19.         }
20.         else {
21.             tmp[index++] = arr[begin2++];
22.         }
23.     }
25.     while (begin1 <= end1){
26.         tmp[index++] = arr[begin1++];
27.     }
29.     while (begin2 <= end2){
30.         tmp[index++] = arr[begin2++];
31.     }
33.     // 拷贝回去，在回溯的过程中就要返回
34. //    for (int i = left ; i <= right ; i++){
35. //        arr[i] = tmp[i];
36. //    }
37.     memcpy(arr + left, tmp + left, sizeof(int)*(right - left + 1));
38. }
40. void MergeSort(int* arr, int n)
41. {
42.     int* tmp = (int*)malloc(sizeof(int)*n);
44.     _MergeSort(arr, 0, n - 1, tmp);
45.     free(tmp);
46. }

复制代码

总结

• 归并的缺点在于必要O(N)的空间复杂度，归并排序的思索更多的使解决在磁盘中的外排序问题。
  
• 时间复杂度: O(N*logN)
  
• 空间复杂度: O(N)
  
• 稳定性:稳定
  
• 没有进行交换，更加适合外排序
  

六、计数排序

基本思想

  计数排序又称为鸽巢原理，是对哈希直接定址法的变形应用

1. void CountSort(int* a, int n)
2. {
3.         int min = a[0], max = a[0];
4.         for (int i = 1; i < n; i++)
5.         {
6.                 if (a[i] < min)
7.                         min = a[i];
9.                 if (a[i] > max)
10.                         max = a[i];
11.         }
13.         int range = max - min + 1; // 节省空间，存储数据并不是从0开始，采用相对映射
14.         int* count = (int*)calloc(range, sizeof(int));
15.         if (count == NULL)
16.         {
17.                 printf("calloc fail\n");
18.                 return;
19.         }
21.         // 统计次数
22.         for (int i = 0; i < n; i++)
23.         {
24.                 count[a[i] - min]++;
25.         }
26.    
27.         // 排序
28.         int i = 0;
29.         for (int j = 0; j < range; j++)
30.         {
31.                 while (count[j]--)
32.                 {
33.                         a[i++] = j + min;//加回去
34.                 }
35.         }
36. }

复制代码

总结

• 计数排序在数据范围会合时，服从很高，但是适用范围及场景有限。
  
• 时间复杂度：O(MAX(N,范围))
  
• 空间复杂度：O(范围)
  

---

总结

  是不是被排序这一高深的学问给吓到了？哈哈，别急，下篇我会介绍一种最常用的排序算法，它有许多变式，也很美妙~

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