排序算法六：快速排序

一、原理

选择排序的原理是分治，把排序序列切分成若干个小组后分别排序。每次排序都以随机的一个元素作为哨兵（一般都以排序区间的中间元素或者首元素作为哨兵），比他大的元素都放到右边，比它小的都放到左边。然后分别对该元素左边和右边的元素再法排序，直到所有的元素都是有序状态。

具体的排序过程描述为：

选取一个哨兵元素 temp，设置两个指针 low 和 high 分别从数组的两端开始遍历。
high 指针从右到左遍历，当遇到 A[high] < temp 的时候，设置 A[left] 的值为 A[high] 。
low 指针从左到右遍历，当遇到 A[high] > temp 的时候，设置 A[high] 的值为 A[left] 。
重复执行 2 、 3 步，直到 low 和 high 相遇，设置 low 元素的值为 temp 。此时 low 左边的元素都小于 temp，low 右边的元素都大于 temp 。再分别对左右子区间的元素分别排序。

图例：

以数组 [54, 15, 34, 82, 15, 46, 85, 43] 为例，初始状态时设置 low 指针指向第一个元素，high 指针指向最后一个元素，temp 为第一个元素的值 54：

遍历 high 指针，从右到左找到第一个小于 54 的元素 43，赋值给 low：

遍历 low 指针，从左到右找到第一个大于 54 的元素 82，赋值给 high：

遍历 high 指针，从右到左找到一个小于 54 的元素 46，赋值给 low：

遍历 low 指针，继续寻找第一个大于 54 的元素。但是直到遇见 high 指针，都没有找到再比 54 大的元素，把 temp 值赋值给 low：

此时第一轮排序完成，54 左边的元素都比它小，右边的元素都比它大。因此按照这个操作，继续对左边和右边的区间再执行相同的操作，多次排序即可完成整个数组的排序。

复杂度分析：

最坏的情况下，数组无序，快速排序和冒泡排序差不多。

时间复杂度：最坏情况下，时间复杂度为 O( $n^{2}$ )；最好的情况和平均情况下算法复杂度为 O( $n \log (n)$ )。
空间复杂度：最坏情况下，空间复杂度为 O( $n$ )；平均情况下空间复杂度为 O( $\log (n)$ ) 。

二、代码实现

快排的写法多样，以下实现了 C++和 Python 两种语言的快速排序算法实现。

其中 C++选取的哨兵是数组第一个元素，python 选取的哨兵是数组中间元素。

2.1 C++实现

以区间中点作为排序标杆：

/*
 * 快速排序算法实现，对 [left, right) 部分的数组排序。
 * @data 待排序数组
 * @left 左区间，包含该下标元素
 * @right 右区间，不包含该下标元素
 */
template<typename T>
void quick_sort(vector<T> &data, int left, int right) {
    int i = left, j = right - 1;
    T temp;

    if (right <= left) {
        return;
    }

    temp = data[i];

    while (i < j) {
        // 从右到左遍历找到一个比 temp 小的
        while (i < j && data[j] >= temp) {
            j--;
        }
        if (i < j && data[j] < temp) {
            data[i] = data[j];
        }

        // 从左到右遍历找到一个比 temp 大的
        while (i < j && data[i] <= temp) {
            i++;
        }
        if (i < j && data[i] > temp) {
            data[j] = data[i];
        }
    }

    data[i] = temp;

    // 排序的区间是左闭右开
    quick_sort(data, left, i);
    quick_sort(data, i + 1, right);
}

* 快速排序算法实现，对 [left, right) 部分的数组排序。

* @data 待排序数组

* @left 左区间，包含该下标元素

* @right 右区间，不包含该下标元素

template<typename T>

void quick_sort(vector<T> &data, int left, int right) {

int i = left, j = right - 1;

T temp;

if (right <= left) {

return;

}

temp = data[i];

while (i < j) {

// 从右到左遍历找到一个比 temp 小的

while (i < j && data[j] >= temp) {

j--;

}

if (i < j && data[j] < temp) {

data[i] = data[j];

}

// 从左到右遍历找到一个比 temp 大的

while (i < j && data[i] <= temp) {

i++;

}

if (i < j && data[i] > temp) {

data[j] = data[i];

}

data[i] = temp;

// 排序的区间是左闭右开

quick_sort(data, left, i);

quick_sort(data, i + 1, right);

}

2.2 python

以区间中点元素作为标杆：

import math


def quick_sort(data, left, right):
    """
    快速排序算法，对 [left, right) 区间的元素排序
    :param data: 待排序数组
    :param left: 待排序数组的左区间，包含对对该下标元素排序
    :param right: 待排序数组的右区间，不包含对该下标元素排序
    :return:
    """
    i, j = left, right - 1

    if i >= j:
        return

    # 选择区间中点元素作为哨兵
    mid = math.floor((i + j) / 2)
    temp = data[mid]
    data[i], data[mid] = data[mid], data[i]

    while i < j:
        while i < j and data[j] >= temp:
            j -= 1
        if i < j and data[j] < temp:
            data[i] = data[j]

        while i < j and data[i] <= temp:
            i += 1
        if i < j and data[i] > temp:
            data[j] = data[i]

    data[i] = temp

    quick_sort(data, left, i)
    quick_sort(data, i + 1, right)

import math

def quick_sort(data, left, right):

"""

快速排序算法，对 [left, right) 区间的元素排序

:param data: 待排序数组

:param left: 待排序数组的左区间，包含对对该下标元素排序

:param right: 待排序数组的右区间，不包含对该下标元素排序

:return:

"""

i, j = left, right - 1

if i >= j:

return

# 选择区间中点元素作为哨兵

mid = math.floor((i + j) / 2)

temp = data[mid]

data[i], data[mid] = data[mid], data[i]

while i < j:

while i < j and data[j] >= temp:

j -= 1

if i < j and data[j] < temp:

data[i] = data[j]

while i < j and data[i] <= temp:

i += 1

if i < j and data[i] > temp:

data[j] = data[i]

data[i] = temp

quick_sort(data, left, i)

quick_sort(data, i + 1, right)

2.3 golang 实现快速排序

2020-02-29 刷 leetcode 添加，使用数组中间元素作为哨兵：

/*
 * 快速排序，对 [left, right] 区间内的元素排序
 * @nums 排序数组
 * @left 左边界
 * @right 右边界，包含该下标元素
 */
func doQuickSort(nums []int, left, right int) {
    i, j := left, right
    if left >= right {
        return
    }

    // 取中间元素作为哨兵
    mid := (i + j) / 2
    x := nums[mid]
    nums[mid], nums[i] = nums[i], nums[mid]

    for i < j {
        for nums[j] >= x && i < j {
            j -= 1
        }
        if i < j && nums[j] < x {
            nums[i] = nums[j]
        }
        for nums[i] <= x && i < j {
            i += 1
        }
        if i < j && nums[i] > x {
            nums[j] = nums[i]
        }
    }
    nums[i] = x
    doQuickSort(nums, left, i-1)
    doQuickSort(nums, i+1, right)
}

func quickSort(nums []int) []int {
    doQuickSort(nums, 0, len(nums)-1)
    return nums
}

* 快速排序，对 [left, right] 区间内的元素排序

* @nums 排序数组

* @left 左边界

* @right 右边界，包含该下标元素

func doQuickSort(nums []int, left, right int) {

i, j := left, right

if left >= right {

return

}

// 取中间元素作为哨兵

mid := (i + j) / 2

x := nums[mid]

nums[mid], nums[i] = nums[i], nums[mid]

for i < j {

for nums[j] >= x && i < j {

j -= 1

}

if i < j && nums[j] < x {

nums[i] = nums[j]

}

for nums[i] <= x && i < j {

i += 1

}

if i < j && nums[i] > x {

nums[j] = nums[i]

}

nums[i] = x

doQuickSort(nums, left, i-1)

doQuickSort(nums, i+1, right)

}

func quickSort(nums []int) []int {

doQuickSort(nums, 0, len(nums)-1)

return nums

}

一	二	三	四	五	六	日
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

一、原理

二、代码实现

2.1 C++实现

2.2 python

2.3 golang 实现快速排序

发表评论 取消回复

发表评论取消回复