首页 > 代码库 > 排序——快速排序算法

排序——快速排序算法

快速排序由C. A. R. Hoare在1962年提出。

它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。快速排序是对冒泡排序的一种改进。

这样说可能不是很形象,不是很好理解,我举个例子说明一下:有以下数列:

4 7 2 1 5 8 6 3  第一次选择4为基准,i=left=0,j=right=7,key=4,从后往前遍历,3 < 4,互换位置。i=0,j=7,key=4;

3 7 2 1 5 8 6 4 到第二个循环,3<4,因此i = 1,7>4,互换位置。i=1,j=7,key=4;

3 4 2 1 5 8 6 7 转到循环一,1<4,互换位置。i=1,j=3,key=4;

3 1 2 4 5 8 6 7 循环二,循环满足条件,直到i==j,跳出大循环,递归调用,i = 3处分开成两个数列。将key=4固定。

3 1 2               基准为3,i=left=0,j=right=2,key=3,从后往前遍历,2 < 3,互换位置。i=0,j=2,key=3;

2 1 3      到第二循环,结束。key=3固定。

2 1          基准为2,i=left=0,j=right=1,key=2,从后往前遍历,1 < 2,互换位置。i=0,j=1,key=2;

1 2          到第二循环,结束。

5 8 6 7      基准为5,i=left=4,j=right=7,key=5,从后往前遍历,结束。key=5固定;

8 6 7              基准为8,i=left=5,j=right=7,key=8,从后往前遍历,7 < 8,互换位置。i=5,j=7,key=8;

7 6 8       到第二循环,结束。key=8固定。

7 6        基准为7,i=left=5,j=right=6,key=7,从后往前遍历,6 < 7,互换位置。i=5,j=6,key=7;

6 7      到第二循环,结束。

以上为快排的实现过程(如有疑问,还望指出)

代码:(C语言):

void qSort(int num[],int left,int right){//第一个和最后一个元素
    if(left < right){
        int i=left, j=right;
        int key = num[left];//将第一个元素当作基准
        while(i<j){
            while(i<j && num[j]>=key) j--;
            int t=num[i]; num[i]=num[j]; num[j]=t;
            while(i<j && num[i]<=key) i++;
            t=num[i]; num[i]=num[j]; num[j]=t;
        }//固定key在数列中的位置不变,以key为界线递归调用重新排序。
        qSort(num,left,i-1);
        qSort(num,i+1,right);
    }
}

 

排序——快速排序算法