首页 > 代码库 > 快速排序和归并排序总结

快速排序和归并排序总结

  都是两种效率高而且常用的排序方法,今天来总结下。

 

  先说快排:

 

  首先,快速排序的时间复杂度为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;}
View Code

 

  这里我实现的版本是以第一个数为基准数,但是如果要按照升序排序的话而待排列数组又是降序的话,时间复杂度就成了n了。所以,有的方法是以待排列数组的中位数作为基准数的,要实现这个非常简单,将第一个元素与中位数交换即可。

 

  接下来再说归并排序:

 

     归并排序是建立在归并操作上的一种非常有效的排序方法。同样,归并排序的实质也是分治思想。

 

  基本思想是将数组不断地分成两组,直至留下若干剩下一个或两个元素的小组。再合并这些小组。从而使得数组整体有序。

 

  应该来说在数据范围不是相当大的时候,归并排序和快速排序的耗时应该是差不多的,但是归并排序有一个额外的空间开销--他需要一个辅助数组来存放合并下来的两个组的元素(有序的)。

 

#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;}
View Code

 

  归并排序还有一个有趣的用途--可以用来求一个数组的逆序数。

 

  方法很简单,就是在合并的时候,加一行代码,示例如下:

  

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翻译翻译结果