快速排序(Quicksort)是对冒泡排序的一种改进。

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

算法

快速排序使用分治法(Divide and conquer)策略来把一个序列(list)分为较小和较大的2个子序列,然后递归地排序两个子序列。

步骤为:

  1. 挑选基准值:从数列中挑出一个元素,称为“基准”(pivot)。
  2. 分割:重新排序数列,所有比基准值小的元素摆放在基准前面,所有比基准值大的元素摆在基准后面(与基准值相等的数可以到任何一边)。在这个分割结束之后,对基准值的排序就已经完成。
  3. 递归排序子序列:递归地将小于基准值元素的子序列和大于基准值元素的子序列排序。

递归到最底部的判断条件是数列的大小是零或一,此时该数列显然已经有序。

选取基准值有数种具体方法,此选取方法对排序的时间性能有决定性影响。

代码示例

java

public static void quickSort(int[] arr, int head, int tail) {
    if (head >= tail || arr == null || arr.length <= 1) {
        return;
    }
    int i = head, j = tail, pivot = arr[(head + tail) / 2];
    while (i <= j) {
        while (arr[i] < pivot) {
            ++i;
        }
        while (arr[j] > pivot) {
            --j;
        }
        if (i < j) {
            int t = arr[i];
            arr[i] = arr[j];
            arr[j] = t;
            ++i;
            --j;
        } else if (i == j) {
            ++i;
        }
    }
    quickSort(arr, head, j);
    quickSort(arr, i, tail);
}

python

import random

def quick_sort(numbers):
    if len(numbers) <= 1:
        return numbers

    left, right, mid = [], [], []
    pivot = random.choice(numbers)

    for number in numbers:
        if number == pivot:
            mid.append(number)
        elif number < pivot:
            left.append(number)
        else:
            right.append(number)

    return quick_sort(left) + mid + quick_sort(right)

【腾讯云】境外1核2G服务器低至2折,半价续费券限量免费领取!
https://cloud.tencent.com/act/cps/redirect?redirect=1068&cps_key=e4b50f6c64a4480367f8a8d16fd07c5a&from=console

标签: java, 快速排序, Quicksort

添加新评论