学习回顾算法（快速排序算法）

朴灿烈づ我的快乐病毒、 2022-06-05 07:40 154阅读 0赞

## 快速排序算法概述 ##

快速排序由C.A.R.Hoare在1962年提出。其基本思想是：通过一趟排序将要排序的数据分隔成独立的两部分，其中一部分的所有数据比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序。

**快速排序算法原理介绍**  
假设排序的数组是A\[0\] … A\[N - 1\]，首先取任意一个数据（通常选用数组的第一个数）作为关键数据，然后将所有比它小的都放到它前面，所有比它大的都放它后面。  
排序过程介绍：  
1）设置两个变量i、j，排序开始的时候：i = 0， j = N - 1;  
2）以数组第一个元素作为关键数据，赋值给key，即使key = A\[0\]；  
3）从j开始向前搜索，即从后向前搜索（j–），找到第一个小于key的值，将A\[j\]和A\[i\]互换。  
4）从i开始向后搜索，即由前开始往后搜索（i++），找到第一个大于key的A\[i\]，将A\[i\]和A\[j\]互换。  
5）重复3、4步骤，直到i == j；

例子：  
以初始数组为\[2 4 7 5 8 1 3 6 6\]为例子，算法实现过程如下  
![快速排序][SouthEast]

**快速排序算法分析**  
（1）时间复杂度  
平均情况：  
O(N\*log2N)。  
最坏情况：  
O(N^2)  
最好情况：  
O(N\*log2N)。

（2）空间复杂度  
空间复杂度不是很好计算，递归调用的时候需要复制相应的组，所以最坏为O(N)

（3）稳定性  
快速排序过程中元素会被打乱，所以不是一种稳定的排序算法。

## 实现 ##

**1、golang实现**

package main
    
    import (
        "fmt"
    )
    
    func QuickSort(values []int) {
    
        iLen := len(values)
        if iLen <= 1 {
            return
        }
        //fmt.Println(values)
        head, tail := 0, iLen-1
        value, i := values[0], 1
        for head < tail {
            //元素大于第一个元素，和第i个元素和低tail个元素交换，由于不知道第tail个元素是否
            //小于第一个元素，所以i不增加，tail交换后确定已经大于第一个元素,所以tail减一
            if values[i] > value {
                values[i], values[tail] = values[tail], values[i]
                tail--
            } else { //如果元素不大于第一个元素，则和第一个元素所在的位置交换，交换后第一个元素的位置已经被交换过来的占据
                //第head个元素被第一个元素占据。这时候head要指向下一个，下一个用于交换较小位置也要偏移一个
                values[i], values[head] = values[head], values[i]
                head++
                i++
            }
        }
        QuickSort(values[:head])
        QuickSort(values[head+1:])
        return
    }
    
    func main() {
        values := []int{
       2, 4, 7, 5, 8, 1, 3, 6, 6}
        fmt.Println(values)
        ret := QuickSort(values)
        fmt.Println(ret)
        return
    }

结果

[2 4 7 5 8 1 3 6 6]
    [2 4 7 5 8 1 3 6 6]
    [1]
    [5 8 7 3 6 6 4]
    [4 3]
    [3]
    []
    [6 6 7 8]
    [6]
    [8 7]
    [7]
    []
    [1 2 3 4 5 6 6 7 8]

[SouthEast]: /images/20220605/e5f8ef6469db41e38f348c25a7f848f0.png