【CLRS】《算法导论》读书笔记（二）：快速排序（Quicksort）

旧城等待， 2022-01-09 10:23 292阅读 0赞

**快速排序（Quicksort）**

维基百科：[http://en.wikipedia.org/wiki/Quick\_sort][http_en.wikipedia.org_wiki_Quick_sort]

平均时间复杂度：O(*n* log *n*)

示例：

\[6, 5, 3, 1, 8, 7, 2, 4\]

![04153342-e6a4c1197bf545eaa9b0c205a7354076.gif][]

**快速排序****三步分治过程：**

**分解**：数组 A\[p .. r\] 被划分为两个（可能为空）子数组 A\[p .. q - 1\] 和 A\[q + 1 .. r\]，使得 A\[p .. q - 1\] 中的每一个元素都小于等于 A\[q\]，而 A\[q\] 也小于等于 A\[q + 1 .. r\] 中的每个元素。其中，计算下标q也是划分过程的一部分。

**解决**：通过递归调用快速排序，对数组 A\[p .. q - 1\] 和 A\[q + 1 .. r\] 进行排序。

**合并**：因为子数组都是原址排序的，所以不需要合并操作：数组 A\[p .. r\] 已经有序。

**快速排序：**

伪代码：

PARTITION(A, p, r)

x = A\[r\]

i = p - 1

for j = p to r - 1

if A\[j\] <= x

i = i + 1

exchange A\[i\] with A\[j\]

exchange A\[i + 1\] with A\[r\]

return i + 1

QUICKSORT(A, p, r)

if p < r

q = PARTITION(A, p, r)

QUICKSORT(A, p , q - 1)

QUICKSORT(A, q + 1, r)

**随机化的快速排序**

伪代码：

RANDOMIZED-PARTITION(A, p, r)

i = RANDOM(p, r)

exchange A\[r\] with A\[i\]

return PARTITIOIN(A, p, r)

RANDOMIZED-QUICKSORT(A, p, r)

if p < r

q = RANDOMIZED-PARTITION(A, p, r)

RANDOMIZED-QUICKSORT(A, p, q - 1)

RANDOMIZED-QUICKSORT(A, q + 1, r)

**C语言实现**

quick\_sort.h

void quick_sort(int *array, int length);

quick\_sort.c

#import "quick_sort.h"
    
    void exchange(int *a, int *b) {
        int temp = *a;
        *a = *b;
        *b = temp;
    }
    
    int partition(int *array, int start, int end) {
        int i, j;
        int value = array[end];
    
        for(i = start - 1, j = start; j <= end - 1; j++) {
            if(array[j] <= value) {
                i++;
                exchange(array + i, array + j);
            }
        }
        exchange(array + i + 1, array + end);
    
        return i + 1;
    }
    
    void quick_sort_recursive(int *array, int start, int end) {
        if(start < end) {
            int index = partition(array, start, end);
            quick_sort_recursive(array, start, index - 1);
            quick_sort_recursive(array, index + 1, end);
        }
    }
    
    void quick_sort(int *array, int length) {
        quick_sort_recursive(array, 0, length - 1);
    }

main.c

#import <stdio.h>
    #import "quick_sort.h"
    
    int main() {
        int i;
        int array[8] = {
        6, 5, 3, 1 ,8, 7, 2, 4};
    
        quick_sort(array, 8);
        
        for(i = 0; i < 8; i++) {
            printf("%d\n", array[i]);
        }
    
        return 0;
    }

运行结果：

![16211429-106f551f30fc4f6591dcb48afb07edd1.png][]

转载于:https://www.cnblogs.com/dyingbleed/archive/2013/03/10/2942858.html

[http_en.wikipedia.org_wiki_Quick_sort]: http://en.wikipedia.org/wiki/Quick_sort
[04153342-e6a4c1197bf545eaa9b0c205a7354076.gif]: /images/20220109/19fbf2c19f264067a4aa2e18a2d54644.png
[16211429-106f551f30fc4f6591dcb48afb07edd1.png]: /images/20220109/274779fed66e4b479d2f20c70d3ea0aa.png