C语言数据结构与算法(排序)

大家好，欢迎来到“干货”小仓库！！

    很高兴在CSDN这个大家庭与大家相识，希望能在这里与大家共同进步，共同劳绩更好的自己！！无人扶我青云志，我自踏雪至山巅！！！
  

1.插入排序

1.1基本思想

   直接插入排序是一种简朴的插入排序法，其基本思想是：把待排序的记载按其关键码值的巨细逐个插入到一个已经排好序的有序序列中，直到所有的记载插入完为止，得到一个新的有序序列 。
  生存实例：我们玩扑克牌时，就用了插入排序思想。
                                  

1.2直接插入排序

   就是将一组已经有序的数组中插入一个新的数据，将其放在数组的精确位置，最终使数组变成有序。
  单趟图例：
                

代码实现及解析：
                        

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

复制代码

  特性总结：
  ① 元素聚集越靠近有序，直接插入排序算法的时间效率越高
  ② 时间复杂度：O(N^2)
  ③ 空间复杂度：O(1)，它是一种稳定的排序算法
  ④ 稳定性：稳定
  2.希尔排序

2.1基本思想

      希尔排序法又称缩小增量法。       基本思想：      ①将数据分组(分的组越多，每组数据越少)
  ②对每组中的数据排好序
  ③再对整体数据分组，比上次分的组数要少，然后再对每组举行排序，依次循坏举行。
  ④直到数据分成一组，数据就全部有序了。
  2.2实现

代码实现及图解：

1. //希尔排序
2. void ShellSort(int* a, int n)
3. {
4.   int gap = n;
5.   while (gap > 1)
6.   {
7.         gap = gap / 3 + 1;
8.         for (int i = 0; i < n - gap; i++)
9.         {
10.             int end = i;
11.                 int tmp = a[i + gap];
12.                 while (end >= 0)
13.                 {
14.                         if (a[end] > tmp)
15.                         {
16.                             a[end + gap] = a[end];
17.                                 end -= gap;
18.                         }
19.                         else
20.                                 break;
21.                         }
22.                         a[end + gap] = tmp;
23.                 }
24.         }
25. }

复制代码

  特性总结：
  ①希尔排序是对直接插入排序的优化。
  ② 当gap > 1时都是预排序，目的是让数组更靠近于有序。当gap == 1时，数组已经靠近有序的了，这样就 会很快。这样整体而言，可以达到优化的效果。我们实现后可以举行性能测试的对比。
  ③稳定性：不稳定。
  3.选择排序

3.1基本思想

   每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完 。
  3.2实现

   单趟原理：
  ①挑选出最大值和最小值
  ②将挑选出的最大值和最小值分别与末了一个数据和起始数据交换
  代码实现及图解：

1. //交换
2. void Swap(int* a, int* b)
3. {
4.   int tmp = *a;
5.   *a = *b;
6.   *b = tmp;
7. }
8. //选择排序
9. void SelectSort(int* a, int left, int right)
10. {
11.         while (left < right)
12.         {
13.                 int min=left, max=left;
14.                 for (int i = left+1; i <= right; i++)
15.                 {
16.                         if (a[i] < a[min])
17.                                 min=i;
18.                         if (a[i] > a[max])
19.                                 max=i;
20.                 }
21.                 Swap(&a[left], &a[min]);
22.                 if (max == left)
23.                         max = min;
24.                 Swap(&a[right], &a[max]);
25.                 ++left;
26.                 --right;
27.         }
28. }

复制代码

  特性总结：
  ①直接选择排序思考非常好理解，但是效率不是很好。实际中很少使用
  ②时间复杂度：O(N^2)
  ③ 空间复杂度：O(1)
  ④稳定性：不稳定
  4.堆排序

4.1基本思想

   堆排序(Heapsort)是指利用堆积树（堆）这种数据结构所计划的一种排序算法，它是选择排序的一种。它是通过堆来举行选择数据。须要留意的是排升序要建大堆，排降序建小堆。
  4.2实现

代码实现及解析：

1. //交换
2. void Swap(int* a, int* b)
3. {
4.         int tmp = *a;
5.         *a = *b;
6.         *b = tmp;
7. }
8. //向下调整
9. void AdjustDown(int* a, int n, int parent)
10. {
11.         int child = parent *2 + 1;
12.         while (child < n)
13.         {
14.                 if (child+1<n && a[child] < a[child + 1])
15.                         ++child;
17.                 if (a[child] > a[parent])
18.                 {
19.                         Swap(&a[child], &a[parent]);
20.                         parent = child;
21.                         child = parent * 2 + 1;
22.                 }
23.                 else
24.                         break;
25.         }
26. }
27. //堆排序
28. void HeapSort(int* a, int n)
29. {        //向下调整建堆
30.         for (int i = (n - 2) / 2; i >= 0; i--)
31.         {
32.                 AdjustDown(a, n, i);
33.         }
35.         int end = n - 1;
36.         while (end > 0)
37.         {
38.                 Swap(&a[0], &a[end]);
39.                 AdjustDown(a, end, 0);
40.                 --end;
41.         }
42. }

复制代码

  特性总结：
  ①堆排序使用堆来选数，效率就高了很多。(上一篇文章《C语言数据结构与算法(二叉树)》有讲TOPK问题)
  ②时间复杂度：O(N*logN)
  ③空间复杂度：O(1)
  ④稳定性：不稳定
  5.冒泡排序

5.1基本思想

   所谓交换，就是根据序列中两个记载键值的比力结果来对换这两个记载在序列中的位置，交换排序的特点是：将键值较大的记载向序列的尾部移动，键值较小的记载向序列的前部移动。
  5.2实现

代码实现及图解：

1. //交换
2. void Swap(int* a, int* b)
3. {
4.         int tmp = *a;
5.         *a = *b;
6.         *b = tmp;
7. }
9. //冒泡排序
10. void BubbleSort(int* a, int n)
11. {
12.         for (int j = 0; j < n; j++)
13.         {
14.                 for (int i = 1; i < n-j; i++)
15.                 {
16.                         if (a[i - 1] > a[i])
17.                                 Swap(&a[i], &a[i - 1]);
18.                 }
19.         }
20.        
21. }

复制代码

  特性总结：
  ①冒泡排序是一种非常轻易理解的排序
  ②时间复杂度：O(N^2)
  ③空间复杂度：O(1)
  ④稳定性：稳定
  6.快速排序

   基本思想：任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序聚集分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都分列在相应位置上为止。
  6.1hoare版本

   ①选出一个基准值，一样平常选最左边或者最右边的那个数据，也可以选中间的数据，然后交换到最左边或者最右边即可。
  ②左边做基准值，右边先开始移动，找到比基准值小就停下来，然后左边找比基准值大的。
  ③将左右两边找的值举行交换，然后继续移动右边，左边，直到左边大于或大于右边则停下来，将基准值和停下来的那个位置举行交换，到此单趟就完成了。
  ④利用递归继续实行上面步骤。
  代码解析图解：

1. //交换
2. void Swap(int* a, int* b)
3. {
4.    int tmp = *a;
5.    *a = *b;
6.    *b = tmp;
7. }
9. //horea版本
10. int  Part1(int* a, int left, int right)
11. {
12.    int keyi = left;
14.    while (left < right)
15.    {
16.          while (left < right && a[right] >= a[keyi])
17.                   --right;
19.          while (left < right && a[left] <= a[keyi])
20.                   ++left;
22.          Swap(&a[left], &a[right]);
23.         }
25.    Swap(&a[left], &a[keyi]);
26.    keyi = left;
27.    return keyi;
28. }
29. //快排
30. void QuickSort(int* a, int left, int right)
31. {
32.    if (left >= right)
33.            return;
34.    int keyi = Part1(a, left, right);
36.    QuickSort(a, left, keyi - 1);
38.    QuickSort(a, keyi + 1, right);
39. }

复制代码

6.2挖坑法

代码解析图解：

1. int  Part2(int* a, int left, int right)
2. {
3.    int key = a[left];
4.    int hole = left;
5.    while (left < right)
6.   {
7.         while (left < right && a[right] >= key)
8.             --right;
10.         a[hole] = a[right];
11.         hole = right;
13.         while (left < right && a[left] <= key)
14.                 ++left;
16.         a[hole] = a[left];
17.         hole = left;
18.   }
19. a[hole] = key;
20. return hole;
21. }
23. void QuickSort(int* a, int left, int right)
24. {
25.    if (left >= right)
26.                 return;
27.    int keyi = Part1(a, left, right);
29.    QuickSort(a, left, keyi - 1);
31.    QuickSort(a, keyi + 1, right);
32. }

复制代码

6.3前后指针法

代码解析图解：

1. //交换
2. void Swap(int* a, int* b)
3. {
4.         int tmp = *a;
5.         *a = *b;
6.         *b = tmp;
7. }
9. //前后指针法
10. int  Part3(int* a, int left, int right)
11. {
12.         int keyi = left;
13.         int prev = left;
14.         int cur = left+1;
15.         while (cur<=right)
16.         {
17.                 if (a[cur] >= a[keyi])
18.                         ++cur;
19.                 else
20.                 {
21.                         ++prev;
22.                         if (prev != cur)
23.                         {
24.                                 Swap(&a[prev], &a[cur]);
25.                                 ++cur;
26.                         }
27.                         else
28.                                 ++cur;
29.                 }
30.         }
31.         Swap(&a[keyi], &a[prev]);
32.         keyi = prev;
33.         return keyi;
34. }
35. void QuickSort(int* a, int left, int right)
36. {
37.         if (left >= right)
38.                 return;
40.         int keyi = Part1(a, left, right);
42.         QuickSort(a, left, keyi - 1);
44.         QuickSort(a, keyi + 1, right);
45. }

复制代码

6.4快速排序优化

   当上面的三种快速排序方法遇到靠近有序的数据的时间，效率会大大低沉，可做如下优化：
  ①三数取中(选基准值)。上面三种方法都可以加上三数取中进步代码效率。
  ②小区间优化(小区间用插入排序)。
  
代码解析及图解：

1. //三数取中
2. int GetMidNum(int* a, int left, int right)
3. {
4.         int mid = left + rand() % (right - left);
5.         /*int mid = (left + right) / 2;*/
6.         if (a[left] > a[right])
7.         {
8.                 if (a[mid] > a[left])
9.                         return left;
10.                 else if (a[mid] < a[right])
11.                         return right;
12.                 else
13.                         return mid;
14.         }
15.         else
16.         {
17.                 if (a[mid] > a[right])
18.                         return right;
19.                 else if (a[mid] < a[left])
20.                         return left;
21.                 else
22.                         return mid;
23.         }
24. }
25. //交换
26. void Swap(int* a, int* b)
27. {
28.         int tmp = *a;
29.         *a = *b;
30.         *b = tmp;
31. }
33. //前后指针法
34. int  Part3(int* a, int left, int right)
35. {
36.         int tmp = GetMidNum(a, left, right);
37.         if (tmp != left)
38.                 Swap(&a[tmp], &a[left]);
39.         int keyi = left;
40.         int prev = left;
41.         int cur = left+1;
42.         while (cur<=right)
43.         {
44.                 if (a[cur] >= a[keyi])
45.                         ++cur;
46.                 else
47.                 {
48.                         ++prev;
49.                         if (prev != cur)
50.                         {
51.                                 Swap(&a[prev], &a[cur]);
52.                                 ++cur;
53.                         }
54.                         else
55.                                 ++cur;
56.                 }
57.         }
58.         Swap(&a[keyi], &a[prev]);
59.         keyi = prev;
60.         return keyi;
61. }
62. //快排
63. void QuickSort(int* a, int left, int right)
64. {
65.         if (left >= right)
66.                 return;
68.         //小区间优化--小区间直接使用插入排序
69.         if ((right - left + 1) > 10)
70.         {
71.                 //int keyi = Part1(a, left, right);  //hoare版本
72.                 //int keyi = Part2(a, left, right);  //挖坑法
73.                 int keyi = Part3(a, left, right);    //前后指针法
75.                 //  [left,keyi-1] keyi [keyi+1,right]
76.                 QuickSort(a, left, keyi - 1);
77.                 QuickSort(a, keyi + 1, right);
79.         }
80.         else
81.         {
82.                 InsertSort(a + left, right - left + 1);//插入排序
83.         }
84. }

复制代码

6.5三路划分法

   结合了三数取中、小区间优化。
  特殊用途：用于解决大量数据类似的情况。
  原理：
  ①比基准值小的数据往左边放。
  ②和基准值相称的数据往中间放。
  ③比基准值大的数据往右边放。
  代码解析及图解：

1. void  QuickSortPart4(int* a, int left, int right)
2. {
3.         if (left >= right)
4.                 return;
5.         if ((right - left + 1) < 10)
6.         {
7.                 InsertSort(a + left, right - left + 1);//插入排序
8.         }
9.         else
10.         {
11.                 int begin = left;
12.                 int end = right;
13.                 int tmp = GetMidNum(a, left, right);
14.                 if (tmp != left)
15.                         Swap(&a[tmp], &a[left]);
16.                 int keyi = left;
17.                 int cur = left + 1;
18.                 while (cur <= right)
19.                 {
20.                         if (a[cur] < a[keyi])
21.                         {
22.                                 Swap(&a[cur], &a[keyi]);
23.                                 ++left;
24.                                 ++keyi;
25.                         }
26.                         else if (a[cur] > a[keyi])
27.                         {
28.                                 Swap(&a[cur], &a[right]);
29.                                 --right;
30.                         }
31.                         else
32.                                 ++cur;
33.                 }
35.                 QuickSortPart4(a, begin, left - 1);
36.                 QuickSortPart4(a, right + 1, end);
37.         }
38. }

复制代码

6.6总结

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

   递归的问题：
  ①效率。（影响不是很大）
  ②深度太深，会导致栈溢出。
  递归改非递归有两种方式:
  ①直接改成循环。类似斐波那契等情况。
  ②使用栈辅助改循环
    通过画出快排的递归展开图，可以看出，本质就是区间在不断的变革。
  代码解析：

2. void QuickSortNonR(int* a, int left, int right)
3. {
4.     //利用之前栈的实现接口函数
5.         Stack st;         
6.         StackInit(&st);
7.         StackPush(&st, right);
8.         StackPush(&st, left);
10.         while (!StackEmpty(&st))
11.         {
12.                 int begin = StackTop(&st);
13.                 StackPop(&st);
14.                 int end = StackTop(&st);
15.                 StackPop(&st);
17.                 int keyi = Part3(a, begin, end);//前后指针法
19.                 //[begin,keyi-1] keyi [keyi+1,end]
20.                 if (keyi + 1 < end)
21.                 {
22.                         StackPush(&st, end);
23.                         StackPush(&st, keyi + 1);
24.                 }
26.                 if (begin < keyi - 1)
27.                 {
28.                         StackPush(&st, keyi - 1);
29.                         StackPush(&st, begin);
30.                 }
31.         }
33.         StackDestroy(&st);
34. }

复制代码

8.归并排序

8.1基本思想

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

8.2实现

   ①归并排序先递归到区间只有一个数据的时间(分解)，才开始举行往回排序(合并)。
  ②在合并的时间，须要改变数据的位置，而且又不能对其他数据造成影响，故须要别的的一个数组，临时存储排好序的数据，然后拷贝回原数组。
  递归展开图：

1. void _MergeSort(int* a, int left, int right, int* tmp)
2. {
3.         if (left >= right)
4.                 return;
6.         int mid = (left + right) / 2;
7.         //[left,mid] [mid+1,right]
9.         _MergeSort(a, left, mid,tmp);
10.         _MergeSort(a, mid + 1, right, tmp);
12.         int begin1 = left; int end1 = mid;
13.         int begin2 = mid + 1; int end2 = right;
14.         int i = left;
15.         while (begin1 <= end1 && begin2 <= end2)
16.         {
17.                 if (a[begin1] <= a[begin2])
18.                 {
19.                         tmp[i++] = a[begin1++];
20.                 }
21.                 else
22.                         tmp[i++] = a[begin2++];
23.         }
24.         while (begin1 <= end1)
25.                 tmp[i++] = a[begin1++];
27.         while (begin2 <= end2)
28.                 tmp[i++] = a[begin2++];
30.         memcpy(a + left, tmp + left, sizeof(int) * (right - left + 1));
31. }
32. //归并排序
33. void MergeSort(int* a, int left, int right)
34. {
35.        
36.         int* tmp = (int*)malloc(sizeof(int) * (right - left + 1));
37.         if (tmp==NULL)
38.                 exit(2);
40.         _MergeSort(a, left, right, tmp);
42.         free(tmp);
43. }

复制代码

  归并排序的特性总结：
  1. 归并的缺点在于须要O(N)的空间复杂度，归并排序的思考更多的是解决在磁盘中的外排序问题。
  2. 时间复杂度：O(N*logN)
  3. 空间复杂度：O(N)
  4. 稳定性：稳定
  9.归并排序的非递归

   归并排序的递归，本质上就是在改变要排序的数据的个数，可以直接改成循环。
  图解：

1. //归并非递归
2. void MergeSortNonR(int* a, int n)
3. {
4.         int* tmp = (int*)malloc(sizeof(int) * (n));
5.         if (tmp == NULL)
6.                 exit(2);
7.         int gap = 1;
8.         while (gap < n)
9.         {
11.                 for (int i = 0; i < n; i += 2 * gap)
12.                 {
13.                         int begin1 = i; int end1 = i + gap - 1;
14.                         int begin2 = i + gap; int end2 = i + 2 * gap - 1;
16.                         if (end1 >= n || begin2 >= n)
17.                                 break;
18.                         else if (end2 >= n)
19.                                 end2 = n - 1;
21.                        
22.                         int j = i;
23.                         while (begin1 <= end1 && begin2 <= end2)
24.                         {
25.                                 if (a[begin1] <= a[begin2])
26.                                 {
27.                                         tmp[j++] = a[begin1++];
28.                                 }
29.                                 else
30.                                         tmp[j++] = a[begin2++];
31.                         }
32.                         while (begin1 <= end1)
33.                                 tmp[j++] = a[begin1++];
35.                         while (begin2 <= end2)
36.                                 tmp[j++] = a[begin2++];
38.             //归并一部分拷贝一部分(拷贝回原组)
39.                         memcpy(a+i, tmp+i, sizeof(int) * (end2-i+1));
41.                 }
42.                 gap *= 2;
43.         }
44. }

复制代码

10.计数排序

10.1基本思想

      ① 统计类似元素出现次数        ② 根据统计的结果将序列接纳到原来的    10.2实现

代码分析：

、

1. //计数排序
2. void CountSort(int* a, int n)
3. {
4.         int min = a[0];
5.         int max = a[0];
6.         for (int i = 1; i < n; i++)
7.         {
8.                 if (min > a[i])
9.                         min = a[i];
10.                 if (max < a[i])
11.                         max = a[i];
12.         }
14.         int range = max - min + 1;
15.         int* CountA = (int*)malloc(sizeof(int) * range);//计数数组
17.         if (CountA == NULL)
18.         {
19.                 perror("malloc fail\n");
20.                 exit(2);
21.         }
22.         memset(CountA, 0, sizeof(int) * range);
24.         for (int i = 0; i < n; i++)
25.         {
26.                 CountA[a[i] - min]++;
27.         }
29.         int j = 0;
30.         for (int i = 0; i < range; i++)
31.         {
32.                 while (CountA[i]--)
33.                 {
34.                         a[j++] = i + min;
35.                 }
36.         }
37.         free(CountA);//释放
38. }

复制代码

11.排序稳定性分析

      稳定性   ：假定在待排序的记载序列中，存在多个具有类似的关键字的记载，若经过排序，这些记载的相对序次保持稳定，即在原序列中，r=r[j]   ，且   r   在   r[j]   之前，而在排序后的序列中，   r   仍在   r[j]   之前，则称这种排序算法是稳定的；否则称为不稳定的。   (简朴来说就是排好序后，类似数据的相对位置保持稳定则是稳定的，否则不稳定)。      排序总结：   

      

---

  快乐的时光总是短暂，咱们下篇博客再见啦！！！觉得不错的，不要忘了给岑寂努力的自己点个赞和收藏咯，感谢支持,谢谢大家！！！


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