钓鱼网站网站怎么做,哈尔滨seo优化服务商,深圳市市长,济南网站制作服务文章目录 前言 一.冒泡排序二.选择排序三.插入排序四.希尔排序五.堆排序六.快速排序hoare挖坑法前后指针快排递归实现#xff1a;快排非递归实现#xff1a; 七、归并排序归并递归实现#xff1a;归并非递归实现#xff1a; 八、各个排序的对比图 前言 排序#xff1a;所谓… 文章目录 前言 一.冒泡排序二.选择排序三.插入排序四.希尔排序五.堆排序六.快速排序hoare挖坑法前后指针快排递归实现快排非递归实现 七、归并排序归并递归实现归并非递归实现 八、各个排序的对比图 前言 排序所谓排序就是使一串记录按照其中的某个或某些关键字的大小 递增或递减的排列起来的操作。 稳定性假定在待排序的记录序列中存在多个具有相同的关键字的记录若经过排序这些记录的相对次序保持不变即在原序列中r[i]r[j]且r[i]在r[j]之前而在排序后的序列中r[i]仍在r[j]之前则称这种排序算法是稳定的否则称为不稳定的。 内部排序数据元素全部放在内存中的排序。 外部排序数据元素太多不能同时放在内存中根据排序过程的要求不能在内外存之间移动数据的排序
接下来会涉及到的排序
这里写了一个测试排序性能的代码方便我们观察各个排序的好坏
//测试排序的性能
void TestOP()
{srand((unsigned)time(NULL));//N的数值手动改变以判断性能的好坏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() i;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);
}还有交换函数
//交换函数
void Swap(int* x, int* y)
{int tmp *x;*x *y;*y tmp;
}以下排序默认是升序即从小到大的顺序
一.冒泡排序
冒泡的时间复杂度是O(N^2),空间复杂度是O(1),具有稳定性 从图中我们可以看出冒泡排序其实就是一种选择排序即走一次找到最大的数放在最右边接下来要排序的数据就少了一个再走一次找到此时最大的数放在此时的最右边接下来不断重复此步骤数据就有序了 //冒泡排序
void BubbleSort(int* a, int n)
{for (int i 0; i n - 1; i){int flag 0;for (int j 0; j n - 1 - i; j){if (a[j] a[j 1]){Swap(a[j], a[j 1]);flag 1;}}if (flag 0){return;}}
}虽然我们使用了flag进行了优化使冒泡排序在最好的情况下的时间复杂度位O(N),但是实际上冒泡排序只有教学意义没有实践意义效率非常低 在十万个数据下面冒泡走了5s而在一百万数据下面走了接近1min了可见效率是如此的低下 二.选择排序
选择排序的时间复杂度是O(N^2),空间复杂度是O(1),具有不稳定性 从图中我们可以清楚的看到选择排序每走一次找到最大或者最小的数据放在最右边或者最左边然后减少排序的个数以此类推完成排序 这个排序方法可以优化一下即走一次找到最小的同时找到最大的
//选择排序
void SelectSort(int* a, int n)
{int begin 0;int end n - 1;while (begin end){int mini begin;int maxi begin;for (int i begin 1; i end; i){if (a[i] a[mini]){mini i;}if (a[i] a[maxi]){maxi i;}}Swap(a[begin], a[mini]);if (maxi begin){maxi mini;}Swap(a[end], a[maxi]);begin;end--;}
} 选择排序即没有实际意义也没有教学意义效率低下 在十万个数据下面选择走了8s而在一百万数据下面走了接近15min了效率不行 三.插入排序
插入排序的时间复杂度是O(N^2),空间复杂度是O(1),具有稳定性 插入排序的思路就是假设在[0,end]是有序的数据在end1的位置上插入一个新的数据用tmp保存插入的数据。 如果end位置上的值大于tmp,end就减1比较此时end位置上的值与tmp的大小 如果end位置上的值小于tmp退出循环将tmp赋给end 1 位置上的值 //插入排序
void InsertSort(int* a, int n)
{for (int i 0; i n - 1; i){int end i;//[0,end]是有序的插入[end1]数据int tmp a[end 1];while (end 0){if (a[end] tmp){a[end 1] a[end];end--;}else{break;}}a[end 1] tmp;}
}虽然插入排序的时间复杂度是O(N^2),但是它具有实践意义
在十万个数据下面走了1s在一百万数据下面走了16s了可见效率是还可以 四.希尔排序
希尔排序的时间复杂度是O(N^1.3),空间复杂度是O1不具有稳定性 希尔排序Shell Sort是插入排序的一种。也称缩小增量排序是直接插入排序算法的一种更高效的改进版本。 希尔排序的思想 预排序先分gap,在各自的组内进行插入排序插入排序排好序后减小gap的值再次进行预排序直到gap 1,进行插入排序这样数据就有序了 假设gap 3,将原数据分成3组那么第一趟预排序的结果为下图 可以看到在走了一趟后的数据比原始数据接近有序这就是希尔排序的优点
//希尔排序
void ShellSort(int* a, 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 a[end gap];while (end 0){if (a[end] tmp){a[end gap] a[end];end - gap;}else{break;}}a[end gap] tmp;}}
}在十万个数据下面希尔走了31ms在一百万数据下面走了264ms可见效率还是很快的 五.堆排序
堆排序的时间复杂度是O(NlogN),空间复杂度是O(1),不具有稳定性 堆排序Heap Sort是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构并同时满足堆积的性质即子结点的键值或索引总是小于或者大于它的父节点。 堆排序的基本思想是 将待排序序列构造成一个大顶堆此时整个序列的最大值就是堆顶的根节点。将其与末尾元素进行交换此时末尾就为最大值。然后将剩余n-1 个元素重新构造成一个堆这样会得到 n 个元素的次小值。 如此反复执行便能得到一个有序序列了。 //向下调整法
void AdjustDown(int* a, int n, int parent)
{int child 2 * parent 1;while (child n){if (child 1 n a[child 1] a[child]){child;}if (a[child] a[parent]){Swap(a[child], a[parent]);parent child;child 2 * parent 1;}else{break;}}
}//堆排序
void HeapSort(int* a, int n)
{//创建堆for (int i (n - 1 - 1) / 2; i 0; i--){AdjustDown(a, n, i);}//排序int end n - 1;while (end 0){Swap(a[0], a[end]);AdjustDown(a, end, 0);end--;}
}在十万个数据下面堆排走了45ms在一百万数据下面走了473ms效率还可以
六.快速排序
快速排序的平均时间复杂度是O(NlogN),但是在最坏情况下有可能是O(N^2),空间复杂度是O(logN)~O(N),不具有稳定性 快速排序Quick Sort是一种常用的排序算法。快速排序的基本思想是通过选择一个基准元素将数组分为两部分使得左边的元素都小于等于基准元素右边的元素都大于等于基准元素。然后对左右两部分分别进行快速排序直到整个数组有序。 但是当数组已经有序时是最坏情况快速排序的时间复杂度可能会达到O(N^2)。但是在大多数情况下快速排序的时间复杂度都非常接近O (NlogN)
快速排序优化的方法
1.三数取中 可以看到假定最左边的数作为基准元素会不准确因为有可能是最大的数也有可能是最小的数影响效率我们可以选择三个数中间的数来作为基准元素 //三数取中法 left midi right
int GetMidi(int* a,int left,int right)
{int midi (left right) / 2;if (a[left] a[midi]){if (a[midi] a[right]){return midi;}else if (a[left] a[right]){return left;}else{return right;}}else{if (a[midi] a[right]){return midi;}else if (a[left] a[right]){return left;}else{return right;}}
}2.小区间优化 由于快速排序要递归数据区间只要递归就要消耗空间那么当数据区间比较小时可以用插入排序不用在递归了 //小区间排序 - 插入排序
if ((right - left 1) 10)
{//注意数组取的位置和数组的长度InsertSort(aleft, right - left 1);
}快速排序有三种排序方法
hoare 此时数据6已经排好了只需要递归它的左边与右边进行排序即可
// 快速排序hoare版本
int PartSort1(int* a, int left, int right)
{//三数取中int midi GetMidi(a, left, right);Swap(a[left], a[midi]);int keyi left;int begin left;int end right;while (begin end){while (begin end a[end] a[keyi]){end--;}while (begin end a[begin] a[keyi]){begin;}Swap(a[begin], a[end]);}Swap(a[keyi], a[begin]);return begin;
}挖坑法 // 快速排序挖坑法
int PartSort2(int* a, int left, int right)
{//三数取中int midi GetMidi(a, left, right);Swap(a[left], a[midi]);int key a[left];int begin left;int end right;while (begin end){while (begin end a[end] key){end--;}a[begin] a[end];while (begin end a[begin] key){begin;}a[end] a[begin];}a[begin] key;return begin;
}前后指针 // 快速排序前后指针法
int PartSort3(int* a, int left, int right)
{//三数取中int midi GetMidi(a, left, right);Swap(a[left], a[midi]);int keyi left;int prev left;int cur prev 1;while (cur right){if (a[cur] a[keyi] prev ! cur){Swap(a[cur], a[prev]);}cur;}Swap(a[prev], a[keyi]);return prev;
}快排递归实现
以上三种方法针对的是每一次排序我们还需要递归剩下的区间来完成数据的有效
void QuickSort(int* a, int left, int right)
{//[left,right]是闭区间if (left right){return;}//小区间排序 - 插入排序if ((right - left 1) 10){//注意数组取的位置和数组的长度InsertSort(aleft, right - left 1);}else{//随便选择一种排序方法即可int keyi PartSort3(a,left,right);//[left,keyi-1] keyi [keyi1,right]//递归左边与右边QuickSort(a, left, keyi - 1);QuickSort(a, keyi 1, right);}
}在十万个数据下面快速排序递归方法走了7ms在一百万数据下面走了80ms可见效率非常快 快排非递归实现
众所周知递归会在栈上开辟空间当递归的深度很大时会导致栈溢出这时我们可以把快速排序改成用非递归的形式实现
递归改为非递归的方法有两种 用循环实现 利用栈来实现 现在我们利用栈来实现这里的栈是数据结构里面的栈。因为内存的栈的空间很小而堆的空间很大数据结构的栈就是在堆上开辟的 // 快速排序 非递归实现
//利用栈来实现
void QuickSortNonR(int* a, int left, int right)
{ST st;STInit(st);STPush(st, right);STPush(st, left);while (!STEmpty(st)){int begin STTop(st);STPop(st);int end STTop(st);STPop(st);int keyi PartSort3(a, begin, end);//[begin,keyi-1] keyi [keyi1,end]if (keyi 1 end){STPush(st, end);STPush(st, keyi 1);}if (begin keyi - 1){STPush(st, keyi - 1);STPush(st, begin);}}STDestroy(st);
}在十万个数据下面快速排序非递归方法走了19ms在一百万数据下面走了283ms可见效率与递归方法的差不多 七、归并排序
归并排序的时间复杂度是O(NlongN),空间复杂度是O(N),具有稳定性 归并排序MERGE-SORT是建立在归并操作上的一种有效的排序算法,该算法是采用分治法Divide andConquer的一个非常典型的应用。将已有序的子序列合并得到完全有序的序列即先使每个子序列有序再使子序列段间有序。若将两个有序表合并成一个有序表称为二路归并。 归并排序核心步骤 将数据划分区间区间大小从小到大每个区间进行归并归并完成后就要拷贝回去 归并递归实现
void _MergeSort(int* a, int* tmp, int left,int right)
{//递归if (left right){return;}int mid (left right) / 2;//[left,mid][mid1,right]_MergeSort(a, tmp, left, mid);_MergeSort(a, tmp, mid1, right);//归并int begin1 left;int end1 mid;int begin2 mid 1;int end2 right;int i left;while (begin1 end1 begin2 end2){if (a[begin1] a[begin2]){tmp[i] a[begin1];}else{tmp[i] a[begin2];}}while (begin1 end1){tmp[i] a[begin1];}while (begin2 end2){tmp[i] a[begin2];}//拷贝memcpy(a left, tmp left, (right - left 1) * sizeof(int));
}//归并排序
void MergeSort(int* a, int n)
{int* tmp (int*)malloc(n * sizeof(int));if (tmp NULL){perror(malloc fail);return;}_MergeSort(a, tmp, 0, n - 1);free(tmp);tmp NULL;
}在十万个数据下面归并排序递归方法走了9ms在一百万数据下面走了93ms可见效率非常快
归并非递归实现 上面我们提到递归会有栈溢出的问题所有我们可以尝试一下归并的非递归的实现方法
递归改为非递归的方法有两种 用循环实现 利用栈来实现
这次我们使用循环来实现归并的核心就是分区间进行排序既然如此 我们可以设置分组gap的初始值为1然后归并一次归并完成后gap乘以2来进行下一次的归并区间不断重复此步骤直到gap 大于等于 数组长度时退出循环
//归并排序 非递归实现
void MergeSortNonR(int* a, int n)
{int* tmp (int*)malloc(sizeof(int) * n);if (tmp NULL){perror(malloc fail);return;}//分组排序 每次两个gap组进行归并排序int gap 1;while (gap n){for (int i 0; i n; i2*gap){int begin1 i;int end1 i gap - 1;int begin2 i gap;int end2 i 2 * gap - 1;int j i;//printf([%d,%d],[%d,%d], begin1, end1, begin2, end2);//如果begin2越界了就不归并if (begin2 n){break;}//如果end2越界了就修正if (end2 n){end2 n - 1;}//归并排序while (begin1 end1 begin2 end2){if (a[begin1] a[begin2]){tmp[j] a[begin1];}else{tmp[j] a[begin2];}}while (begin1 end1){tmp[j] a[begin1];}while (begin2 end2){tmp[j] a[begin2];}//拷贝memcpy(a i, tmp i, (end2 - i 1) * sizeof(int));}gap * 2;}free(tmp);tmp NULL;
}在十万个数据下面归并排序非递归方法走了9ms在一百万数据下面走了87ms可见效率非常快 八、各个排序的对比图
