数据结构初阶排序全解

目录

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，谁小谁先放，然后依次放入新数组，此时需要一个新数组暂时存排序后的值，然后赋值给原数组。来看代码吧

void _MergeSort(int* arr,int left, int right,int* tmp) {if (left >= right)return;	int mid = left + (right - left) / 2;//分成左右序列_MergeSort(arr, left, mid, tmp);_MergeSort(arr, mid+1, right, tmp);//定义两个假有序数组int begin1 = left;int end1 = mid;int begin2 = mid + 1;int end2 = right;int index = begin1;//index表示第二个暂存数组的下标值while (begin1 <= end1 && begin2 <= end2) {if (arr[begin1] > arr[begin2]) {tmp[index++] = arr[begin2++];}else{tmp[index++] = arr[begin1++];}}while (begin1 <= end1) {tmp[index++] = arr[begin1++];}while (begin2 <= end2) {tmp[index++] = arr[begin2++];}//最后把暂存数组值放到原数组for (int i = left; i <= right; i++) {arr[i] = tmp[i];}
}
void MergeSort(int* arr, int n) {int* tmp = (int*)malloc(sizeof(int) * n);_MergeSort(arr, 0, n - 1, tmp);free(tmp);
}

希望我的讲解能帮助大家理解归并排序。

6>>测试

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

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

test.c

#include"sort.h"
#include<stdio.h>
#include<time.h>
#include<stdlib.h>
void PrintArr(int* arr, int n)
{for (int i = 0; i < n; i++){printf("%d ", arr[i]);}printf("\n");
}void test() {int a[] = { 5, 3, 9, 6, 2, 4, 7, 1, 8 };int n = sizeof(a) / sizeof(a[0]);printf("排序之前：");PrintArr(a, n);MergeSort(a, n);//quicksort(a, 0, n - 1);printf("排序之后：");PrintArr(a, n);
}                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                  void TestOP()
{srand(time(0));const int N = 100000;int* a1 = (int*)malloc(sizeof(int) * N);int* a2 = (int*)malloc(sizeof(int) * N);int* a3 = (int*)malloc(sizeof(int) * N);//int* a4 = (int*)malloc(sizeof(int) * N);int* a5 = (int*)malloc(sizeof(int) * N);int* a6 = (int*)malloc(sizeof(int) * N);//int* a7 = (int*)malloc(sizeof(int) * N);for (int i = 0; i < N; ++i){a1[i] = rand();a2[i] = a1[i];a3[i] = a1[i];//a4[i] = a1[i];a5[i] = a1[i];a6[i] = a1[i];//a7[i] = a1[i];}int begin1 = clock();insertsort(a1, N);int end1 = clock();int begin2 = clock();shellsort(a2, N);int end2 = clock();int begin3 = clock();selectsort(a3, N);int end3 = clock();//int begin4 = clock();//HeapSort(a4, N);//int end4 = clock();int begin5 = clock();quicksort(a5, 0, N - 1);int end5 = clock();int begin6 = clock();MergeSort(a6, N);int end6 = clock();//int begin7 = clock();//BubbleSort(a7, N);//int end7 = clock();printf("InsertSort:%d\n", end1 - begin1);printf("ShellSort:%d\n", end2 - begin2);printf("SelectSort:%d\n", end3 - begin3);//printf("HeapSort:%d\n", end4 - begin4);printf("QuickSort:%d\n", end5 - begin5);printf("MergeSort:%d\n", end6 - begin6);//printf("BubbleSort:%d\n", end7 - begin7);//free(a1);//free(a2);//free(a3);//free(a4);//free(a5);//free(a6);//free(a7);
}int main()
{//test();TestOP();return 0;
}

sort.h

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<assert.h>
#include<string.h>
#include"stack.h"
void insertsort(int* arr, int n);//直插排序
void shellsort(int* arr, int n);//希尔排序void selectsort(int* arr, int n);//选择排序
void HeapSort(int* arr, int n);//堆排序void BubbleSort(int* arr, int n);//冒泡排序
void quicksort(int* arr, int left, int right);//快排
void QuickSortNonR(int* arr, int left, int right);//非递归借栈快排void MergeSort(int* arr, int n);//归并排序

sort.c

#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) {if (left >= right)return;	int mid = left + (right - left) / 2;//分成左右序列_MergeSort(arr, left, mid, tmp);_MergeSort(arr, mid+1, right, tmp);//定义两个假有序数组int begin1 = left;int end1 = mid;int begin2 = mid + 1;int end2 = right;int index = begin1;//index表示第二个暂存数组的下标值while (begin1 <= end1 && begin2 <= end2) {if (arr[begin1] > arr[begin2]) {tmp[index++] = arr[begin2++];}else{tmp[index++] = arr[begin1++];}}while (begin1 <= end1) {tmp[index++] = arr[begin1++];}while (begin2 <= end2) {tmp[index++] = arr[begin2++];}//最后把暂存数组值放到原数组for (int i = left; i <= right; i++) {arr[i] = tmp[i];}
}
void MergeSort(int* arr, int n) {int* tmp = (int*)malloc(sizeof(int) * n);_MergeSort(arr, 0, n - 1, tmp);free(tmp);
}

7>>总结

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