数组排序简介-快速排序（Quick Sort）

基本思想

        采用经典的分治策略，选择数组中某个元素作为基准数，通过一趟排序将数组分为独立的两个子数组，一个子数组中所有元素值都比基准数小，另一个子数组中所有元素值都比基准数大。然后再按照同样的方式递归的对两个子数组分别进行快速排序，以达到整个数组有序。

算法步骤

假设数组的元素个数为 n 个，则快速排序的算法步骤如下：

1. 哨兵划分：选取一个基准数，将数组中比基准数大的元素移动到基准数右侧，比他小的元素移动到基准数左侧。
   1. 从当前数组中找到一个基准数 pivot（这里以当前数组第 1 个元素作为基准数，即 pivot=nums[low]）。
   2. 使用指针 i 指向数组开始位置，指针 j 指向数组末尾位置。
   3. 从右向左移动指针 j，找到第 1个小于基准值的元素。
   4. 从左向右移动指针 i，找到第 1个大于基准数的元素。
   5. 交换指针 i、指针 j 指向的两个元素位置。
   6. 重复第 3∼5步，直到指针 i 和指针 j 相遇时停止，最后将基准数放到两个子数组交界的位置上。
2. 递归分解：完成哨兵划分之后，对划分好的左右子数组分别进行递归排序。
   1. 按照基准数的位置将数组拆分为左右两个子数组。
   2. 对每个子数组分别重复「哨兵划分」和「递归分解」，直到各个子数组只有 1 个元素，排序结束。

我们以 [4,7,5,2,6,1,3] 为例，演示一下快速排序的整个步骤。

我们先来看一下单次「哨兵划分」的过程。

        在经过一次「哨兵划分」过程之后，数组就被划分为左子数组、基准数、右子树组三个独立部分。接下来只要对划分好的左右子数组分别进行递归排序即可完成排序。快速排序算法的整个步骤如下：

适用场景

        当需要对大量数据进行排序时，快速排序表现出色；

        对于随机分布的数据，快速排序的性能非常好。

        快速排序是一种原地排序算法，它只需要少量的额外内存空间来进行递归调用。这使得它在内存资源有限的环境中非常适用。

        在一些对时间要求较高的实时应用中，快速排序可以满足快速响应的需求

排序稳定性

        在进行哨兵划分时，基准数可能会被交换至相等元素的右侧。因此，快速排序是一种 不稳定排序算法。

代码实现(golang)

func quickSort(arr []int) []int {
    if len(arr) <= 1 {
        return arr
    }
    pivot := arr[0]
    var left, right []int
    for _, v := range arr[1:] {
        if v <= pivot {
            left = append(left, v)
        } else {
            right = append(right, v)
        }
    }
    return append(append(quickSort(left), pivot), quickSort(right)...)
}

func main() {
    arr := []int{9, 7, 5, 11, 12, 2, 14, 3, 10, 6}
    fmt.Println("原始数组：", arr)
    sortedArr := quickSort(arr)
    fmt.Println("排序后数组：", sortedArr)
}