数据布局初阶排序全解

目录

1>>排序前言
2>>插入排序
2.1>>直接插入排序
2.2>>希尔排序
3>>选择排序
3.1>>直接选择排序
3.2>>堆排序
4>>交换排序
4.1冒泡排序
4.2快速排序
5>>归并排序
6>>测试
test.c
sort.h
sort.c
7>>总结

---

1>>排序前言

        排序顾名思义，就是将一组乱序的数，按从大到小或者从小到大举行排列的操作。
常见的排序如下

可以看到排序也是有分类的，既然有分类，那么这边给出宝子们一个思考，在最后测试的时间给出答案，思考1：排序方法这么多，哪个最好呢？最差的有什么用呢？

那么废话不多说，今天的重点内容就是明白并写出一个个排序算法，现在直接上高速，带着宝子们攻破一个个排序算法！

这边给出各个排序算法的声明，会在对应内容举行解释，宝子们先有个印象即可~~
2>>插入排序

2.1>>直接插入排序

        直插排序类似生活中的扑克牌，每拿到一张新牌，就要插入到手中的有序扑克牌中。那靠这个思路就可以写出步骤：
1.设置新插入的牌tmp
2.比较之前的每一个牌，找到比tmp小的，将团体往后移动腾出空间
3.插入到这张牌后面
代码如下：

设置end为每次手中牌的末端，tmp为新插入的牌，循环end>=0进入循环,假如比较发现手中牌比插入牌大，那么将手中牌往后移动一位，若小，跳出循环，将这张牌后一张牌，也就是空出来的位置赋值tmp，也就是新插入的牌。
2.2>>希尔排序

        希尔排序相当于直接插入排序的最优化法，什么意思呢？就是通过预排序，将整个数组提拔到接近有序的状态，最后再用直插排序举行排序，如许会快许多，那怎么实现呢？就是通太过组，将每隔n/3+1个数两两分为一组，先实现一次预备排序，这里直接来看代码举行解释

 刚开始令gap等于n，只要gap大于1那么就进入循环，每次gap等于gap/3+1，每次都举行预排序，当gap为1时就是直接插入排序啦，代码也只需要更改直接插入排序里面为1的值即可。
3>>选择排序

3.1>>直接选择排序

思路：
1.定义begin和end代表开始与结束，每次循环begin++，end--直到begin>=end
2.找出数组内最大值和最小值
3.将最大值和end交换，最小值与begin交换
代码如下：

代码就是定义begin为0，end为末端值，然后循环遍历找最大值下标和最小值下标，在出循环的时间举行交换即可。
注意：当begin等于max的时间，此时交换相当于原地不动，因此需要让max等于min让它实现原地交换一次，在跟end互换。如 9  3  5   1begin为9，max也为9，end为1，min也为1，实现上面交换，1 3 5 9，max又跟end交换，9 3 5 1，以是需要克制这种环境。
3.2>>堆排序

1.要实现堆排序，首先得要是一个堆，那么第一个循环就要把堆建立，双亲结点向下调解头脑，从最后一个结点的双亲结点开始（最后一个结点是n-1)它的双亲结点是-1然后除2，依次向下调解，如许就是一个堆。
2.将这个棵树的每一个子树都想象成一个堆，然后：
3.从最后一个结点开始，到0为止，每次交换它的最后一个结点和第0个结点，然后向下调解，如许就可以或许从大/从小排序

4>>交换排序

4.1冒泡排序

需要十个数就用数组存储，那么两两相邻的相比不就是数组两个相邻元素的比较吗？以是利用j和j+1举行比较，这里要注意j要＜9，由于如许操作的就是0-8下标的值，j+1就不会越界，而且每次循环都将一个最大的放到最右边了，以是j<9-i，每次循环少循环一次。
到这里，基本框架已经完成，我们只需再完善一下：假如我们输入的十个数是9 0 1 2 3 4 5 6 7 8，那么会发现，纵然我们第一次循环就已经排序完成，但是循环还是举行了，那么此时我们就可以加入一个布尔值变量，在循环开始定义为1，假如对数值举行两两更换，那么布尔值就为0，若出来为1就跳出循环即可，这种操作广泛用于各种循环和一些满足条件跳出的代码，可以充分减少运行次数。

4.2快速排序

快速排序讲一种最经典的排序找基准值法——hoare法

 怎样实现快速排序呢？就要通过递归的头脑实现，每次找到一个基准值，使得左边的数都小于它，右边的数都大于它。
那么hoare方法就是设定基准值为0下标值，定义left和right，从右边往左找比基准值小的，从左往右找比基准值小的，然后举行交换，最后当left>right时，交换基准值和right，返回right就是基准值啦！
5>>归并排序

这个比较复杂，但是也还好，容我细说

以上素材来源网络，如有侵权告知删除。
借用一下，通过这张图片来明白，所谓归并，就是一个数组微分积分的过程，将一个无序数组，不断的拆解，拆成单个单个有序数组，实现两个有序数组的排序，这就是归并。
那么代码怎么实现呢？
首先，这是一个递归的过程，每次都举行二分，分成左右序列，

0-3为新无序数列，4-7为新无序数列，分到它为有序为止，也就是

单个的时间，本身就是一个有序的

比较10，6，谁小谁先放，然后依次放入新数组，此时需要一个新数组临时存排序后的值，然后赋值给原数组。来看代码吧

1. void _MergeSort(int* arr,int left, int right,int* tmp) {
2.         if (left >= right)
3.                 return;       
4.         int mid = left + (right - left) / 2;
6.         //分成左右序列
7.         _MergeSort(arr, left, mid, tmp);
8.         _MergeSort(arr, mid+1, right, tmp);
9.         //定义两个假有序数组
10.         int begin1 = left;
11.         int end1 = mid;
12.         int begin2 = mid + 1;
13.         int end2 = right;
14.         int index = begin1;
15.         //index表示第二个暂存数组的下标值
16.         while (begin1 <= end1 && begin2 <= end2) {
17.                 if (arr[begin1] > arr[begin2]) {
18.                         tmp[index++] = arr[begin2++];
19.                 }
20.                 else{
21.                         tmp[index++] = arr[begin1++];
22.                 }
23.         }
24.         while (begin1 <= end1) {
25.                 tmp[index++] = arr[begin1++];
26.         }
27.         while (begin2 <= end2) {
28.                 tmp[index++] = arr[begin2++];
29.         }
30.         //最后把暂存数组值放到原数组
31.         for (int i = left; i <= right; i++) {
32.                 arr[i] = tmp[i];
33.         }
34. }
35. void MergeSort(int* arr, int n) {
36.         int* tmp = (int*)malloc(sizeof(int) * n);
37.         _MergeSort(arr, 0, n - 1, tmp);
38.         free(tmp);
39. }

复制代码

希望我的讲解能帮助大家明白归并排序。
6>>测试

接下来测试每个排序的时间复杂度

这里能看到快排和归并是最快的，另有堆排序，这边没有导入它的代码，下来可以自己尝试噢，希尔其次，冒泡排序最次，那解决前面的疑问，为什么还要冒泡排序呢？由于它有教学意义，较为简单，更好明白。
test.c

1. #include"sort.h"
2. #include<stdio.h>
3. #include<time.h>
4. #include<stdlib.h>
5. void PrintArr(int* arr, int n)
6. {
7.         for (int i = 0; i < n; i++)
8.         {
9.                 printf("%d ", arr[i]);
10.         }
11.         printf("\n");
12. }
14. void test() {
15.         int a[] = { 5, 3, 9, 6, 2, 4, 7, 1, 8 };
16.         int n = sizeof(a) / sizeof(a[0]);
17.         printf("排序之前：");
18.         PrintArr(a, n);
19.         MergeSort(a, n);
20.         //quicksort(a, 0, n - 1);
21.         printf("排序之后：");
22.         PrintArr(a, n);
23. }                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                  
25. void TestOP()
26. {
27.         srand(time(0));
28.         const int N = 100000;
29.         int* a1 = (int*)malloc(sizeof(int) * N);
30.         int* a2 = (int*)malloc(sizeof(int) * N);
31.         int* a3 = (int*)malloc(sizeof(int) * N);
32.         //int* a4 = (int*)malloc(sizeof(int) * N);
33.         int* a5 = (int*)malloc(sizeof(int) * N);
34.         int* a6 = (int*)malloc(sizeof(int) * N);
35.         //int* a7 = (int*)malloc(sizeof(int) * N);
37.         for (int i = 0; i < N; ++i)
38.         {
39.                 a1[i] = rand();
40.                 a2[i] = a1[i];
41.                 a3[i] = a1[i];
42.                 //a4[i] = a1[i];
43.                 a5[i] = a1[i];
44.                 a6[i] = a1[i];
45.                 //a7[i] = a1[i];
46.         }
47.         int begin1 = clock();
48.         insertsort(a1, N);
49.         int end1 = clock();
51.         int begin2 = clock();
52.         shellsort(a2, N);
53.         int end2 = clock();
54.         int begin3 = clock();
55.         selectsort(a3, N);
56.         int end3 = clock();
57.         //int begin4 = clock();
58.         //HeapSort(a4, N);
59.         //int end4 = clock();
61.         int begin5 = clock();
62.         quicksort(a5, 0, N - 1);
63.         int end5 = clock();
64.         int begin6 = clock();
65.         MergeSort(a6, N);
66.         int end6 = clock();
67.         //int begin7 = clock();
68.         //BubbleSort(a7, N);
69.         //int end7 = clock();
70.         printf("InsertSort:%d\n", end1 - begin1);
71.         printf("ShellSort:%d\n", end2 - begin2);
72.         printf("SelectSort:%d\n", end3 - begin3);
73.         //printf("HeapSort:%d\n", end4 - begin4);
74.         printf("QuickSort:%d\n", end5 - begin5);
75.         printf("MergeSort:%d\n", end6 - begin6);
76.         //printf("BubbleSort:%d\n", end7 - begin7);
77.         //free(a1);
78.         //free(a2);
79.         //free(a3);
80.         //free(a4);
81.         //free(a5);
82.         //free(a6);
83.         //free(a7);
84. }
86. int main()
87. {
88.         //test();
89.         TestOP();
90.         return 0;
91. }

复制代码

sort.h

1. #pragma once
2. #include<stdio.h>
3. #include<stdlib.h>
4. #include<stdbool.h>
5. #include<assert.h>
6. #include<string.h>
7. #include"stack.h"
8. void insertsort(int* arr, int n);//直插排序
9. void shellsort(int* arr, int n);//希尔排序
11. void selectsort(int* arr, int n);//选择排序
12. void HeapSort(int* arr, int n);//堆排序
14. void BubbleSort(int* arr, int n);//冒泡排序
15. void quicksort(int* arr, int left, int right);//快排
16. void QuickSortNonR(int* arr, int left, int right);//非递归借栈快排
18. void MergeSort(int* arr, int n);//归并排序

复制代码

sort.c

1. #include"sort.h"#include"stack.h"void insertsort(int* arr, int n) {        for (int i = 0; i < n - 1; i++) {                int end = i;                int tmp = arr[end + 1];                while (end >= 0) {                        if (arr[end] > tmp) {                                arr[end + 1] = arr[end];                                end--;                        }                        else {                                break;                        }                }                arr[end + 1] = tmp;        }}void shellsort(int* arr, int n) {        int gap = n;        while (gap > 1) {                gap = gap / 3 + 1;                for (int i = 0; i < n - gap; i++) {                        int end = i;                        int tmp = arr[end + gap];                        while (end >= 0) {                                if (arr[end] > tmp) {                                        arr[end + gap] = arr[end];                                        end-=gap;                                }                                else {                                        break;                                }                        }                        arr[end + gap] = tmp;                }        }}void swap(int* x, int* y) {        int tmp = *x;        *x = *y;        *y = tmp;}void selectsort(int* arr, int n) {        int end = n - 1;        int begin = 0;        while(begin<end){                int min = begin;                int max = begin;                for (int i = begin + 1; i <=end; i++) {                        if (arr[i] < arr[min])                                min = i;                        if (arr[i] > arr[max])                                max = i;                }                if (begin == max)                        max = min;                swap(&arr[min], &arr[begin]);                swap(&arr[max], &arr[end]);                begin++;                end--;        }}// 你这个是什么方法hoare找基准值int _quicksort(int* arr, int left, int right) {        int keyi = left;        left++;        while (left <= right) {                while (left <= right && arr[right] > arr[keyi])                        right--;                while (left <= right && arr[left] < arr[keyi])                        left++;                if (left<=right)                        swap(&arr[left++], &arr[right--]);        }        swap(&arr[right], &arr[keyi]);        return right;}int _quicksort1(int* arr, int left, int right) {        //挖洞法        //hole等于初始值，right从右从右往左找小，left找大        int hole = left;        int key = arr[hole];        while (left < right) {                while (left<right && arr[right]>key) {                        right--;                }                arr[hole] = arr[right];                hole = right;                while (left<right && arr[left]<key) {                        left++;                }                arr[hole] = arr[left];                hole = left;        }        arr[hole] = key;        return hole;}int _quicksort2(int* arr, int left, int right) {        //前后指针        int prev = left;        int key = left;        int pcur = left + 1;        while (pcur <= right) {                if (arr[pcur] < arr[key]&& ++prev != pcur) {                        swap(&arr[pcur], &arr[prev]);                }                pcur++;        }        swap(&arr[prev], &arr[key]);        return prev;}void quicksort(int* arr, int left, int right) {        //找基准值        //right从右往左找比基准值小，left从左往右找比基准值大，找到实现交换，        // left>right交换right和基准值        if (left >= right)                return;        int keyi = _quicksort(arr,left,right);        quicksort(arr, left, keyi-1);        quicksort(arr, keyi+1, right);}void QuickSortNonR(int* arr, int left, int right) {        stack st;        stinit(&st);        stenter(&st, right);        stenter(&st, left);        while (!stackempty(&st)) {                int begin = stackTop(&st);                stackpop(&st);                int end = stackTop(&st);                stackpop(&st);                //双指针找基准值划分左右序列                int prev = begin;                int key = begin;                int pcur = begin + 1;                while (pcur <= end) {                        if (arr[pcur] < arr[key] && ++prev != pcur) {                                swap(&arr[pcur], &arr[prev]);                        }                        pcur++;                }                swap(&arr[prev], &arr[key]);                key = prev;                //基准值下标为key                //划分左序列（左子树）[begin,key-]和右序列[key+1,end]                if (key + 1 < end) {                        stenter(&st, end);                        stenter(&st, key+1);                }                if (key - 1 > begin) {                        stenter(&st, key-1);                        stenter(&st,begin);                }        }        struin(&st);}void _MergeSort(int* arr,int left, int right,int* tmp) {
2.         if (left >= right)
3.                 return;       
4.         int mid = left + (right - left) / 2;
6.         //分成左右序列
7.         _MergeSort(arr, left, mid, tmp);
8.         _MergeSort(arr, mid+1, right, tmp);
9.         //定义两个假有序数组
10.         int begin1 = left;
11.         int end1 = mid;
12.         int begin2 = mid + 1;
13.         int end2 = right;
14.         int index = begin1;
15.         //index表示第二个暂存数组的下标值
16.         while (begin1 <= end1 && begin2 <= end2) {
17.                 if (arr[begin1] > arr[begin2]) {
18.                         tmp[index++] = arr[begin2++];
19.                 }
20.                 else{
21.                         tmp[index++] = arr[begin1++];
22.                 }
23.         }
24.         while (begin1 <= end1) {
25.                 tmp[index++] = arr[begin1++];
26.         }
27.         while (begin2 <= end2) {
28.                 tmp[index++] = arr[begin2++];
29.         }
30.         //最后把暂存数组值放到原数组
31.         for (int i = left; i <= right; i++) {
32.                 arr[i] = tmp[i];
33.         }
34. }
35. void MergeSort(int* arr, int n) {
36.         int* tmp = (int*)malloc(sizeof(int) * n);
37.         _MergeSort(arr, 0, n - 1, tmp);
38.         free(tmp);
39. }

复制代码

7>>总结

        今天讲解了各种类型的排序算法，最常用的还是时间复杂度最小的堆排序、快排、归并排序，希望这篇文章对大家有用，假如有题目接待评论区一起探讨，谢谢宝子们的观看，等待与你下篇再见~~