青岛模板自助建站,怎么做木马网站,企业网站的规划与设计,怎么优化网络目录 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排序前言
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为新插入的牌循环end0进入循环,如果比较发现手中牌比插入牌大那么将手中牌往后移动一位若小跳出循环将这张牌后一张牌也就是空出来的位置赋值tmp也就是新插入的牌。
2.2希尔排序 希尔排序相当于直接插入排序的最优化法什么意思呢就是通过预排序将整个数组提升到接近有序的状态最后再用直插排序进行排序这样会快很多那怎么实现呢就是通过分组将每隔n/31个数两两分为一组先实现一次预备排序这里直接来看代码进行解释 刚开始令gap等于n只要gap大于1那么就进入循环每次gap等于gap/31每次都进行预排序当gap为1时就是直接插入排序啦代码也只需要更改直接插入排序里面为1的值即可。
3选择排序
3.1直接选择排序
思路
1.定义begin和end代表开始与结束每次循环beginend--直到beginend
2.找出数组内最大值和最小值
3.将最大值和end交换最小值与begin交换
代码如下 代码就是定义begin为0end为末尾值然后循环遍历找最大值下标和最小值下标在出循环的时候进行交换即可。
注意当begin等于max的时候此时交换相当于原地不动因此需要让max等于min让它实现原地交换一次在跟end互换。如 9 3 5 1begin为9max也为9end为1min也为1实现上面交换1 3 5 9max又跟end交换9 3 5 1所以需要避免这种情况。
3.2堆排序
1.要实现堆排序首先得要是一个堆那么第一个循环就要把堆建立双亲结点向下调整思想从最后一个结点的双亲结点开始最后一个结点是n-1)它的双亲结点是-1然后除2依次向下调整这样就是一个堆。
2.将这个棵树的每一个子树都想象成一个堆然后
3.从最后一个结点开始到0为止每次交换它的最后一个结点和第0个结点然后向下调整这样就能够从大/从小排序 4交换排序
4.1冒泡排序
需要十个数就用数组存储那么两两相邻的相比不就是数组两个相邻元素的比较吗所以使用j和j1进行比较这里要注意j要9因为这样操作的就是0-8下标的值j1就不会越界并且每次循环都将一个最大的放到最右边了所以j9-i每次循环少循环一次。
到这里基本框架已经完成我们只需再完善一下如果我们输入的十个数是9 0 1 2 3 4 5 6 7 8那么会发现即使我们第一次循环就已经排序完成但是循环还是进行了那么此时我们就可以加入一个布尔值变量在循环开始定义为1如果对数值进行两两替换那么布尔值就为0若出来为1就跳出循环即可这种操作广泛用于各种循环和一些满足条件跳出的代码可以充分减少运行次数。 4.2快速排序
快速排序讲一种最经典的排序找基准值法——hoare法 如何实现快速排序呢就要通过递归的思想实现每次找到一个基准值使得左边的数都小于它右边的数都大于它。
那么hoare方法就是设定基准值为0下标值定义left和right从右边往左找比基准值小的从左往右找比基准值小的然后进行交换最后当leftright时交换基准值和right返回right就是基准值啦
5归并排序
这个比较复杂但是也还好容我细说 以上素材来源网络如有侵权告知删除。
借用一下通过这张图片来理解所谓归并就是一个数组微分积分的过程将一个无序数组不断的拆解拆成单个单个有序数组实现两个有序数组的排序这就是归并。
那么代码怎么实现呢
首先这是一个递归的过程每次都进行二分分成左右序列0-3为新无序数列4-7为新无序数列分到它为有序为止也就是
单个的时候本身就是一个有序的比较106谁小谁先放然后依次放入新数组此时需要一个新数组暂时存排序后的值然后赋值给原数组。来看代码吧
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, mid1, 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
#includesort.h
#includestdio.h
#includetime.h
#includestdlib.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
#includestdio.h
#includestdlib.h
#includestdbool.h
#includeassert.h
#includestring.h
#includestack.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
#includesort.h
#includestack.hvoid 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(beginend){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 (leftright)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 (leftright arr[right]key) {right--;}arr[hole] arr[right];hole right;while (leftright 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从左往右找比基准值大找到实现交换// leftright交换right和基准值if (left right)return;int keyi _quicksort(arr,left,right);quicksort(arr, left, keyi-1);quicksort(arr, keyi1, 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-]和右序列[key1,end]if (key 1 end) {stenter(st, end);stenter(st, key1);}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, mid1, 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总结 今天讲解了各种类型的排序算法最常用的还是时间复杂度最小的堆排序、快排、归并排序希望这篇文章对大家有用如果有问题欢迎评论区一起探讨谢谢宝子们的观看期待与你下篇再见~~
