知识框架

排序算法概念

算法安稳性

假如待排序表中有两个元素 r1 和 r2，其对应的要害字 key1 = key2,运用某一排序算法后,r1 仍然在 r2 的前面,则这个算法是安稳的,否则是不安稳的。

排序算法的分类

在排序的进程中，依据数据元素是否彻底在内存中，可将排序算法分为两类：

内部排序

内部排序是指在排序期间元素悉数存放在内存中的排序。一般状况下，内部排序算法在履行进程中都要进行两种操作：比较和移动。经过比较两个要害字，确认对应的元素的前后联系，然后经过移动元素以抵达有序。当然，并不是一切的内部排序算法都要依据比较操作，事实上，基数排序就不是依据比较的。 内部排序算法的性能取决于算法的时刻复杂度和空间复杂度，而时刻复杂度一般是由比较和移动的次数来决议的。

外部排序

外部排序是指在排序期间元素无法悉数一起存放在内存中，必须在排序的进程中依据要求不断地在内、外存之间移动的排序。

内部排序

简略排序

挑选排序

算法逻辑

一种最简略的排序算法是这样的：首要，找到数组中最小的那个元素，其次，将它和数组的榜首个元素交流方位（假如榜首个元素便是最小元素那么它就和自己交流）。再次，在剩余的元素中找到最小的元素，将它与数组的第二个元素交流方位。如此往复，直到将整个数组排序。这种方法叫做挑选排序，因为它在不断地挑选剩余元素之中的最小者。（即 先把最小的拿出来，然后把剩余的元素中在把最小的拿出来…）

源码

/**
 * @brief 交流数组中指定方位的两个元素
 *
 * @param i 方针元素
 * @param j 方针元素
 * @param targetArrary  方针数组
 */
static void MySwap(int i, int j, int *targetArrary)
{
    assert(i >= 0 && j >= 0);
    int temp = targetArrary[i];
    targetArrary[i] = targetArrary[j];
    targetArrary[j] = temp;
}
/**
 * @brief 挑选排序
 *
 * @param targetArray 待排序的数组
 * @param arrarySize  数组巨细
 */
static void SelectionSort(int *targetArray, int arrarySize)
{
    /*
     * j是遍历的索引，开端将 j = i；j开端向后不断的遍历，假如最小的元素便是 i，
     * 那么自己和自己交流下方位，
     * targetArrary[i ... arrarySize) 中最小的元素放在 targetArrary[i]的方位上
     * 可是不是自己，将 minIndex指向的元素和 I 指向的元素交流方位;
     *
     * targetArrary[0 ... i) 表明现已有序
     */
    for (int i = 0; i < arrarySize; ++i)
    {
        int minIndex = i;
        /* targetArrary[i ... arrarySize) 是无序状况 */
        for (int j = i; j < arrarySize; ++j)
        {
            /* 寻觅最小的元素 */
            if (targetArray[j] < targetArray[minIndex])
            {
                /* 更新最小元素的index */
                minIndex = j;
            }
        }
        /* 当最小值便是自己时，不需求进行数据的交流 */
        if (i != minIndex)
            MySwap(i, minIndex, targetArray);
    }
}

时刻复杂度

如下图所示，挑选排序的内循环仅仅在比较当时元素与目前已知的最小元素（以及将当时索引加1和检查是否代码越界），这现已简略到了极点。交流元素的代码写在内循环之外，每次交流都能排定一个元素，因而交流的总次数是N。所以算法的时刻功率取决于比较的次数。

• 关于长度为N的数组，挑选排序需求大约N2/2N^2/2N2/2次比较和N次交流

证明：能够经过算法的排序轨道来证明这一点。咱们用一张NxN的表格来表明排序的轨道（见上图），其中每个非灰色字符都表明一次比较。表格中大约一半的元素不是灰色的－即对角线和其上部分的元素。对角线上的每个元素都对应着一次交流。经过查看代码咱们能够更精确地得到，0到N-1的恣意i都会进行一次交流和N-1-i次比较，因而总共有N次交流以及（N-1）＋（N-2）＋＋2＋1＝N（N-1）／2～N2/2N^2/2N2/2次比较。

• 经过代码剖析可知时刻复杂度为 O(N2N^2N2)

1 + 2 + 3 + … + n = 12n2\frac 12n^221​n2 + 12\frac 1221​n

算法特色

总的来说,挑选排序是简略了解和完结的简略算法，它有两个明显的特色：

• 运行时刻和输入无关

为了找出最小的元素而扫描一遍数组并不能为下一遍扫描供给什么信息。这种性质在某些状况下是缺陷，因为运用挑选排序的人或许会惊讶地发现，一个现已有序的数组或是主键悉数持平的数组和一个元素随机摆放的数组所用的排序时刻竟然相同长！咱们将会看到，其他算法会更善于运用输入的初始状况。

• 数据移动是最少

每次交流都会改动两个数组元素的值，因而挑选排序用了N次交流－交流次数和数组的巨细是线性联系。咱们将研究的其他任何算法都不具有这个特征（大部分的增长数量级都是线性对数或是平方级别）。

刺进排序

算法逻辑

通常咱们整扑克牌的方法是一张一张的来，将每一张牌刺进到其他现已有序的牌中的适当方位。在核算机的完结中，为了给要刺进的元素腾出空间，咱们需求将其余一切元素在刺进之前都向右移动一位，这种算法叫做刺进排序。

如下图，关于1到N-1之间的每一个i，将a[i]与a[0]到a[i-1]中比它小的一切元素顺次有序地交流。在索引i由左向右改动的进程中，它左边的元素总是有序的，所以当i抵达数组的右端时排序就完结了。

源码

/**
 * @brief 刺进排序
 *
 * @param targetArray 待排序的数组
 * @param arraySize 数组巨细
 */
static void InsertionSort(int *targetArray, int arraySize){
    /*
     * targetArrary[0 ... i) 表明现已有序
     * targetArrary[i ... n) 表明未排序
     * j是遍历的索引，从i的方位向前检索
     *
     * Note: i = 0 时已排序的数组为空
     */
    for (int i = 0; i < arraySize; ++ i){
        int temp = targetArray[i];
        int j = i;
        /*
         * 将 targetArrary[i]刺进到合适的方位，
         * 将 i 元素的与 i 前面现已排好序的元素逐个进行比较
         */
        for (j = i; j - 1 >= 0 && temp < targetArray[j - 1]; -- j){
            /* 将前面的元素向后移动(运用移动代替元素的交流) */
            targetArray[j] = targetArray[j - 1];
        }
        /* j为当时 targetArrary[i]应该刺进的正确的方位 */
        targetArray[j] = temp;
    }
}

时刻复杂度

如下图，与挑选排序相同，当时索引左边的一切元素都是有序的，但它们的终究方位还不确认，为了给更小的元素腾出空间，它们或许会被移动。可是当索引抵达数组的右端时，数组排序就完结了。

和挑选排序不同的是，刺进排序所需的时刻取决于输入中元素的初始次序。例如，对一个很大且其中的元素现已有序（或挨近有序）的数组进行排序将会比对随机次序的数组或是逆序数组进行排序要快得多。

• 关于随机摆放的长度为N且主键不重复的数组，均匀状况下刺进排序需求～N2/4N^2/4N2/4次比较以及 ～N2/4N^2/4N2/4次交流。最坏状况下需求～N2/2N^2/2N2/2次比较和～N2/2N^2/2N2/2次交流，最好状况下需求N-1次比较和0次交流。(经过代码剖析时刻也为 O(n2)(n^2)(n2))

证明： 经过一个NxN的轨道表能够很简略就得到交流和比较的次数。最坏状况下对角线之下一切的元素都需求移动方位，最好状况下都不需求。关于随机摆放的数组，在均匀状况下每个元素都或许向后移动半个数组的长度，因而交流总数是对角线之下的元素总数的二分之一。

比较的总次数是交流的次数加上一个额定的项，该项为N减去被刺进的元素正好是已知的最小元素的次数。在最坏状况下（逆序数组），这一项相关于总数能够忽略不计；在最好状况下（数组现已有序），这一项等于N-1。

• 刺进排序需求的交流操作和数组中倒置的数量相同，需求的比较次数大于等于倒置的数量，小于等于倒置的数量加上数组的巨细再减一。

证明：每次交流都改动了两个次序倒置的元素的方位，相当于削减了一对倒置，当倒置数量为0时，排序就完结了。每次交流都对应着一次比较，且1到N-1之间的每个i都或许需求一次额定的比较（在a[i]没有抵达数组的左端时）。

倒置指的是数组中的两个次序倒置的元素。

算法特色

考虑一般的状况是部分有序的数组。比如EXAMPLE中有11对倒置：E-A、X-A、X-M、X-P、X-L、X-E、M-L、M-E、P-L、P-E以及L-E。假如数组中倒置的数量小于数组巨细的某个倍数，那么咱们说这个数组是部分有序的。下面是几种典型的部分有序的数组：

• 数组中每个元素间隔它的终究方位都不远；
• 一个有序的大数组接一个小数组；
• 数组中只有几个元素的方位不正确；

刺进排序对这样的数组很有用，而挑选排序则否则。事实上，当倒置的数量很少时，刺进排序很或许比本章中的其他任何算法都要快。

总的来说，刺进排序关于部分有序的数组十分高效，也很合适小规模数组。这很重要，因为这些类型的数组在实践运用中经常出现，而且它们也是高档排序算法的中间进程。

挑选 VS 刺进

挑选排序：在现已排好的有序部分的元素现已是终究的成果；

刺进排序：在现已排好的有序部分的元素不是终究的成果，而是暂时的排序成果；

• 刺进排序关于有序数组来说，时刻复杂度是下降到 O(n), 但一般状况下算法时刻复杂度仍是 O(n2n^2n2)
• 挑选排序时刻复杂度永远是 O(n2n^2n2)

归并排序

算法逻辑

将两个有序的数组归并成一个更大的有序数组。很快人们就依据这个操作发明晰一种简略的递归排序算法：归并排序。要将一个数组排序，能够先（递归地）将它分红两半别离排序，然后将成果归并起来。你将会看到，归并排序最吸引人的性质是它能够确保将恣意长度为N的数组排序所需时刻和$NlogN$成正比；它的主要缺陷则是它所需的额定空间和N成正比。

归并进程

/* 归并排序的伪代码 */
MergeSort(arr, l, r){
/* 待处理的元素为空或不需求再进行排序处理 */
if(l >= r) 
    return;
/* 核算数组的中间方位 */
int mid = (l + r) / 2;
/* 对 arr［l，mid］ 进行排序 */
MergeSort(arr, l, mid);
／* 对 arr［mid ＋ 1，r］进行排序 */
MergeSort(arr, mid + 1, r);
/* 将arr［l，mid］和arr［mid ＋ 1，r］兼并 */
merge(arr, l, mid, r);
}

为什么要进行原地归并？

完结归并的一种直截了当的方法是将两个不同的有序数组归并到第三个数组中，完结的方法很简略，创立一个适当巨细的数组然后将两个输入数组中的元素一个个从小到大放入这个数组中。 可是，当用归并将一个大数组排序时，咱们需求进行很屡次归并，因而在每次归并时都创立一个新数组来存储排序成果会带来问题。咱们更希望有一种能够在原地归并的方法，这样就能够先将前半部分排序，再将后半部分排序，然后在数组中移动元素而不需求运用额定的空间。

源码

归并排序的代码完结能够分为递归方法完结(自顶向下)或是非递归方法完结(自底向上)，完结的核心思维是相同的；总的来说仍是递归的方法完结起来更简略了解。

自顶向下(递归)

/***
 * 兼并两个现已有序的数组到方针数组中，使其全体有序
 * @param dest 方针数组
 * @param source 数据源
 * @param l 数组的最小下标
 * @param h 数组的最大下标
 * @param mid 数据源数组的分界下标，其左右两头的数组都是有序的
 */
static void merge(int *temp, int *source, int l, int h, int mid){
    /* i 和 j 在归并进程中数组的下标 */
    int i = l;
    int j = mid + 1;
    /*
     * COPY 指定规模的数组到temp数组作为暂时数组运用
     * temp的内存空间要大于等于source的内存空间(一次性开辟，防止屡次请求内存)
     * 确保temp和source在[l ... h]规模内的元素相同
     */
    for (int i = l; i <= h; ++i)
        temp[i] = source[i];
    /* 将 source[l ... mid] 和 source[mid + 1 ... h] 归并成一个全体有序的数组*/
    for (int k = l; k <= h; ++k){
        /* 左边的数组元素现已处理完结，将右边的数组元素悉数赋值到方针数组即可 */
        if (i > mid)
            source[k] = temp[j ++];
        /* 右边数组元素现已悉数处理完结，将左边的数组元素悉数赋值到方针数组即可 */
        else if (j > h)
            source[k] = temp[i ++];
        /* 将左边数组元素归并到方针数组 */
        else if (source[i] < temp[j])
            source[k] = temp[i ++];
        /* 将右边数组归并到方针数组 */
        else
            source[k] = temp[j ++];
    }
}
/**
 * 递归算法完结的归并排序
 * @param dest 终究有序的方针数组
 * @param source 待排序的数组
 * @param l
 * @param mid
 * @param h
 */
static void mergeSort(int *temp, int *source, int l, int h){
    if (l >= h)
        return;
    /* (h + l)/2 的核算方法或许超越类型的最大值 */
    int  mid = l + (h - l) / 2;
    /* 排序左边的数组 */
    mergeSort(temp, source, l, mid);
    /* 排序右边的数组 */
    mergeSort(temp, source, mid + 1, h);
    /* 将有序的两个数组merge成一个全体有序的数组 */
    merge(temp, source, l, h, mid);
}

递归归并排序的履行进程

假定数组a[]如下：

要将a[0…15]排序，sort（）方法会调用自己将a[0…7]排序，再在其中调用自己将a[0…3]和a[0…1]排序。在将a[0]和a[1]别离排序之后，终于才会开端将a[0]和a[1]归并（简略起见，咱们在轨道中把对单个元素的数组进行排序的调用省掉了）。第2次归并是a[2]和a[3]，然后是a[0…1]和a[2…3]，以此类推。从这段轨道能够看到，sort()方法的效果其实在于安排屡次merge（）方法调用的正确次序。

算法复杂度

如下图所示，表明数组a[16]递归的树状图。每个结点都表明一个sort()方法经过merge()方法归并而 成的子数组。这棵树正好有n层。关于0到n-1之间的恣意k，自顶向下的第k层有2k2^k2k个子数组，每个数组的长度为2n−k2^{n-k}2n−k，归并最多需求2n−k2^{n-k}2n−k次比较。因而每层的比较次数为2k2^k2k*2n−k2^{n-k}2n−k ＝2n2^n2n，n 层总共为n2n2^n2n ＝ NlgN。

• 关于长度为N的恣意数组，自顶向下的归并排序需求12NlgN\frac{1}{2}NlgN21​NlgN至$NlgN$次比较。

证明：令C(N)表明将一个长度为N的数组排序时所需求的比较次数。咱们有C(0)=C(1)＝0，关于 N＞0.经过递归的sort()方法咱们能够由相应的归纳联系得到比较次数的上限:

C(N) $\le$ C($\lceil N/2\rceil$）+ C($\lfloor N/2\rfloor$) + N

右边的榜首项是将数组的左半部分排序所用的比较次数，第二项是将数组的右半部分排序所用的比较次 数，第三项是归并所用的比较次数,因为归并所需的比较次数最少为$\lfloor N/2\rfloor$(比较左边或右边的数组元组)，比较次数的下限是：

C(N) $\ge$ C($\lceil N/2\rceil$）+ C($\lfloor N/2\rfloor$) + N

当N为2的幂（即N＝2n2^n2n）且等号建立时咱们能够得到一个解。首要，因为$\lceil N/2\rceil$＝$\lfloor N/2\rfloor$＝2n−12^{n-1}2n−1，能够得到：C(2n2^n2n) = 2(C(2n−12^{n-1}2n−1)) + 2n2^n2n

将两头一起除以2n2^n2n可得：C(2n2^n2n)/2n2^n2n = C(2n−12^{n-1}2n−1)/2n−12^{n-1}2n−1 + 1

用这个公式替换右边的榜首项可得: C(2n2^n2n)/2n2^n2n = C(2n−22^{n-2}2n−2)/2n−22^{n-2}2n−2 + 1 + 1

将上一步重复n-1遍可得: C(2n2^n2n)/2n2^n2n = C(202^020)/202^020 + n

将两头一起乘以2n 2^n2n可得: C(N) = C(2n2^n2n) =n2n n2^nn2n =$NlgN$

关于一般的N，得到的准确值要更复杂一些。但对比较次数的上下界不等式运用相同的方法不难证明前面所述的关于恣意N的定论。这个定论关于恣意输入值和次序都建立。

• 关于长度为N的恣意数组，自顶向下的归并排序最多需求拜访数组$6NlgN$次。

证明：每次归并最多需求拜访数组6N次（2N次用来仿制，2N次用来将排好序的元素移动回去，别的 最多比较2N次，因为递归方法完结的mergeSort()中别离对数组的左右别离排序）。

优化

• 能够削减在merge进程对数组元素的COPY

/**
 * @brief 将指定规模内的原数组归并到方针数组中
 *
 * @param dest
 * @param source
 * @param l
 * @param h
 * @param mid
 */
static void merge2(int *dest, int *source, int l, int h, int mid){
    /* i 和 j 在归并进程中数组的下标 */
    int i = l;
    int j = mid + 1;
    /* 将 source[l ... mid] 和 source[mid + 1 ... h] 归并成一个全体有序的数组*/
    for (int k = l; k <= h; ++k){
        /* 左边的数组元素现已处理完结，将右边的数组元素悉数赋值到方针数组即可 */
        if (i > mid)
            dest[k] = source[j ++];
        /* 右边数组元素现已悉数处理完结，将左边的数组元素悉数赋值到方针数组即可 */
        else if (j > h)
            dest[k] = source[i ++];
        /* 将左边数组元素归并到方针数组 */
        else if (source[i] < source[j])
            dest[k] = source[i ++];
        /* 将右边数组归并到方针数组 */
        else
            dest[k] = source[j ++];
    }
}
/**
 * @brief 在mergeSort基础上进行优化,以节约将数组元素仿制到用于归并的辅佐数组所用的时刻（但空间不行）。
 *        要做到这一点咱们要调用两种排序方法:
 *          一种将数据从输入数组排序到辅佐数组，
 *          一种将数据从辅佐数组排序到输入数组。
 *
 * @param dest
 * @param source
 * @param l
 * @param h
 *
 * NOTE:运用 dest 表明原数组， source表明要排序的方针数组，
 *      运用一次性仿制数组的优化后，要在递归调用的每个层次交流输入数组和辅佐数组的角色.
 */
static void mergeSort2(int *dest, int *source, int l, int h){
    if (l >= h)
        return;
    int  mid = l + (h - l) / 2;
    /* 排序左边的数组 */
    mergeSort2(source, dest, l, mid);
    /* 排序右边的数组 */
    mergeSort2(source, dest, mid + 1, h);
    merge2(dest, source, l, h, mid);
}

• 在数组现已有序的状况下，归并排序的时刻复杂度降为O(n)

/**
 * 在原始的mergeSort进行了优化，假如数组全体有序时不在需求进行merge操作
 * @param temp 终究有序的方针数组
 * @param source 待排序的数组
 * @param l
 * @param mid
 * @param h
 */
static void mergeSort3(int *temp, int *source, int l, int h){
    if (l >= h)
        return;
    /* (h + l)/2 的核算方法或许超越类型的最大值 */
    int  mid = l + (h - l) / 2;
    /* 排序左边的数组 */
    mergeSort3(temp, source, l, mid);
    /* 排序右边的数组 */
    mergeSort3(temp, source, mid + 1, h);
    /* 
     * 将有序的两个数组merge成一个全体有序的数组,
     * 假如数组现已有序不在需求merge，时刻复杂度为O(n)
     */
    if (source[mid] > source[mid + 1])
        merge(temp, source, l, h, mid);
}

证明：数组有序的状况下，依据上面的代码可知，sort()进程仅仅处理数组递归成的树的每个节点，不在需求merge进程，那么依据sort()完结逻辑递归构建的树的最下面一层的叶子节点的数量便是数组元素的总个数，倒数第二层节点的个数便是$\lceil N/2\rceil$个，以此类推，直到根节点。所以节点的总数量便是：

1 + N/2 + N/4 … N = N2\frac{N}{2}2N​(1-(12)m){\frac{1}{2}})^m)21​)m)/12\frac{1}{2}21​ < N = O(n)

自低向上(非递归)

递归完结的归并排序是算法规划中分治思维的典型运用。咱们将一个大问题分割成小问题别离处理，然后用一切小问题的答案来处理整个大问题。尽管咱们考虑的问题是归并两个大数组，实践上咱们归并的数组大大都都十分小。
完结归并排序的另一种方法是先归并那些微型数组，然后再成对归并得到的子数组，如此这般，直到咱们将整个数组归并在一起。这种完结方法比标准递归方法所需求的代码量更少。首要咱们进行的是两两归并（把每个元素幻想成一个巨细为1的数组），然后是四四归并（将两个巨细为2的数组归并成一个有4个元素的数组），然后是八八的归并，一直下去。在每一轮归并中，最终一次归并的第二个子数组或许比榜首个子数组要小（但这对merge0）方法不是问题），假如不是的话一切的归并中两个数组巨细都应该相同，而在下一轮中子数组的巨细会翻倍.如下图所示：

/***
 * 兼并两个现已有序的数组到方针数组中，使其全体有序
 * @param dest 方针数组
 * @param source 数据源
 * @param l 数组的最小下标
 * @param h 数组的最大下标
 * @param mid 数据源数组的分界下标，其左右两头的数组都是有序的
 */
static void merge(int *temp, int *source, int l, int h, int mid){
    /* i 和 j 在归并进程中数组的下标 */
    int i = l;
    int j = mid + 1;
    /*
     * COPY 指定规模的数组到temp数组作为暂时数组运用
     * 确保temp和source在[l ... h]规模内的元素相同
     */
    for (int i = l; i <= h; ++i)
        temp[i] = source[i];
    /* 将 source[l ... mid] 和 source[mid + 1 ... h] 归并成一个全体有序的数组*/
    for (int k = l; k <= h; ++k){
        /* 左边的数组元素现已处理完结，将右边的数组元素悉数赋值到方针数组即可 */
        if (i > mid)
            source[k] = temp[j ++];
        /* 右边数组元素现已悉数处理完结，将左边的数组元素悉数赋值到方针数组即可 */
        else if (j > h)
            source[k] = temp[i ++];
        /* 将左边数组元素归并到方针数组 */
        else if (source[i] < temp[j])
            source[k] = temp[i ++];
        /* 将右边数组归并到方针数组 */
        else
            source[k] = temp[j ++];
    }
}
/**
 * @brief 归并排序自底向上的完结方法
 *
 * @param temp merge进程运用的暂时数组
 * @param source 待排序的数组
 * @param l 数组的最小下标
 * @param h 数组的最大下标
 * @param arrSize 数组巨细
 */
static void mergeSortUP(int *temp, int *source, int l, int h, int arrSize){
    /*
     * sz 表明兼并数组的巨细（现已有序），终止条件表明当时兼并数组的巨细是否大于等于方针数组的巨细
     * 小于数组的巨细，兼并区间的长度小于数组的巨细，还需求持续进行
     * 兼并区间长度大于等于arrSize时，变数整个数组现已有序
     */
    for (int sz = 1; sz < arrSize; sz += sz){
        /*
         * i += sz + sz ： 每次处理(兼并)两个sz巨细数组，将其进行merge
         * source[i,i + sz - 1]  source[i + sz, i + sz + sz - 1]
         * 循环持续条件表明:i + sz < arrSize 存在第二个数组，此刻榜首个数组必定存在，这两个空间需求进行兼并
         * i + sz 表明第二个数组的开端的index
         * i 表明遍历兼并的两个区间的开端方位，所以每次向后移动两个sz的巨细
         */
        for (int i = 0; i + sz < arrSize; i += sz + sz){
            /*
             * 优化: source[i,i + sz - 1]  source[i + sz, i + sz + sz - 1] 两个数组是别离有序的，
             * 只有 source[i + sz - 1] > source[i + sz] 进行 merge才有含义
             */
            if(source[i + sz - 1] > source[i + sz]){
                /*
                 * 只能确保 i + sz  没能越界，可是不能确保最终的区间还包含 sz 个元素，
                 * 或许缺乏 sz 个元素（即 i + sz + sz - 1 或许越界）
                 * 当缺乏 sz 个元素时，用实践的长度作为数组的最终的鸿沟
                 */
                merge(temp, source, i,
                      (i + 2 * sz - 1 <= arrSize - 1 ? i + 2 * sz - 1 : arrSize - 1),
                      i + sz - 1);
            }
        }
    }
}

算法复杂度

• 关于长度为N的恣意数组，自底向上的归并排序需求12NlgN\frac{1}{2}NlgN21​NlgN至$NlgN$次比较，最多拜访数组 6NlgN次。

证明: 处理一个数组的遍数正好是$\lceil NlgN\rceil$。每一遍会拜访数组6N次，比较次 数在$N/2$和$N$之间。

快速排序

它或许是运用最广泛的排序算法了。快速排序流行的原因是它完结简略、适用于各种不同的输入数据且在一般运用中比其他排序算法都要快得多。快速排序引人注目的特色包含它是原地排序（只需求一个很小的辅佐栈），且将长度为N的数组排序所需的时刻和$NlgN$成正比。别的，快速排序的内循环比大大都排序算法都要短小，这意味着它无论是在理论上仍是在实践中都要更快。

算法原理

快速排序是一种分治的排序算法。它将一个数组分红两个子数组，将两部分独登时排序。快速排序和归并排序是互补的：归并排序将数组分红两个子数组别离排序，并将有序的子数组归并以将整个数组排序；而快速排序将数组排序的方法则是当两个子数组都有序时整个数组也就自然有序了。在榜首种状况中，递归调用发生在处理整个数组之前；在第二种状况中，递归调用发生在处理整个数组之后。在归并排序中，一个数组被等分为两半；在快速排序中，切分（partition）的方位取决于数组的内容(切分元素左边的数组元素不大于切分元素，右面数组元素不小于切分元素)。快速排序的大致进程如下图所示：

快排的切分

经过上面快排的原理发现，要完快排首要需求完结切分方法。[假定一切的元素都不相同]一般战略是先随意地取arr[lo]作为切分元素(v表明)，即那个将会被排定的元素，然后咱们逐渐遍历右边没有被拜访的元素，在遍历的进程中整理数组，使其一部分是小于arr[lo]的，另一部分是大于arr[lo]；其中大于v和小于v的分界点运用j表明(即arr[j]),当时正在拜访的元素运用i表明(即arr[i]为当时正在拜访的元素)。如下图所示：

经过上面快排的原理发现，要完快排首要需求完结切分方法。一般战略是先随意地取arr[lo]作为切分元素，即那个将会被排定的元素，然后咱们从数组的左端开端向右扫描直到找到一个大于等于它的元素，再从数组的右端开端向左扫描直到找到一个小于等于它的元素。这两个元素显然是没有排定的，因而咱们交流它们的方位。如此持续，咱们就能够确保左指针i的左边元素都不大于切分元素，右指针j的右侧元素都不小于切分元素。当两个指针相遇时，咱们只需求将切分元素arr[lo]和左子数组最右侧的元素（arr[j]）交流然后回来j即可。切分方法的大致进程如下图所示。

切分完结

/**
 * @brief 交流数组中i和j两个方位的元素
 *
 * @param arr
 * @param i
 * @param j
 */
static void swap(int *arr, int i, int j){
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}
/**
 * @brief 将数组指定规模内的元素切分红小于切分元素和大于等于切分元素两部分
 *
 * @param arr 数据源
 * @param lo 数组最小下标
 * @param hi 数组最大下标
 * @return int 回来切分元素的数组下标方位
 */
static int partition(int *arr, int lo, int hi){
    int j = lo;
    /*
     * arr[l + 1 ... j] < v , arr[j + 1 ... i - 1] >= v
     * 默许数组的榜首个元素作为数组的切分元素
     * i 表明当时正在处理的元素下标，j 表明小于v的数组元素最大下标
     */
    for (int i = lo + 1; i <= hi; ++i){
        /*
         * 当时元素小于v，将小于v的j向右移动1位，然后交流当时元素和
         * arr[j](原arr[j + 1])方位的元素
         */
        if (arr[i] < arr[lo]){
            ++j;
            swap(arr, i, j);
        }
    }
    /*
     * 交流切分元素和arr[j]元素的方位，使数组arr[lo ... j - 1] < v
     * arr[j + 1 ... hi] >= v
     */
    swap(arr, lo, j);
    /* j指向的是切分元素的方位 */
    return j;
}

切分进程

这段代码按照arr[lo]的值v进行切分。在for循环中，arr[i]小于v时咱们增大j，然后交流arr[j]和arr[i]，arr[i]大于等于v时咱们进行 i++，当i遍历到数组最终方位时，切分结束,最终交流切分元素和arr[j]的元素，来确保i左边的元素都小于v，j右侧的元素都不小于v。如下图的比如：

快排的完结

/**
 * @brief 快速排序的递归完结
 *
 * @param arr 待排序的数组
 * @param lo 数组的最小下标
 * @param hi 数组的最大下标
 */
static void quickSort(int *arr, int lo, int hi){
    /* 待处理的数组巨细为 1(一个元素不在需求排序，自身现已有序) */
    if (lo >= hi)
        return;
    /* 获取切分元素的数组下标,arr[p]自身现已有序 */
    int p = partition(arr, lo, hi);
    /* 对 arr[p] 左边的数组元素进行排序 */
    quickSort(arr, lo, p - 1);
    /* 对 arr[p] 右面的数组元素进行排序 */
    quickSort(arr, p + 1, hi);
}

咱们便是经过递归地调用切分来排序的。因为切分进程总是能排定一个元素，用归纳法不难证明递归能够正确地将数组排序：假如左子数组和右子数组都是有序的，那么由左子数组（有序且没有任何元素大于切分元素）、切分元素和右子数组（有序且没有任何元素小于切分元素）组成的成果也一定是有序的。

快排的进程

快速排序递归地将子数组arr[lo … hi]排序，先用partition方法将arr[j]放到一个合适方位，然后再用递归调用将其他方位的元素排序。

优化1

经过上面快排的完结进程能够发现，当输入的数组是彻底有序时，算法的时刻复杂度会成为 O(n2)O(n^2)O(n2)，递归的深度为O(n)，因为当数组彻底有序时，切分数组进程默许是挑选的数组的榜首个元素作为切分点对数组进行切分的，可是数组有序时每次总是回来数组的榜首个元素，此刻小于v(arr[lo])的数组部分是空，大于等于v的数组部分是N-1个元素；依此类推，全体履行的指令个数是 $n+(n-1)+(n-2)+\dots 1$

• 上述的问题应该如何处理呢？

咱们在切分元组时能够随机准则切分元素，而不是默许的运用数组的榜首元素作为切分的元素，这样能够有用的防止上述的问题。尽管随机化今后仍是存在每次都随机到数组的榜首的方位作为切分元素，可是概率是极低的(几乎不或许发生): 1n∗1n−1∗…1=1n!\frac {1}{n} * \frac {1}{n-1} * … 1 = \frac{1}{n!}n1​∗n−11​∗…1=n!1​
当N十分小的时分，概率仍是比较大的，可是假如数据量十分小时退化成O(n2)O(n^2)O(n2)也是无所谓的。 随机化是找不到一个确认的测试用例使其算法退化成O(n2)O(n^2)O(n2)，可是假如指定数组中间或其他某个方位的元素作为切分点时是能够找到测试用例使其退化成O(n2)O(n^2)O(n2)

为快排添加随机化

/**
 * @brief 将数组指定规模内的元素切分红小于切分元素和大于等于切分元素两部分
 *        添加随机化选取切分元素的进程，防止有序数组算法时刻复杂度下降到O(n2)
 *
 * @param arr 数据源
 * @param lo 数组最小下标
 * @param hi 数组最大下标
 * @return int 回来切分元素的数组下标方位
 */
static int partitionOpt1(int *arr, int lo, int hi){
    /* 获取随机数组小标作为切分的元组 */
    int randP = MyRandSpecial(lo, hi);
    /* 交流arr[lo]和arr[randP]元素的方位，后边仍是原始的逻辑 */
    swap(arr, lo, randP);
    int j = lo;
    /*
     * arr[l + 1 ... j] < v , arr[j + 1 ... i - 1] >= v
     * 默许数组的榜首个元素作为数组的切分元素
     * i 表明当时正在处理的元素下标，j 表明小于v的数组元素最大下标
     */
    for (int i = lo + 1; i <= hi; ++i){
        /*
         * 当时元素小于v，将小于v的j向右移动1位，然后交流当时元素和
         * arr[j](原arr[j + 1])方位的元素
         */
        if (arr[i] < arr[lo]){
            ++j;
            swap(arr, i, j);
        }
    }
    /*
     * 交流切分元素和arr[j]元素的方位，使数组arr[lo ... j - 1] < v
     * arr[j + 1 ... hi] >= v
     */
    swap(arr, lo, j);
    /* j指向的是切分元素的方位 */
    return j;
}

优化2

前面介绍的快排仍是存在可优化空间的，之间是假定数组的元素都是不同的，那么假如数组中的一切的元素都是相同的呢？会有什么问题吗？

• 假定一个数组的一切的元素都是0，切分进程如下：将数组分红2部分并回来j指向的方位(该为数组的榜首个元素），即该切分的成果便是切分元素(arr[j])边没有任何元素而右边有 $N-1$ 个元素，再次对 $N-1$ 个元素进行上面相同的方法切分，顺次递推不断地进行递归切分，所以算法的时刻复杂度将会退化为 O(n2)O(n^2)O(n2)。[推算进程参考有序数组的切分]

或许大家还或许存在疑问，上面的切分逻辑是假如当时正在遍历的元素大于等于切分元素时将切分元素右面(arr[j+1])的区间添加一个元素(即i++操作)关于数组元素相同的状况是有问题的，那么咱们将切分的逻辑改成当正在遍历的元素小于等于切分元素时添加切分元素左边的区间(即j++操作)，切分的进程如下：

经过上面的切分进程能够知道改动切分的逻辑后仍是存在问题的，与改动之前的差异便是之前的逻辑每次切分都回来数组的榜首个元素且切分元素左边0个元素，切分元素右面$N-1$个元素；之后的逻辑是每次切分都回来数组的最终一个元素且切分元素左边是$N-1$个元素，切分元素右面是0个元素，终究的复杂度仍是O(n2)O(n^2)O(n2)。

处理上述的问题能够运用双路快排的思维，其实双路指的便是切分数组元素的进程与之前的切分进程时存在差异的，但做的工作同样是先随机挑选一个元素作为切分的元素，然后依据切分元素为鸿沟将数组分红两部分，一部分是小于切分元素的，别的一部分是大于切分元素的，要害点是将等于切分元素的部分向方法将其平分在切分元素的两头。

双路快速排序

全体的算法思路和之前相同，不同的是数组的切分逻辑发生了改动。下面将介绍双路快排的partition的进程:

1. 随机选取一个元素作为切分数组，然后跟数组的榜首个方位的元素进行交流；
2. 设置i和j别离作为遍历数组的变量，当arr[i]大于等于切分元素时暂不在持续向后遍历，当arr[j]小于等于切分元素时暂不向前持续遍历；
3. 交流arr[i]和arr[j]的元素，然后别离履行 i++ 和 j– 的操作；该交流元素的进程其实便是将等于切分元素的元素均匀分在切分点的两头的进程

/**
 * @brief 假如数组中存在很多相同的元素时，运用partitionOpt1将会使算法的复杂度下降到O(n2)
 *        针对该问题的处理思路是将相同的元素均匀分到切分元素的两头
 *
 * @param arr 数组源
 * @param lo 指定数组最小下标
 * @param hi 指定数组最大下标
 * @return int 切分元素的数组下标
 */
static int partitionOpt2(int *arr, int lo, int hi)
{
    /* 获取随机数组小标作为切分的元组 */
    int randP = MyRandSpecial(lo, hi);
    /* 交流arr[lo]和arr[randP]元素的方位，后边仍是原始的逻辑 */
    swap(arr, lo, randP);
    /*
     * 初始时 arr[lo + 1 ... i - 1] --> arr[lo + 1, lo] 左鸿沟大于右鸿沟阐明数组为空
     * 初始时 arr[j + 1 ... hi] --> arr[hi + 1, hi] 左鸿沟大于右鸿沟阐明数组为空
     */
    int i = lo + 1;
    int j = hi;
    /* arr[lo + 1 ... i - 1] <= V  arr[j + 1 ... hi] >= V */
    while (true)
    {
        /* i 早年向后遍历 */
        while (i <= j && arr[i] < arr[lo])
            ++i;
        /* j 从后向前遍历 */
        while (j >= i && arr[j] > arr[lo])
            --j;
        /*
         * i > j 阐明当时一切的元素都处理完了
         * i = j 阐明当时还有没有处理的数组元素需求进行处理，arr[i] <= V arr[j] >= V
         * 阐明i和j指向的是相同的元素，不必再处理了
         */
        if (i >= j)
            break;
        /*
         * 此刻i指向了归于切分元素右端的元素,j指向了归于切分元素左端的元素
         * 交流两个元素,别离移动两个遍历的指针 i 和 j
         */
        swap(arr, i, j);
        ++i;
        --j;
    }
    /* 将切分元素放到正确的方位 */
    swap(arr, lo, j);
    return j;
}
/**
 * @brief 快速排序的递归完结
 *
 * @param arr 待排序的数组
 * @param lo 数组的最小下标
 * @param hi 数组的最大下标
 */
static void quickSort(int *arr, int lo, int hi){
    /* 待处理的数组巨细为 1(一个元素不在需求排序，自身现已有序) */
    if (lo >= hi)
        return;
    /* 获取切分元素的数组下标,arr[p]自身现已有序 */
    int p = partitionOpt2(arr, lo, hi);
    /* 对 arr[p] 左边的数组元素进行排序 */
    quickSort(arr, lo, p - 1);
    /* 对 arr[p] 右面的数组元素进行排序 */
    quickSort(arr, p + 1, hi);
}

双路快排进程

用双路快排处理相同元素的数组的效果如下图所示，将相同的元素散布到切分元素的两头

优化3

上面介绍的双路快排能够处理重复元素的数组，可是切分点两头都是相同的元素，因而没有必要再次处理切分完结的元素，为了防止上述的问题，咱们将采用3ways快排：

三路快速排序

三路快排不需求处理与切分点相同的元素，只需对小于和大于切分点的元素部分进行排序，它从左到右遍历数组一次，维护一个指针lt使得a[lo…lt-1]中的元素都小于V，一个指针gt使得a[gt＋1…hi]中的元素都大于V，一个指针i使得a[lt…i-1]中的元素都等于V，a[i…gt]中的元素都还未确认，如下图所示，一开端i和lo持平，咱们对a[i]进行三路比较来直接处理以下状况：

• a[i]小于v，将 a[lt]和a[i]交流，将lt和i加一；
• a[i]大于v，将 a[gt]和a[i]交流，将gt减一；
• a[i]等于v，将i加一。

/**
 * @brief 3路快排
 *
 * @param arr 待排序的数组
 * @param lo 数组的最小下标
 * @param hi 数组的最大下标
 */
static void quickSortBy3Ways(int *arr, int lo, int hi){
    if (lo >= hi)
        return;
    /* 获取随机数组小标作为切分的元组 */
    int randP = MyRandSpecial(lo, hi);
    /* 交流arr[lo]和arr[randP]元素的方位，后边仍是原始的逻辑 */
    swap(arr, lo, randP);
    /**
     * arr[lo + 1, lt] < V
     * arr[lt + 1, i - 1] == V
     * arr[gt, hi] > V
     * arr[i] 表明当时正在处理的元素，具体归于哪个部分还未知
     */
    int lt = lo + 1;
    int gt = hi + 1;
    int i = lo + 1;
    /*
     * 依据切分元素将数组切分红<V，==V和>V三个部分;
     *
     * i == gt 时一切的数组元素现已处理完结，因为arr[gt, hi]是闭区间
     */
    while (i < gt)
    {
        /* arr[lo + 1, lt] < V */
        if (arr[i] < arr[lo]){
            ++lt;
            /* 将原arr[lt + 1]元素切换到了原arr[i]的方位，<V的区间扩展了 */
            swap(arr, i, lt);
            ++i;
        }
        /* arr[gt, hi] > V */
        else if (arr[i] > arr[lo]){
            --gt;
            /* i指向的是原arr[gt-1]的元素，是未处理的，一切不需求++i操作 */
            swap(arr, i, gt);
        }
        /* arr[lo + 1, lt] == V */
        else{
            ++i;
        }
    }
    /*
     * 将切分元素放到正确的方位
     * arr[lo, lt - 1] < V
     * arr[lt, gt - 1] == V
     * arr[gt, hi] > V
     */
    swap(arr, lt, lo);
    /* 对小于V部分元素进行排序 */
    quickSortBy3Ways(arr, lo, lt - 1);
    /* 对大于V部分元素进行排序 */
    quickSortBy3Ways(arr, gt, hi);
}

时刻复杂度剖析

快速排序是每次随机选定一个切分元素，依据切分元素将数组分红两部分，可是这两部分的元素并不一定是均匀的，或许一端的元素多，另一端的元素少； 算法的复杂度应该是最坏的状况，快排的最坏为O(n2)O(n^2)O(n2)，可是概率是十分低的(假如数据量是各位数时即便为O(n2)O(n^2)O(n2)也是提现不出来)； 快排与之前的排序算法不同的一点是它是一种随机的算法，关于随机算法的时刻复杂的剖析不能依据最坏的状况来剖析，应该运用数学希望进行剖析，在切分数组进程尽管会不均匀的将数组分红两部分，可是全体因为每个元素被选定的几率是持平的，从数学的希望上来看是将数组平分；所以层数的希望值是 $O(logn)$,在每层的操作是$O(n)$，全体的时刻复杂度是$O(nlogn)$ [具体的数学推导能够参考《算法导论》]

… 更新 …

外部排序

参考：

• 算法（第4版）作者:[[美] Robert Sedgewick]/[[美] Kevin Wayne]