排序算法-09-排序1 排序 (25分)-第二部分
作者:神秘网友
发布时间:2020-09-07 19:43:47
排序算法-09-排序1 排序 (25分)-第二部分
排序算法-09-排序1 排序 (25分)-第二部分- 题目
09-排序1 排序 (25分) - 排序算法-09-排序1 排序 (25分)-第一部分
http://blog.csdn.net/bobo1356/article/details/71749720
- 基本思想
分而治之的思想。归并排序也是先分解后归并,归并的时候也做了一部分工作。而快速排序,是选取一个基准元素(povit),然后把数组分为两部分,通过交换,使得基准元素的左边都小于基准元素,右边都大于基准元素。
基准元素一次性就排在了真正正确的地方。然后再递归地处理基准元素左边和右边就可以了。不需要在合并的时候进行操作。
快排的一个关键点是选择基准元素。
如果基准元素每次都正好选在正中间,那么 T(N) = 2*T(N/2) + O(N) = O(N*logN)。
但是如果基准元素每次都选择在最边上,那么 T(N) = T(N-1)+O(N) = O(N^2)。这样快排就退化为很慢的算法了。
一种选择基准元素的方式是:选择数组左端、右端、中间的中位数作为基准元素。 - 代码
#include <stdio.h> #define ElementType long #define maxn 100001 #define threshold 10 ElementType A[maxn]; void Swap(ElementType A[], int i, int j); ElementType Median3(ElementType A[], int left, int right); void Quick_sort(ElementType A[], int N); int main(int argc, const char * argv[]) { int N,i; scanf("%d",&N); for(i=0; i<N; i++){ scanf("%ld",&A[i]); } Quick_sort(A, N); printf("%ld",A[0]); for(i=1; i<N; i++){ printf(" %ld",A[i]); } printf("\n"); return 0; } void Swap(ElementType A[], int i, int j){ ElementType tmp = A[i]; A[i] = A[j]; A[j] = tmp; } ElementType Median3(ElementType A[], int left, int right) { int mid = (left + right)/2; //下面使得 A[left]、 A[mid]、 A[right] 按序排列 if(A[left] > A[mid]) Swap(A, left, mid); if(A[left] > A[right]) Swap(A, left, right); if(A[mid] > A[right]) Swap(A, mid, right); //之后只需要考虑A[left+1] - A[right-2] Swap(A,mid,right-1); return A[right-1]; } void Qsort(ElementType A[], int left, int right) { int length = right-left+1; if(length <= 1) return; else if(length < threshold) Insert_sort(A+left, length); else{ ElementType povit; int lo = left, hi = right-1; povit = Median3(A, left, right); while(1){ while(A[++lo] < povit); while(A[--hi] > povit); if(lo > hi) break; else Swap(A,lo,hi); } Swap(A, right-1, lo); //将povit换到正确的位置上 Qsort(A,left, lo-1); //递归解决左边 Qsort(A,lo+1,right); } } void Quick_sort(ElementType A[], int N) { Qsort(A, 0, N-1); }
- 运行结果
我们可以看到快速排序真的蛮快的。 - 小结
快速排序是不稳定的算法,最坏时间复杂度为O(N^2),但是当基准元素选取的比较好的时候,时间复杂度为O(N*logN)。空间复杂度为O(1)。
我在上面的一个优化是:当数组长度小于一个阈值(我这儿为10)时,采用插入排序。
- 核心代码
#include<stdlib.h> int cmp(const void *a, const void *b) { return(*(ElementType*)a-*(ElementType*)b); } qsort(A,N,sizeof(ElementType),cmp);
- 运行结果
哇,我发现我自己写的快排竟然比库函数还快一点,狠开心。
- 大概思想
可以用循环的方式来实现归并排序。具体就是刚开始两两归并,然后规模依次乘2,直到规模大于数组长度。
具体的归并时要注意,先归并长度足够的元素,最后处理剩余的元素。 - 代码
void Merge(ElementType A[],ElementType tmpA[], int L, int R, int rightEnd) { int tmp = L,leftEnd = R-1,size = rightEnd-L+1; while(L<=leftEnd && R<=rightEnd) { if(A[L] <= A[R]) tmpA[tmp++] = A[L++]; else tmpA[tmp++] = A[R++]; } while(L<=leftEnd) tmpA[tmp++] = A[L++]; while(R<=rightEnd) tmpA[tmp++] = A[R++]; int i; for(i=0; i<size; i++) A[rightEnd-i] = tmpA[rightEnd-i]; } //将A[]中的N个元素归并到tmpA[]中,其中length表示当前有序子列的长度 void Merge_pass(ElementType A[], ElementType tmpA[], int N, int length) { int i; for(i=0; i<=N-2*length; i+=2*length) { Merge(A, tmpA, i, i+length, i+2*length-1); } //归并最后两个列 if(i+length < N) Merge(A, tmpA, i, i+length, N-1); else{//如果最后只剩一个子列 for(; i<N; i++) tmpA[i] = A[i]; } } void Merge_sort(ElementType A[], int N) { int length = 1; ElementType *tmpA; tmpA = malloc(sizeof(ElementType) * N); if(tmpA != NULL) { while(length < N) { Merge_pass(A, tmpA, N, length); length *= 2; Merge_pass(tmpA, A, N,length); length *= 2; } free(tmpA); } else{ printf("空间不足\n"); } }
- 运行结果
- 小结
非递归排序用循环实现,比递归排序更快一些。时间复杂度还是O(N*logN)。