首页 > 代码库 > 快速排序和归并排序总结
快速排序和归并排序总结
都是两种效率高而且常用的排序方法,今天来总结下。
先说快排:
首先,快速排序的时间复杂度为nlogn,其思想实质为分治法。而这分治法的基本思想为以下三点:
1.先从数列中取出一个基准数。
2.在分治的过程中,比这个基准数小的数全部放到这个基准数的左边,反之则放到右边。
3.然后再对由第二步产生的两个区间再进行第二步的操作,当分出来的区间仅剩一个数为止。
#include <stdio.h>#include <string.h>#include <stdlib.h>#include <time.h>#define maxn 1000000int a[maxn];void qs(int a[],int l,int r){ if(l < r) { int i=l, j=r, x=a[l]; while(i < j) { while(i<j && a[j] >= x) j--; if(i < j) a[i++] = a[j]; while(i<j && a[i] < x) i++; if(i < j) a[j--] = a[i]; } a[i] = x; qs(a,l,i-1); qs(a,i+1,r); }}void print(int a[],int n){ for(int i=0; i<n; i++) printf("%d ",a[i]); printf("\n");}int main(){ int n,i; while(scanf("%d",&n) == 1) { srand(time(0)); for(i=0; i<n; i++) a[i] = rand()%100; qs(a,0,n-1); print(a,n); } return 0;}
这里我实现的版本是以第一个数为基准数,但是如果要按照升序排序的话而待排列数组又是降序的话,时间复杂度就成了n2 了。所以,有的方法是以待排列数组的中位数作为基准数的,要实现这个非常简单,将第一个元素与中位数交换即可。
接下来再说归并排序:
归并排序是建立在归并操作上的一种非常有效的排序方法。同样,归并排序的实质也是分治思想。
基本思想是将数组不断地分成两组,直至留下若干剩下一个或两个元素的小组。再合并这些小组。从而使得数组整体有序。
应该来说在数据范围不是相当大的时候,归并排序和快速排序的耗时应该是差不多的,但是归并排序有一个额外的空间开销--他需要一个辅助数组来存放合并下来的两个组的元素(有序的)。
#include <stdio.h>#include <string.h>#include <stdlib.h>#include <time.h>#define maxn 1000000int a[maxn],temp[maxn];void ma(int a[],int l,int mid,int r,int temp[]){ int i = l, j = mid+1; int m = mid,n = r; int t = 0; while(i<=m && j<=n) { if(a[i] <= a[j]) temp[t++] = a[i++]; else temp[t++] = a[j++]; } while(i<=m) temp[t++] = a[i++]; while(j<=n) temp[t++] = a[j++]; for(i=0; i<t; i++) a[i+l] = temp[i];}void ms(int a[],int l,int r,int temp[]){ if(l < r) { int m = (l + r) >> 1; ms(a,l,m,temp); ms(a,m+1,r,temp); ma(a,l,m,r,temp); }}void print(int a[],int n){ for(int i=0; i<n; i++) printf("%d ",a[i]); printf("\n");}int main(){ int n,i; while(scanf("%d",&n) == 1) { srand(time(0)); for(i=0; i<n; i++) a[i] = rand()%100; ms(a,0,n-1,temp); print(a,n); } return 0;}
归并排序还有一个有趣的用途--可以用来求一个数组的逆序数。
方法很简单,就是在合并的时候,加一行代码,示例如下:
void ma(int a[],int l,int mid,int r,int temp[]){ int i = l, j = mid+1; int m = mid,n = r; int t = 0; while(i<=m && j<=n) { if(a[i] <= a[j]) temp[t++] = a[i++]; else { cnt += (m-i+1); //如果a[i] 这是比 a[j]大,那么从a[i]其后面一共有m-i+1个数比a[j]大 temp[t++] = a[j++]; } } while(i<=m) temp[t++] = a[i++]; while(j<=n) temp[t++] = a[j++]; for(i=0; i<t; i++) a[i+l] = temp[i];}
那么把全局变量cnt 在main函数里定为0即可。
复制去Google翻译翻译结果
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。