快速排序

查找策略的效率取决于表中记录排列的顺序，如果记录是按关键字域有序排列，那么就可以高效地对表进行查找。排序的方法通常有以下几种：

1. 插入排序，时间复杂度O（n2）
2. 快速排序，时间复杂度O（nlog2n）
3. 堆排序
4. 归并排序
5. 基数排序

C.A.Hoare提出的快速排序方法具有最好的平均时间性能，我们在本文进行重点分析。

快速排序的思想用文字描述起来挺费劲的，通俗讲起来就是找一个基准关键字，在每一次遍历使得基准关键字的所有左对象的值都小于基准值，而所有右对象的值都大于基准值，然后，以基准关键字为界分左右文件再分别排序。下面，以简单的实例进行分析：

假定有一无序数组：

19 2 76 11 23 49 76 12 15 3８

按照以下算法，第一次遍历排序过程如下

１.取基准基为19（通常为第一个元素值）
２.从左至右找到一个比基准值大的对象，再从右至左找到一个比基准值小的对象，两对象进行交换

   19 2 15 11 23 49 76 12 76 38

3.继续以上动作，直到两元素重合

   19 2 15 11 12 49 76 23 76 38

3.交换基准值与最后的对象值

   12 2 15 11 19 49 76 23 76 38

可看到，在第一次排序之后形成以基准值19为界的两部分，19的所有左值都小于19，19的所有右值都大于19，这样，将这两部分再分别进行排序，最终使得整个数组成为有序数组。

以下是快递排序的Ｃ语言排序实现：

#include <stdio.h>
#include <stdlib.h>
#以下代码参考《数据结构》
void quicksort(int *list, int left, int right)
{
    int pivot, i, j;
    int m;
    if(left < right)
    {
        i = left;
        j = right + 1;
        pivot = list[left];//记录基准值
        do{
            do{
                i ++;
            }while(list[i] < pivot);//跳过比基准值小的值

            do{
                j --;
            }while(list[j] > pivot);//跳过比基准值大的值

            if(i < j)
            {
                m = list[i];
                list[i] = list[j];
                list[j] = m;
            }
        }while(i < j);
        //此时，j值一定小于i值，因此将j值与基准值交换
        m = list[left];
        list[left] = list[j];
        list[j] = m;

        //此时，j值为原基准值，以j值为界分左右两部分，递归排序
        quicksort(list, left, j - 1);
        quicksort(list, j + 1, right);
    }
}
#define NUM_LIST    10
int numbers[NUM_LIST];
int main()
{
    int i;

    srand(getpid());

    for(i = 0; i < NUM_LIST; i++)
    {
        numbers[i] = rand() % 100;
    }

    printf("Num: ");
    for(i = 0; i < NUM_LIST; i++)
        printf("%d ", numbers[i]);
    printf("\n");
    quicksort(numbers, 0, NUM_LIST - 1);

    printf("Sort Num: ");
    for(i = 0; i < NUM_LIST; i++)
        printf("%d ", numbers[i]);
    printf("\n");
}


！！对于快速排序，《数据结构》有提到，除了将子序列的第一个记录当成基准值外，更好的方法是取当前子文件的初值、中值、后值三个关键字的中间值。