什么建设网站,贵阳网站建设方案报价,seo营销方法,网站开发属于无形资产吗本章代码gitee仓库#xff1a;排序 文章目录 #x1f383;0. 思维导图#x1f9e8;1. 插入排序✨1.1 直接插入排序✨1.2 希尔排序 #x1f38a;2. 选择排序#x1f38b;2.1 直接选择排序#x1f38b;2.2 堆排序 #x1f38f;3. 交换排序#x1f390;3.1 冒泡排序#… 本章代码gitee仓库排序 文章目录 0. 思维导图1. 插入排序✨1.1 直接插入排序✨1.2 希尔排序 2. 选择排序2.1 直接选择排序2.2 堆排序 3. 交换排序3.1 冒泡排序3.2 快速排序hoare版本挖坑法前后指针小区间优化非递归 4. 归并排序4.1 递归4.2 非递归 5. 性能测试5.1 1w数据5.2 10w数据5.3 100w数据5.4 1000w数据5.5 1亿数据 0. 思维导图 1. 插入排序 ✨1.1 直接插入排序
我们日常打扑克牌摸牌让后将牌按顺序插入好这其实就是插入排序的过程打小插入排序的思想就植入我们的脑海
第一张牌不用管直接拿在手里之后的牌按照大小再一个一个插入即可
//直接插入排序
void InsertSort(int* a, int n)
{//第一张牌不用排所以直接从下标1开始走for (int i 1; i n; i){int end i - 1;int tmp a[i];while (end 0){if (a[end] tmp){//往后挪数据a[end 1] a[end];end--;}elsebreak;}//直接break出来 或者 end -1a[end 1] tmp;}
}直接插入排序特性 越接近有序效率越高(不用那么多次挪动数据) 时间复杂度O(N2) 逆序最坏O(N2)有序最好O(N) 空间复杂度O(1) 稳定性稳定 ✨1.2 希尔排序
希尔排序是基于直接插入排序的一种优化将数据分为gap组对每组进行排序然后再缩小间隔知道gap为1的时候该序列为有序 //希尔排序
void ShellSort(int* a, int n)
{int gap n;while (gap 1){//最后一次gap一定要是1gap gap / 3 1;//分组插入排序 预排序for (int i 0; i n - gap; i){int end i;int tmp a[i gap];while (end 0){if (a[end] tmp){a[end gap] a[end];end - gap;}elsebreak;}a[end gap] tmp;}}
}希尔排序特性 希尔排序有2层循环一个是gap的逐渐缩小一个是分为gap组之后的插入排序我们一般以为时间复杂度为**O(N*logN)**这个量级。但其实这其中的N一直是在变化的可理解为先上升后下降 所以这个量级是略大于N*logN查阅资料可得知希尔排序的时间复杂度大概为O(N1.3~2) 稳定性不稳定 2. 选择排序
还是以打扑克来举例有时候我们感觉一张一张摸牌十分费时间所以就指定一个人来发牌发完之后我们将这一把牌拿到手中再开始理牌 2.1 直接选择排序
这个选择排序每次都是趟都是选出最小的数我们可以在此基础上做出优化每次选出2个数即最小值和最大值
//选择排序
void SelectSort(int* a, int n)
{int left 0;int right n - 1;while (left right){int mini left;int maxi left;for (int i left 1; i right; i){if (a[i] a[mini]){mini i;}if (a[i] a[maxi]){maxi i;}}Swap(a[left], a[mini]);//数据修正if (a[left] a[maxi]){maxi mini;}Swap(a[right], a[maxi]);left;right--;}
}直接选择排序特性 不考虑序列的有序性每次都找出最小最大值效率较低 时间复杂度O(N2) 最好情况O(N2) 最坏情况O(N2) 空间复杂度O(1) 稳定性不稳定 2.2 堆排序
堆排序也是选择排序的一种只不过没有直接选择排序那么朴实堆排序有一些“华丽”的技巧。
堆排序在之前二叉树的章节讲过了这里就不再过多赘述有兴趣的可以查看此篇文章数据结构——二叉树
//向下调整 前提子树都是堆
void AdjustDown(int* val, int sz, int parent)
{//默认左孩子大int child parent * 2 1;//至多叶子结点结束while (child sz){//不越界 选出更大的孩子if (child 1 sz val[child] val[child 1]){child;}if (val[child] val[parent]){Swap(val[child], val[parent]);parent child;child parent * 2 1;}else{break;}}
}//堆排序
void HeapSort(int* a, int n)
{//向下调整 O(N)for (int i (n - 1 - 1) / 2; i 0; --i){AdjustDown(a,n, i);}//向下调整排序 O(N*logN)for (int i 0; i n; i){Swap(a[0], a[n - 1 - i]);AdjustDown(a, n - 1 - i, 0);}
}堆排序特性 堆排序进行选数据效率较高时间复杂度O(N*logN)空间复杂度O(1)稳定性不稳定 3. 交换排序
3.1 冒泡排序
冒泡排序应该是多数人的启蒙排序算法思路较为简单 //冒泡排序
void BubbleSort(int* a, int n)
{for (int i 0; i n; i){for (int j 0; j n - i - 1; j){if (a[j] a[j 1]){Swap(a[j], a[j 1]);}}}
}冒泡排序特性 时间复杂度O(N2) 最坏情况O(N2) 最好情况O(N) 空间复杂度O(1) 稳定性稳定 这里的最好情况就是里面没有发送交换了就证明此时序列已经有序则不需要往后再遍历优化如下
//冒泡排序
void BubbleSort(int* a, int n)
{for (int i 0; i n; i){bool falg true;for (int j 0; j n - i - 1; j){if (a[j] a[j 1]){Swap(a[j], a[j 1]);falg false;}}if (falg)break;}
}3.2 快速排序
快速排序顾名思义速度很快效率很高排序算法里面的大哥大
快排的思想是选出一个基准值key然后把这个值放入正确的位置最终排好序要去的位置 例如6,2,9,1,5,7,4这组数据 我们选出6为key值然后将比6小的放左边比6大的放右边 这一趟下来6就在正确的位置上了 hoare版本 //快速排序
void QuickSort(int* a, int left,int right)
{if (left right)return;//记录起始int begin left;int end right;//选取最左边为key值int keyi left;while (left right){//选左 右先走 找小值while (leftright a[right] a[keyi]){right--;}while (left right a[left] a[keyi]){left;}//交换两边的值Swap(a[left], a[right]);}Swap( a[keyi], a[left]);keyi left;//左右区间递归QuickSort(a, begin, keyi - 1);QuickSort(a, keyi1, end);
}hoare版本为快排的最初始版本这个版本不容易控制 找大值/小值的时候如果该值等于key值也需要挪动即a[right] a[keyi]、a[left] a[keyi] 另外判断条件还应加上leftright防止越界 左边作为key右边先走这样就能保证相对位置比key要小或者就是key的位置 右边作为key左边先走相遇位置比key大或者就是key的位置 已排序或者逆序的情况都是最糟糕的情况 有多少个数据就有递归多少层栈帧最终会导致栈溢出 随机选key 这个keyi影响了快排的效率只要keyi取的数每次越接近于中间那么每次就越接近于二分所以我们可以考虑随机选key这样就不必担心序列是否接近有序 //快速排序
void QuickSort(int* a, int left,int right)
{if (left right)return;//记录起始int begin left;int end right;//left可能不是0加上leftint randi left (rand() % (right - left));//还是选择左边为key交换一下Swap(a[left], a[randi]);//选取最左边为key值int keyi left;while (left right){//选左 右先走 找小值while (leftright a[right] a[keyi]){right--;}//左边找大值while (left right a[left] a[keyi]){left;}//交换两边的值Swap(a[left], a[right]);}Swap( a[keyi], a[left]);keyi left;//[begin,keyi-1] keyi [keyi1,end]//左右区间递归QuickSort(a, begin, keyi - 1);QuickSort(a, keyi1, end);
}三数取中 int GetMidNumi(int* a, int left, int right)
{int mid (left right) / 2;if (a[left] a[mid]){if (a[mid] a[right])return mid;else if (a[left] a[right])return left;elsereturn right;}else //a[left] a[mid]{if (a[mid] a[right])return mid;else if (a[left] a[right])return left;elsereturn right;}
}
int Partition1(int* a, int left, int right)
{//三数取中 开始 中间 末尾 选中间值int midi GetMidNumi(a, left, right);if (midi ! left)Swap(a[left], a[midi]);//选取最左边为key值int keyi left;while (left right){//选左 右先走 找小值while (left right a[right] a[keyi]){right--;}//左边找大值while (left right a[left] a[keyi]){left;}Swap(a[left], a[right]);}Swap(a[keyi], a[left]);keyi left;return keyi;
}
void QuickSort(int* a, int left, int right)
{if (left right)return;int keyi Partition1(a, left, right);QuickSort(a, left, keyi - 1);QuickSort(a, keyi 1, right);
}挖坑法 基本思路不边只是这个更好理解挖坑填坑、挖坑填坑最后相遇位置一定是坑位
//挖坑
int Partition2(int* a, int left, int right)
{//三数取中 开始 中间 末尾 选中间值int midi GetMidNumi(a, left, right);if (midi ! left)Swap(a[left], a[midi]);//选取最左边为key值int key a[left];int hole left;while (left right){//选左 右先走 找小值while (left right a[right] key){right--;}//填坑a[hole] a[right];//挖坑hole right;//左边找大值while (left right a[left] key){left;}a[hole] a[left];hole left;}a[hole] key;return hole;
}
void QuickSort(int* a, int left, int right)
{if (left right)return;int keyi Partition2(a, left, right);QuickSort(a, left, keyi - 1);QuickSort(a, keyi 1, right);
}前后指针 cur找的值比key小prevcur与prev位置的值交换curcur找的值比key大cur
//前后指针
int Partition3(int* a, int left, int right)
{//三数取中 开始 中间 末尾 选中间值int midi GetMidNumi(a, left, right);if (midi ! left)Swap(a[left], a[midi]);int keyi left;int prev left;int cur left 1;while (cur right){if (a[cur] a[keyi] prev ! cur){Swap(a[prev], a[cur]);}cur;}Swap(a[keyi], a[prev]);keyi prev;return keyi;
}
void QuickSort(int* a, int left, int right)
{if (left right)return;int keyi Partition3(a, left, right);QuickSort(a, left, keyi - 1);QuickSort(a, keyi 1, right);
}小区间优化
当大量的数据递归到小量数据的时候递归就会很麻烦所以当数据量较小的时候我们可以采用插入排序进行辅助直接将这一小段数据排成有序 #define INSERTION_SORT_THRESHOLD 10
void QuickSort(int* a, int left, int right)
{if (left right)return;//区间自己决定 一般采用10左右if ((right - left 1) INSERTION_SORT_THRESHOLD){int keyi Partition2(a, left, right);QuickSort(a, left, keyi - 1);QuickSort(a, keyi 1, right);}elseInsertSort(a left, right - left 1);
}非递归
模拟递归将区间放入栈
void QuickSortNonR(int* a, int left, int right)
{//用C的stl库stackint st;st.push(right);st.push(left);while (!st.empty()){int begin st.top();st.pop();int end st.top();st.pop();int keyi Partition2(a, begin, end);//[begin,keyi-1] keyi [keyi1,end]if (keyi 1 end){st.push(end);st.push(keyi 1);}if (begin keyi - 1){st.push(keyi - 1);st.push(begin);}}
}快排特性 时间复杂度O(N*logN) 快排比较像二叉树 单趟排序的时间复杂度为O(N)而递归的深度是O(logN)合计起来就是O(N*logN)这个量级 空间复杂度O(logN) 稳定性不稳定 4. 归并排序 归并排序的思想就是分治将一个序列看作n个子序列然后将子序列排好序之后两两归并这个方法也成为二路归并 4.1 递归
//归并排序
void _MergeSort(int* a, int begin, int end, int* tmp)
{if (begin end)return;//分割区间int mid (begin end) / 2;//子区间递归排序//[begin,mid] [mid1,end]_MergeSort(a, begin, mid, tmp);_MergeSort(a, mid1, end, tmp);//归并int begin1 begin;int begin2 mid1;int end1 mid;int end2 end;int index begin;while (begin1 end1 begin2 end2){if (a[begin1] a[begin2])tmp[index] a[begin1];elsetmp[index] a[begin2];}//防止未结束的区间while (begin1 end1){tmp[index] a[begin1];}while (begin2 end2){tmp[index] a[begin2];}//拷贝回原序列memcpy(a begin, tmp begin, sizeof(int) * (end - begin (int)1));
}void MergeSort(int* a, int n)
{//开辟临时空间int* tmp (int*)malloc(sizeof(int) * n);if (tmp NULL){perror(malloc fail\n);exit(-1);}_MergeSort(a, 0, n - 1, tmp);free(tmp);
}4.2 非递归 归并排序的非递归需要注意的就是边界问题我们每次都是分为2组归并如果是单数的话会发生越界行为所以要查看这两组的区间 begin1取值为i所以肯定不会越界 end1如果越界后面的肯定越界无需进行归并 end1没有越界begin2如果越界无需进行归并 begin2没有越界end2越界需要归并修正end2
void MergeSortNonR(int* a, int n)
{int* tmp (int*)malloc(sizeof(int) * n);if (tmp NULL){perror(malloc fail\n);exit(-1);}int gap 1;while (gap n){for (int i 0; i n; i 2 * gap){//归并int begin1 i;int end1 i gap - 1;int begin2 i gap;int end2 i 2 * gap - 1;//修正 外面一次性拷贝//if (end1 n)//{// //不归并// end1 n - 1;// //给一个不存在区间// begin2 n;// end2 n - 1;//}//else if (begin2 n)//{// //不归并 修正成不存在的区间// begin2 n;// end2 n - 1;//}//else if (end2 n)//{// //修正// end2 n - 1;//}if (end1 n || begin2 n){break;}if (end2 n){end2 n - 1;}int index i;while (begin1 end1 begin2 end2){if (a[begin1] a[begin2])tmp[index] a[begin1];elsetmp[index] a[begin2];}//防止未结束的区间while (begin1 end1){tmp[index] a[begin1];}while (begin2 end2){tmp[index] a[begin2];}memcpy(a i, tmp i, sizeof(int) * (end2 - i 1));}//外面拷贝一把梭哈//memcpy(a, tmp, sizeof(int) * n);gap * 2;}free(tmp);
}归并排序特性 时间复杂度O(N*logN)空间复杂度O(N)稳定性稳定归并排序更多解决的是磁盘中的外排序问题 5. 性能测试 测试性能我们开release版本火力全开 测试环境为Linux的g 本次只是简单的进行测试可能会有偶然性 void TestOP()
{srand(time(0));const int N 10000; //1w//const int N 100000; //10w//const int N 5000000; //100w//const int N 10000000; //1000w//const int N 100000000; //1亿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);int* a8 (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];//a4[i] 2;a5[i] a1[i];a6[i] a1[i];a7[i] a1[i];a8[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(a3, N);int end4 clock();int begin5 clock();BubbleSort(a5, N);int end5 clock();int begin6 clock();QuickSort(a4, 0, N - 1);int end6 clock();int begin7 clock();MergeSort(a6, N);int end7 clock();std::vectorint v(a8, a8 N);int begin8 clock();std::sort(v.begin(),v.end());int end8 clock();printf(InsertSort:%d\n, end1 - begin1);printf(ShellSort:%d\n, end2 - begin2);printf(SeletSort:%d\n, end3 - begin3);printf(HeapSort:%d\n, end4 - begin4);printf(BubbleSort:%d\n, end5 - begin5);printf(QuickSort:%d\n, end6 - begin6);printf(MergeSort:%d\n, end7 - begin7);printf(STLSort:%d\n, end8 - begin8);free(a1);free(a2);free(a3);free(a4);free(a5);free(a6);free(a7);free(a8);
}5.1 1w数据
在1w数据这个量级对于希尔排序、堆排序、快排、归并排序都是挠痒痒忽略不计 5.2 10w数据
在10w这个量级显然直接插入排序、直接选择排序、冒泡排序都以不堪重负而对于这些时间复杂度度在O(N*logN)量级的排序才刚刚开始 5.3 100w数据
到了100w这个量级就不再对量级为O(N2)进行测试了他们坐小孩儿那桌 这里可以看出快排还得是快排
5.4 1000w数据
到1000w这个量级堆排序就有点扛不住了 5.5 1亿数据
在一亿这个量级服务器有点跑不动了 换到Windows环境参考这个具体还得看机器和优化不是特别具有参考意义但可以看一下C库里面的快排实现 那本期的分享就到这里我们下期再见如果还有下期的话。
