用织梦模板做网站,刚学完网站开发,文章类型的网站模版,重庆网站建设冒号个人主页~ 排序#xff08;上#xff09; 栈和队列 排序 二、常见排序的实现8、快速排序的优化9、非递归快速排序#xff08;1#xff09;基本思想#xff08;2#xff09;代码实现#xff08;3#xff09;时间复杂度#xff08;4#xff09;空间复杂度 10、归并排序… 个人主页~ 排序上 栈和队列 排序 二、常见排序的实现8、快速排序的优化9、非递归快速排序1基本思想2代码实现3时间复杂度4空间复杂度 10、归并排序1基本思想2代码实现3时间复杂度4空间复杂度 11、非递归归并排序1基本思想2代码实现3时间复杂度4空间复杂度 12、非比较排序1基本思想2代码实现3时间复杂度4空间复杂度 三、各个排序方法所用时间的比较1、代码实现2、分析 四、各个排序的稳定性1、基本概念2、各个排序的稳定性复杂度一览表 二、常见排序的实现
8、快速排序的优化
当我们使用快速排序时最坏的情况就是数组有序此时的时间复杂度为O(N^2) 最好的情况就是key每次取中位数 所以我们为了避免最坏情况的发生我们在快速排序的基础上衍生了一种优化的方法叫做三数取中 还有一种方法是随机选key但随机选key的效果不如三数取中
int GetMidIndex(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 right;elsereturn left;}else{if (a[mid] a[right])return mid;else if (a[left] a[right])return right;elsereturn left;}
}将三个比较出中间的数字作为key然后换到left上进行partsort 在每个partsort的最前边加上这条语句就优化了这个快速排序的结构
int PartSort(int* a, int left, int right)
{int midi GetMidIndex(a, left, right);Swap(a[left], a[midi]);......
}9、非递归快速排序
1基本思想
前边我们讲的快速排序是基于递归条件下实现的但我们知道递归会消耗栈上的空间并且栈上的空间比较小不能实现大量数据的快速排序所以我们要将这个过程放在空间更大的堆上也就是使用栈来实现 栈的作用就是存储区间这个区间由两个整数组成通过出入栈来模拟递归的过程
2代码实现
这里需要包含一下以前我们写过的栈的头文件
void QuickSortNonR(int* a, int left, int right)
{Stack st;StackInit(st);StackPush(st,right);StackPush(st, left);while (!StackEmpty(st)){int left StackTop(st);StackPop(st);int right StackTop(st);StackPop(st);//取出区间int keyi PartSort1(a, left, right);//通过keyi将数据区间一分为二if (keyi 1 right){StackPush(st, right);StackPush(st, keyi 1);}if (left keyi - 1){StackPush(st, keyi - 1);StackPush(st, left);}//存入区间}StackDestroy(st);
}3时间复杂度
同递归方式的快速排序为O(log₂N * N)
4空间复杂度
同递归方式的快速排序为O(log₂N)
10、归并排序
1基本思想
将一个待排序的序列分为若干个子序列每个子序列都是有序的然后再将有序的序列合并为整体的有序序列
2代码实现
void _MergeSort(int* a, int left, int right, int* tmp)
{if (left right)return;//找到中间下标int midi (left right) / 2;//一分为二二分为四的分开_MergeSort(a, left, midi, tmp);_MergeSort(a, midi 1, right, tmp);int begin1 left, end1 midi;int begin2 midi 1, end2 right;//i用来记录容器数组中对应的下标int i left;//将两个数组中按升序归并到容器数组中while (begin1 end1 begin2 end2){if (a[begin1] a[begin2])tmp[i] a[begin1];elsetmp[i] a[begin2];}//如果左右两个区间的数字还没有全部入到容器数组中将它们按顺序输入while (begin1 end1)tmp[i] a[begin1];while (begin2 end2)tmp[i] a[begin2];//将容器数组复制到原来的数组上memcpy(a left, tmp left, sizeof(int) * (right - left 1));
}void MergeSort(int* a, int n)
{int* tmp (int*)malloc(sizeof(int) * n);_MergeSort(a, 0, n - 1, tmp);free(tmp);
}3时间复杂度
归并排序分为两个过程 一是分解过程这是一个类二叉树的过程由中间下标分为两个区间再分为四个区间以此类推此过程的时间复杂度是O(log₂N) 二是合并过程合并过程中需要遍历整个数组找到谁大谁小然后排序这个过程的时间复杂度是O(N) 整个过程的时间复杂度就是O(N*log₂N)
4空间复杂度
该过程需要在堆上开辟n个空间以及递归所需要的log₂n个在栈上的空间由于对于n来说log₂n很小所以它的空间复杂度为O(N)
11、非递归归并排序
1基本思想
与快速排序相同递归方式的归并排序需要使用栈中空间在处理大量数据时空间不够所以我们可以用循环的方法减少栈的使用这就是非递归的归并排序
2代码实现
void MergeSortNonR(int* a, int n)
{int* tmp (int*)malloc(sizeof(int) * n);int gap 1;while (gap n){int j 0;//作为tmp的下标for (int i 0; i n; i 2*gap)//每次跳过两组数据{//这里的间隔差gap每次比较两组数据int begin1 i, end1 i gap - 1;int begin2 i gap, end2 i gap * 2 - 1;//以下同上if (end1 n || begin2 n)break;if (end2 n)end2 n - 1;while (begin1 end1 begin2 end2){if (a[begin1] a[begin2])tmp[j] a[begin1];elsetmp[j] a[begin2];}while (begin1 end1)tmp[j] a[begin1];while (begin2 end2)tmp[j] a[begin2];memcpy(a i, tmp i, sizeof(int) * (end2 - i 1));}gap * 2;//while结束后把间隔调两倍}free(tmp);
}3时间复杂度
for循环每次gap*2时间复杂度为O(log₂N)for循环中遍历了一遍数组时间复杂度为O(N) 总的时间复杂度为O(N * log₂N)
4空间复杂度
申请了堆上的n个空间空间复杂度为O(N)
12、非比较排序
1基本思想
计数排序是一种非比较排序实现过程中不需要任何的比较 第一步统计相同元素出现的次数 第二步根据统计的结果将序列回收到原来的序列当中 这个排序适用于数据比较集中的序列
2代码实现
void CountSort(int* a, int n)
{int min, max;min max a[0];for (int i 0; i n; i){if (a[i] max)max a[i];if (a[i] min)min a[i];}int range max - min 1;//找到这一组数据中最大和最小的数相减得出这组数据的范围int* countA (int*)malloc(sizeof(int) * range);memset(countA, 0, sizeof(int)*range);//创建一个在堆上的数组作为计数数组大小为这组数据的范围将其中的元素全部重置为0for (int i 0; i n; i)countA[a[i] - min];//将每个数字出现的次数记录int k 0;for (int i 0; i range; i){while (countA[i]--)a[k] i min;}
}//下标加上整个数组的最小值就是当前数据的大小countA为0时退出循环不为0就记录下来3时间复杂度
找出最大最小值需要遍历一遍数组记录数字走for循环中range 所以时间复杂度为O(Nrange当数据比较集中时时间复杂度接近O(N) 到底是O(N还是O(range取决于它们俩哪个大
4空间复杂度
在堆上开辟了range个空间空间复杂度为O(range当数据比较集中时空间复杂度接近O(1)
三、各个排序方法所用时间的比较
1、代码实现
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);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];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();
//clock是一个函数用于记录当前时间点在开始时记录一下在结束后记录一下
//得出的时间差就是这个排序所用的时间int begin2 clock();ShellSort(a2, N);int end2 clock();int begin3 clock();BubbleSort(a3, N);int end3 clock();int begin4 clock();SelectSort(a4, N);int end4 clock();int begin5 clock();HeapSort(a5, N);int end5 clock();int begin6 clock();QuickSort(a6, 0, N - 1);int end6 clock();int begin7 clock();MergeSort(a7, N);int end7 clock();int begin8 clock();CountSort(a8, N);int end8 clock();printf(InsertSort:%d\n, end1 - begin1);printf(ShellSort:%d\n, end2 - begin2);printf(BubbleSort:%d\n, end3 - begin3);printf(SelcetSort:%d\n, end4 - begin4);printf(HeapSort:%d\n, end5 - begin5);printf(QuickSort:%d\n, end6 - begin6);printf(MergeSort:%d\n, end7 - begin7);printf(CountSort:%d\n, end8 - begin8);free(a1);free(a2);free(a3);free(a4);free(a5);free(a6);free(a7);free(a8);
}2、分析 当数据给到10W个时我们可以明显看出各个排序的差距 最拉胯的就是冒泡排序跟其他排序所用时间都不在一个量级上 然后就是直接插入以及选择插入 然后就是希尔排序、堆排序、快速排序、归并排序 因为随机数的生成是由时间戳实现的两个随机数之间差的并不多所以范围比较集中这就使得计数排序超级快
四、各个排序的稳定性
1、基本概念
稳定性好就是一个序列中存在着两个即两个以上的相同数据这两个数据在排序前后相对位置不变反之就是不好 这里的前后相对位置不变不是指它们两个数据一直待在原来的位置而是前边的数字a1在排列后还在后边的数字a2前边而不是跑到它的后边了
2、各个排序的稳定性复杂度一览表
排序方法平均情况最好情况最坏情况辅助空间稳定性冒泡排序O(N^2)O(N)O(N^2)O(1)稳定简单选择排序O(N^2)O(N^2)O(N^2)O(1)不稳定直接插入排序O(N^2)O(N)O(N^2)O(1)稳定希尔排序O(N ^log₂N)~O(N ^2)O(N^1.3)O(N^2)O(1)不稳定堆排序O(N^log₂N)O(N^log₂N)O(N^log₂N)O(1)不稳定归并排序O(N^log₂N)O(N^log₂N)O(N^log₂N)O(N)稳定快速排序O(N^log₂N)O(N^log₂N)O(N^2)O(log₂N)~O(N)不稳定 感谢观看
