目录
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>>总结
今天讲解了各种类型的排序算法，最常用的还是时间复杂度最小的堆排序、快排、归并排序，希望这篇文章对大家有用，如果有问题欢迎评论区一起探讨，谢谢宝子们的观看，期待与你下篇再见~~
标签：arr,初阶,end,int,数据结构,right,全解,排序,left From： https://blog.csdn.net/m0_69282950/article/details/143466155