快速排序

基本思想

通过一趟排序将要排序的序列分割成独立的两部分
其中一部分的所有数据都比另一部分的所有数据都要小
再按此方法对两部分分别进行快速排序
最终达到整个数据序列有序

流程

设定一个分界值，通过该分界值将数组分成左右两部分
将大于或等于分界值的数据集中到数组右边，小于分界值的集中到数组左边
然后，左边和右边的数据独立排序，对于左侧的数组数据，又可以取一个分界值，将该部分的数据分成左右两部分，同样左边放置较小值，右边放置较大值。右侧的数组也做类似处理
重复上述过程，可以看出，这是一个递归定义。通过递归将左侧部分排好序，再递归将右侧部分排好序。当左右两个部分数据都排序完成后，整个数组的排序也就完成了。

第一次选取5为分界值

第二次右边选择6，左边选择3为分界值

第三次左1选择2，右1选择4 右2选择7作为分界值

第四次右选择9作为分界值

代码实现：

def quick_sort(alist, start, end):
    """快速排序"""

    # 递归的结束条件
    if start >= end:
        return

    # 界限值
    mid = alist[start]

    # 左右游标
    left = start
    right = end

    while left < right:
        # 从右边开始找寻小于mid的值，归类到左边
        while alist[right] >= mid and left < right:
            right -= 1
        alist[left] = alist[right]

        # 从左边边开始找寻大于mid的值，归类到右边
        while alist[left] < mid and left < right:
            left += 1
        alist[right] = alist[left]

    # 循环一旦结束了，证明找到了mid应该在的位置
    alist[left] = mid

    # 递归操作
    quick_sort(alist, start, left - 1)
    quick_sort(alist, right + 1, end)
    
if __name__ == '__main__':
    alist = [1, 2, 100, 50, 1000, 1, 1]
    quick_sort(alist, 0, len(alist) - 1)
    print(alist)

Java版实现

public class QickSortTest {
    public static void main(String[] args) {
        int[] arr = {6, 1, 2, 7, 9, 3, 4, 5, 10, 8};
        quickSort(arr, 0, arr.length - 1);
        System.out.println(Arrays.toString(arr));
    }

    public static void quickSort(int[] arr, int left, int right){ // left 为红色箭头，right为蓝色箭头
        // 递归结束条件
        if(right < left){
            return;
        }
        int left0 = left; //0
        int right0 = right; //9
        // 计算出基准
        int baseNumber = arr[left0]; // arr[0]
        while (left != right){
            // 1. 从右开始查找比基准数小的
            while (arr[right] >= baseNumber && right > left){
                right--;
            }
            //2. 从左开始查找比基准数大的
            while (arr[left] <= baseNumber && right > left){
                left++;
            }
            // 3. 交换两个值的位置
            int temp = arr[left];
            arr[left] = arr[right];
            arr[right] = temp;
        }
        // 基准归位
        int temp = arr[left];
        arr[left] = arr[left0];
        arr[left0] = temp;

        // 递归调用自己，将左边排好
        quickSort(arr, left0, left - 1);
        // 递归调用自己，将右边排好
        quickSort(arr, left+1, right0);
    }
}

快速排序的稳定性

最差时间复杂度： $O (n^{2})$

最优时间复杂度： $O (n l o g_{2} (n))$ , 每次分界值都刚好能把数列一分为二

快速排序是一个不稳定算法。