快速排序（Quick Sort）

快速排序的基本思想：通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。

算法描述

快速排序使用分治法来把一个串（list）分为两个子串（sub-lists）。具体算法描述如下：

  • 从数列中挑出一个元素，称为“基准”（pivot）；
  • 重新排序数列，所有比基准值小的元素都放在基准前面，所有比基准值大的元素都放在基准后面，相同的元素可以到任意一边。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
  • 递归（recursive）地把小于基准值元素的子数列和大于基准值元素的子数列排序。

算法分析

最佳情况：T(n) = O(n log n)
最差情况：T(n) = O(n2)
平均情况：T(n) = O(n log n)　

代码实现

Java

Java 实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
import java.util.Arrays;

public class QuickSort {

    public static void quickSort(int[] arr, int l, int r) {
        if (l < r) {
            int left = l, right = r;
            int base = arr[left];
            while (left < right) {
                while (left < right && base <= arr[right]) {
                    right--;
                }
                while (left < right && base >= arr[left]) {
                    left++;
                }
                if (left < right) {
                    int temp = arr[left];
                    arr[left] = arr[right];
                    arr[right] = temp;
                }
            }
            if (l != left) {
                int temp = arr[l];
                arr[l] = arr[left];
                arr[left] = temp;
            }
            System.out.printf("以%2d为基准数排序后数组为：%s\n", base, Arrays.toString(arr));
            quickSort(arr, l, left - 1);
            quickSort(arr, right + 1, r);
        }
    }

    public static void main(String[] args) {
        int[] arr = { 3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48 };
        System.out.printf("原始数组：%s\n", Arrays.toString(arr));
        quickSort(arr, 0, arr.length - 1);
        System.out.printf("排序后数组：%s\n", Arrays.toString(arr));
    }
}

Python

Python 实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
def quick_sort(arr, l, r):
    if l < r:
        left, right = l, r
        base = arr[left]
        while left < right:
            while left < right and base <= arr[right]:
                right -= 1
            while left < right and base >= arr[left]:
                left += 1
            if left < right:
                arr[left], arr[right] = arr[right], arr[left]
        if l != left:
            arr[l], arr[left] = arr[left], arr[l]
        print('以%2d为基准数排序后数组为：%s' % (base, arr))
        quick_sort(arr, l, left - 1)
        quick_sort(arr, right + 1, r)


if __name__ == '__main__':
    arr = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48]
    print('原始数组：', arr)
    quick_sort(arr, 0, len(arr) - 1)
    print('排序后数组：', arr)

Go

Go 实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
package main

import (
	"fmt"
)

func QuickSort(arr *[15]int, l, r int) {
    if l < r {
        left, right := l, r
        base := arr[left] // 以最左边的数作为基准数
        for left < right {
            for left < right && base <= arr[right] { // 先从右往左找大于基准数的位置
                right--
            }
            for left < right && base >= arr[left] { // 再从左往右找小于基准数的位置
                left++
            }
            if left < right {
                arr[left], arr[right] = arr[right], arr[left] // 交换找到的大于和小于基准数的两个数的位置
            }
        }
        if l != left {
            arr[l], arr[left] = arr[left], arr[l] // 交换基准数和(left=right)的位置
        }
        fmt.Printf("以%2d为基准数排序后数组为：%v\n", base, *arr)
        QuickSort(arr, l, left-1)  // 递归左边
        QuickSort(arr, right+1, r) // 递归右边
    }
}

func main() {
    arr := [15]int{3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48}
    fmt.Printf("原始数组：%v\n", arr)
    QuickSort(&arr, 0, len(arr)-1)
    fmt.Printf("排序后数组：%v\n", arr)
}