算法（一）——快速排序

2019-08-27

前言

这是我的算法整理的第一篇，其实之前已经有在根据《算法图解》进行整理了，但是像二分查找之类的都还算简单，直到最近复习到快速排序，虽然用分治角度重新认识了这个算法，但是感觉细节部分还是有很多讲究，索性写一篇博客整理一下。

算法概述

快速排序的时间复杂度受枢轴选择的影响。
最糟时间复杂度情况为：每次选择的枢轴均为子列表的最值，即每次分解的3部分中有一部分是空表，这样时间复杂度为O(n^2^)（n+n-1+…+1）。
平均时间复杂度为O(nlog n)。
虽然近乎原地，但递归需要栈的支持，最糟空间复杂度的情况下为O(n)，平均空间复杂度为O(log n)。

从分治角度来看

分治即分而治之（Divide and Conquer），简单来说就是把规模较大的问题简化为规模较小的问题进行解决。分治问题的两个要素为：寻找使问题得到解决的基线条件（尽可能简单），以及分解问题或缩小问题规模以达到基线条件的方法。虽然可能并不是很常用到分治这个词，但其实这是一个很常用的思考方式。拿快速排序来说，其基线条件就是表中只含有小于2个元素，而分解问题的方法就是递归地把表分解为3个部分：枢轴pivot，比枢轴小的部分和比枢轴大的部分。

其实到这里以后，用一些便于在线性表中添加元素和合并线性表的语言其实已经可以便捷地实现快排了。核心思想就是：递归地把表分解为3个部分，直到每个表都只有0个或1个元素，然后再把表合并起来。此处给出Java List版的快排代码（笔者对Java不甚了解，现学现卖，若有啰嗦甚至错误之处烦请赐教）：

/**
 * This method uses simple quick sort algorithm to sort a List.
 * That is, create 2 lists in every sort, and at the end of recursion, merge 2 lists together.
 * @param list
 */
public List<Integer> quickSort(List<Integer> list){
    int p = 0; // choose a pivot

    // partition
    List<Integer> listBelow = new ArrayList<>();
    List<Integer> listAbove = new ArrayList<>();
    for (Integer elem:list) {
        if(elem<=list.get(p)) listBelow.add(elem); // elems equal to pivot should either goto listBelow or listAbove
        else listAbove.add(elem);
    }
    listBelow.remove(0); // remove pivot

    // recursion
    if(listBelow.size()>1) // base condition
        listBelow = quickSort(listBelow); // sort listBelow
    if(listAbove.size()>1)
        listAbove = quickSort(listAbove); // sort ListAbove

    // merge
    listBelow.add(list.get(0)); // add pivot
    listBelow.addAll(listAbove);
    return listBelow;
}

但是如果是顺序存储的线性表，如数组就没那么简单了，因为新建数组、合并数组、向数组中添加元素都比较复杂。再加上对表的分解、合并操作其实比较繁琐，时间上不高效。

常见实现

更常用的排序方法需要借助在线性表头尾的两个指针。这种排序方法有两种具体实现：

在线性表头和尾设置两个指针i和j
指定一个枢轴pivot
1. 从i开始向表尾寻找小于（或等于）枢轴的项
2. 从j开始向表头寻找大于枢轴的项
1. 若找到则交换i、j指向的项，从j开始向表头寻找大于（或等于）枢轴的项
2. 若找到则把j指向的项赋给i指向的项，从i开始项表尾寻找小于枢轴的项
1. 以此类推直到i>j为止
2. 以此类推直到i=j为止

暂且把1称为快排的交换方式实现，2称为快排的覆盖方式实现。

void quickSort(int list[], int i, int j){
    // choose a pivot
    int p=i; // choose the first elem **in the current part** as pivot
    int elem = list[p];
    int temp; // used in swapping method
    int start = i;
    int end = j;

    // partition
    if(j==i)
        return;
    // in swapping method, the condition below is j>=i
    while(j>i){
        for(;list[j]>=elem && i<j;j--);
        if(i!=j)
            // here covered pivot first, finally place pivot to where i&j meet.
            // this realization should be based on that **j replace pivot at first**.
            // in swapping method, swap list[i] and list[j].
            list[i] = list[j];
        else break;
        for(;list[i]<=elem && i<j;i++);
        if(i!=j)
        // in swapping method, swap list[i] and list[j].
            list[j] = list[i];
    }
    list[i] = elem; // in swapping method there's no this step.

    // recursion
    if(i>start+1) quickSort(list, start, i-1); // if parameters here and following are both i rather than i-1 & i+1, recursion may not end.
    if(i<end-1) quickSort(list, i+1, end);
}

有几个需要注意的点：

这种实现需要处理数组的一部分，而不是仅仅处理整个数组，所以需要注意各处的具体实现不要写错了。
递归时需要跳过枢轴项，不然可能会死循环。
覆盖方法要求从j开始，第一次交换覆盖掉枢轴项，因此需要保存枢轴的值。
可以看出，覆盖方式要比交换方式稍省时一些。空间复杂度上二者差不多。

zyf的Android学习笔记

未分类

算法（一）——快速排序

前言

算法概述

从分治角度来看

常见实现