快速排序

快速排序WIKI上这么描述的:

快速排序使用分治法(Divide and conquer)策略来把一个序列(list)分为两个子序列(sub-lists),步骤为:

(1)从数列中挑出一个元素,称为“基准”(pivot)

(2)重新排序数列,所有元素比基准值小的摆放在基准前面,所有元素比基准值大的摆在基准的后面(相同的数可以到任一边),在这个分区退出之后,该基准就处于数列的中间位置,这个称为分区(partition)操作

(3)递归地(recursive)把小于基准值元素的子数列和大于基准值元素的子数列排序

其实说的土一点,就是通过一趟排序,找到了一个key(下标),将要排序的分割撑独立的两部分,其中左边一部分不大于key对应的value值,右边一部分不小于key对应的value值;然后再对子分区进行递归调用上面的分区操作

一个小例子:

#include <stdio.h>
#include <stdlib.h>

#define MAXSIZE 10

typedef struct {
    int data[MAXSIZE];
    int length;
}SqList;

void swap(SqList *L, int low, int high){
    int temp;
    temp = L->data[low];
    L->data[low] = L->data[high];
    L->data[high] = temp;
}

int Partition(SqList *L, int low, int high){
    int value;
    value = L->data[low];
    while (low < high){
        while (low < high && L->data[high] >= value)
            high–;
        swap(L, low, high);
        while (low < high && L->data[low] <= value)
            low++;
        swap(L, low, high);
    }
    return low;
}

int QSort(SqList *L, int low, int high){
    int key;
    if (low < high){
        key = Partition(L, low, high);

        QSort(L, low, key – 1);
        QSort(L, key + 1, high);
    }
    return 0;
}

int QuickSort(SqList *L){

    QSort(L, 0, L->length – 1);
    return 0;
}

int main(){
    SqList L;
    L.length = MAXSIZE;
    printf(“Before sorting: “);
    int j;
    for (j = 0; j < L.length; j++){
        L.data[j] = rand() % 100;
        printf(“%d “, L.data[j]);
    }
    QuickSort(&L);
    printf(“\nAfter sorting: “);
    int i;
    for (i = 0; i < L.length; i++){
        printf(“%d “, L.data[i]);
    }
    printf(“\n”);
    return 0;
}

lihui@LastWish  $ ./a.exe
Before sorting: 33 43 62 29 0 8 52 56 56 19
After sorting: 0 8 19 29 33 43 52 56 56 62

QSort(L, 0, L->length – 1);参数指出了需要排序的序列L最小下标low到最大下标high的范围,进而进行递归直到结束

key = Partition(L, low, high);是最核心的部分,在执行之前,列表为Before sorting: 33 43 62 29 0 8 52 56 56 19,Partition函数要做的是先选取当中一个关键字,比如选择第一个下标的值33,然后想尽办法将它放到一个新的下标位置,使得它左边的值都比它小,右边的值都比它大

(1)程序开始,列表初始值为:33 43 62 29 0 8 52 56 56 19

(2)value = L->data[low];将L->data[low] = L->data[0] = 33赋值给了关键字key对应的值value,而此时的L->data[high] = 19

(3)L->data[high] = L->data[9] = 19不大于value=33,所以不执行high–

(4)交换low和high对应的值swap(L, low, high);显然因为L->data[high]是一个比value=33(即L->data[low])还小的值,因此将19换到左侧,也就是列表变成了:19 43 62 29 0 8 52 56 56 33

(5)此时value还是33,但是L->data[low] = L->data[0] = 19,L->data[high] = 33了,所以满足条件L->data[low] <= value,因此low++,此时low=1,就好像low指针移到了下一位,L->data[low] = L->data[1] = 43,进而执行swap函数,列表变成了19 33 62 29 0 8 52 56 56 43

(6)此时value还是33,但是L->data[low] = L->data[1] = 33,L->data[high] = 43,满足L->data[high] >= value,high–,所以high为8,然后swap函数,列表变成19 56 62 29 0 8 52 56 33 43,然后L->data[low] = 56 <= value = 33不满足,所以直接swap函数,列表变成了19 33 62 29 0 8 52 56 56 43

(7)此时value为33,L->data[low] = L->data[1] = 33,L->data[high] = L->data[8] = 56,所以满足L->data[high] >= value,所以high–,high为7,执行swap函数,列表变成19 56 62 29 0 8 52 33 56 43,接着L->data[low] = 56 <= value=33不成立,执行swap函数变成了19 33 62 29 0 8 52 56 56 43

(8)此时value为33,L->data[high] = 56 >= value成立,所以high–,high=6,执行swap函数,列表变成19 52 62 29 0 8 33 56 56 43,L->data[low] = 52 <= value不成立,所以执行swap函数,列表变成19 52 62 29 0 8 33 56 56 43

(9)此时value为33,L->data[high] = 33 >= value成立,所以high–,high=5,执行swap函数,列表变成19 8 62 29 0 52 33 56 56 43,L->data[low] = 8 <= value成立,所以low++,low=2,执行swap函数列表变成19 8 52 29 0 62 33 56 56 43

(10)此时value为33,L->data[high] = 62 >= value成立,所以high–,high=4,执行swap函数,列表变成19 8 0 29 52 62 33 56 56 43,L->data[low] = 0 <= value成立,所以low++,low=3,执行swap函数列表变成19 8 0 52 29 62 33 56 56 43

(11)此时value为33,L->data[high] = 29 >= value不成立,执行swap函数19 8 0 29 52 62 33 56 56 43,L->data[low] = 29 <= value成立,所以low++,low = 4 = high,所以执行swap函数列表不发生改变,依旧是19 8 0 29 52 62 33 56 56 43

(12)此时low=high,所以函数Partition返回low的值4

(13)接下来就是递归调用QSort(L, 0, 3);和QSort(L, 5, 9);对子列表19 8 0 29和62 33 56 56 43分别进行同样上面的Partition行动,知道顺序全部排好为止

其实Partition函数就是将选取的key不断叫唤,将比它小的值换到它的左边,比它大的换到它的右边,它也在叫唤过程中不断更改自己的位置,直到完全满足这个要求为止

发表评论