首页 > > 程序设计 > C/C++ >

快速排序

2018-06-18 03:57:15来源：未知阅读 ()

快速排序由C. A. R. Hoare在1962年提出。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

比如一个无序的序列a[7]：

4 6 8 9 3 1 5

l:0　　r:6

现在我们要对它做降序排列

1. 定义两个位置标记l和r在要排序部分的左右两边，（这里是0号和6号），先选定第一个元素4作为一个比较的基准值，

2.然后从右往左找一个大于4的数，这里是5。然后把右标记指向5也就是a[6]，（其实原来的j就标记了这）。这时我们把r和l标记的两个数a[r]和a[l]交换。交换完成后，就变成了这样：

5 6 8 9 3 1 4

l:0　　r:6

3. 然后从左到右找一个小于4的数，这里是3。然后让左标记指向它，然后交换a[l]与a[r]。交换完成后，就变成了这样：

5 6 8 9 4 1 3

l:4　　r:6

然后重复第2步，让 r 从现在的位置向左移动找到一个大于4的数，这时我们发现l和r相遇了，这样我们就得到了一个特殊的数组----以元素4为界，它左边的数总是大于4的，它右边的数总是小于4的。这时我们把数组取出2份，左边一份是所有大于4的数，是a[0]~a[3]。然后右边一份是所有小于4的数，a[5]~a[6]。

然后我们分别让这两个子序列进行上面的操作：

对于左边部分a[0]~a[3]：5 6 8 9

选定左边第一个数a[0]，也就是5为基准值，然后让所有比5大的数都在5左边，让所有比5小的数都在5右边。

得到：6 8 9 5

然后再继续分，递归地执行这个过程（让所有比基准值大的数都在基准值左边，所有比基准值小的数都在基准值右边），然后直到不能再分了。

这时我们就能得到一个降序的序列。

具体实现如下：

 1 //LR表示要排序部分的左右边界，如果要排序一个10个元素的数组，就调用QuickSort(0,10);
 2 void QuickSort(int L, int R)        
 3 {
 4     //设置两下标，分别为要排序部分的开始和结束元素的数组下标
 5     int l = L, r = R - 1;    
 6     if (l >= r) return;
 7     int key = a[L];            //以序列第一个元素为基准
 8     while (l < r)
 9     {
10         //让右边的下标r从右往左找到第一个小于key的数
11         while (a[r] <= key&&r>l) r--;//从右往左找到一个比key大的值
12         swap(&a[r], &a[l]);        //交换左右两个下标位置的值
13         if (l == r)break;        //如果l等于r，就结束循环
14         //让左边的下标l从左往右找到第一个大于key的数
15         while (a[l] >= key&&r>l)l++;//从左往右找到一个比key小的值
16         swap(&a[r], &a[l]);        //交换左右两个下标位置的值
17         if (l == r)break;        //如果l等于r，就结束循环
18     }
19     
20     //上面的部分已经让r==l，
21     //并且所有比key小的数都在key的左边，所有比key大的数都在key右边
22     QuickSort(L, r);
23     QuickSort(r+1, R);
24 }

上面代码是实现降序的，如果想实现升序，只要把两个while里面的>=和<=互换。

这里有一个例子，随机生成50000个数，然后降序输出

#include<stdio.h>
#include<time.h>
#include<stdlib.h>
#define N 50000

int a[N];

void init()//初始化数组
{
    srand((unsigned)time(NULL));
    for (int i = 0; i < N; i++)
    {
        a[i] = rand();
    }
}
void print()                //输出数组元素
{
    int i;
    for (i = 0; i < N;i++)
        printf("%d ",a[i]);
    printf("\n");
}

void swap(int*a, int*b)//交换两个变量的值
{
    int c = *a;
    *a = *b;
    *b = c;
}

//LR表示要排序部分的左右边界，如果要排序一个10个元素的数组，就调用QuickSort(0,10);
void QuickSort(int L, int R)        
{
    //设置两下标，分别为要排序部分的开始和结束元素的数组下标
    int l = L, r = R - 1;    
    if (l >= r) return;
    int key = a[L];            //以数组第一个元素为基准
    while (l < r)
    {
        //让右边的下标r从右往左找到第一个小于key的数
        while (a[r] <= key&&r>l) r--;
        swap(&a[r], &a[l]);        //交换左右两个下标位置的值
        if (l == r)break;        //如果l等于r，就结束循环
        //让左边的下标l从左往右找到第一个大于key的数
        while (a[l] >= key&&r>l)l++;
        swap(&a[r], &a[l]);        //交换左右两个下标位置的值
        if (l == r)break;        //如果l等于r，就结束循环
    }
    
    //上面的部分已经让r==l，
    //并且所有比key小的数都在key的左边，所有比key大的数都在key右边
    QuickSort(L, r);
    QuickSort(r+1, R);
}

int main()
{
    init();
    printf("数组原来是这样的：\n");
    print();
    QuickSort(0,N);
    printf("\n排序后：\n");
    print();
    system("pause");
}