快速排序

  1. 首先,从列表的中点位置选取一项。这一项叫做基准点(pivot)

  2. 将列表中的项分区,以便小鱼基准点的所有项都移动到基准点的左边,而剩下的移动到基准点的右边。更具相关的实际项,基准点自身的位置也是变化的。例如:如果基准点自身是最大的项,它会位于列表的最右边,如果基准点是最小值,它会位于最左边。但是不管基准点最终位于何处。这个位置都是它在完全排序的列表中的最终位置。

  3. 分而治之。对于在基准点分割列表而形成的子列表,递归地重复调用该过程。一个子列表包含了基准点左边的所有项,另一个子列表包含基准点右边的所有项。

  4. 每次遇到少于 2 个项的一个子列表,就结束这个过程。

分割

快速排序最复杂的部分就是对子列表分割。一般采用下面的方法,因为此方法比较容易。

  1. 将基准点和子列表中的最后一项交换。

  2. 在已知小于基准点的项和剩余的项之间建立一个边界。在开始的时候边界放在最左边的首位(就是在第一项之前)

  3. 从子列表中的第一项开始,历遍整个子列表。每次遇到小于基准点的项,就将其与边界之后的第一项交换,并将边界移动到交换项之后。

  4. 将基准点和边界之后的第一项交换,从而完成整个过程。

过程如下图所示:

84b98c7ae67ccff1d33a081d2dd40860

现在小于基准项的所有项都在基准项的左边;剩下的都在基准项的右边。

在分割好子列表之后,对于左边和右边的子列表(12,11,13 和 16,19,15,17,18)重复这个过程,直到子列表长度最大为1。

Python实现:

def quick_sort(lyst):
    quick_sort_helper(lyst, 0, len(lyst) - 1)


def partition(lyst, left, right):
    """
    找到基准点并与项目中最后一个交换
    """

    def swap(lyst, i, j):
        """交换项目中 i 和 j的位置"""
        #  可以理解为 lyst[i], lyst[j] = lyst[j], lyst[i]
        temp = lyst[i]
        lyst[i] = lyst[j]
        lyst[j] = temp
		#   找到基准点并与最后一项交换
    middle = (left + right) // 2
    pivot = lyst[middle]
    lyst[middle], lyst[right] = lyst[right], lyst[middle]
    #  将边界点设置为第一个位置
    boundary = left
    #  将项移动到基准点左侧
    for index in range(left, right):
        if lyst[index] < pivot:
            swap(lyst, index, boundary)
            boundary += 1
    #  交换基准点和边界项目
    swap(lyst, right, boundary)
    return boundary


def quick_sort_helper(lyst, left, right):
    """用于隐藏子列表重点的额外参数
    :param lyst:
    :param left:
    :param right:
    :return:
    """
    if left < right:
        pivot_location = partition(lyst, left, right)
        quick_sort_helper(lyst, left, pivot_location - 1)
        quick_sort_helper(lyst, pivot_location + 1, right)


def quick_sort_main(size=20, sort=quick_sort):
    import random
    lyst = []
    for count in range(size):
        lyst.append(random.randint(1, size + 1))
    print(lyst)
    print(f"排序前lyst内存地址:{id(lyst)}\n")
    sort(lyst)
    print(lyst)
    print(f"排序后lyst内存地址:{id(lyst)}\n")


if __name__ == '__main__':
    quick_sort_main()

Go实现:

package main

import (
	"math/rand"
	"time"
	"fmt"
)

func partition(lyst []int, left int, right int) int {

	swap := func(lyst []int, i int, j int) {

		temp := lyst[i]
		lyst[i] = lyst[j]
		lyst[j] = temp
	}
	middle := (left + right) / 2
	pivot := lyst[middle]
	lyst[middle], lyst[right] = lyst[right], lyst[middle]
	boundary := left
	for i := left; i < right; i ++{
		if lyst[i] < pivot {
			swap(lyst, i, boundary)
			boundary += 1
		}
	}
	swap(lyst, right, boundary)
	return boundary
}

func quickSortHelper(lyst []int, left int, right int) {
	if left < right {
		pivotLocation := partition(lyst, left, right)
		quickSortHelper(lyst, left, pivotLocation-1)
		quickSortHelper(lyst, pivotLocation+1, right)
	}
}

func quickSort(lyst []int) {
	quickSortHelper(lyst, 0, len(lyst)-1)
}

func main() {
	//生成若干个不重复的随机数
	//生成count个[start,end)结束的不重复的随机数
	generateRandomNumber := func(start int, end int, count int) []int {
		//范围检查
		if end < start || (end-start) < count {
			return nil
		}

		//存放结果的slice
		nums := make([]int, 0)
		//随机数生成器,加入时间戳保证每次生成的随机数不一样
		r := rand.New(rand.NewSource(time.Now().UnixNano()))
		for len(nums) < count {
			//生成随机数
			num := r.Intn((end - start)) + start

			//查重
			exist := false
			for _, v := range nums {
				if v == num {
					exist = true
					break
				}
			}

			if !exist {
				nums = append(nums, num)
			}
		}

		return nums
	}

	nums := generateRandomNumber(1, 100, 40)
	fmt.Println("排序前:",nums)
	quickSort(nums)
	fmt.Println("排序后:",nums)
}

时间复杂度:

  1. 性能:

最好:$O(nlog_2n)$

最坏:$O(n^2)$

  1. 内存:

最好:$O(log_2n)$

最坏:$O(n)$


在第一次分割中,从列表头部到其尾部扫描了所有的项,因此,这个操作过程的工作量和列表长度 $n$ 成正比。

在这次之后的工作量,和左边的子列表的长度加上右边的子列表的长度(加在一起就是 $n-1$ )成正比。

当再次分割这些子列表的时候,有四个子列表,它们组合起来的长度近似为 $n$ , 因此组合的工作量还是和$n$ 成正比。随着分割为更多子列表,总的工作量还是和$n$ 成正比。

中间最重要的一点是:我们得确定对列表分割了多少次。假设每次新的子列表之间的分割线都尽可能靠近当前子列表的中央(当然通常情况下并不是)。在二叉树搜索算法中,我们会知道,当重复地居中分割一个列表的时候,大概要经过$log_2n$ 步之后会得到一个单元素,因此最好的情况是$O(nlog_2n)$


最坏的情况,假设一个列表已经排序好了。如果所选的基准点是第一个元素,那么在第一次分割的时候,基准点右边有$n-1$ 个元素,第二次 右边有$n-2$ 个元素。

尽管没有对元素进行交换,但总的分割次数是$n-1$次,并且执行比较的总次数是$\frac{1}{2}n^2 - \frac{1}{2}n $ 这跟 选择 冒泡 的次数是一样的。因此最坏的情况:$O(n^2)$


如果采用递归实现该算法,还必须要考虑到调用栈使用的内存。每一次递归都需要一个固定大小的内存用于栈,并且每次分割之后有两次调用。因此,最好的情况内存使用是 $O(log_2n)$ ,最坏的情况下,内存使用为$O(n)$

Note:

最好不要选择第一个和最后一个位置作为基准点!! 选择一个随机位置,或者选择整个列表的中位数,这样有助于算法接近平均情况的性能