排序算法汇总

2019-01-06 本文已影响12人 Teci

简单来说，时间复杂度指的是语句执行次数，空间复杂度指的是算法所占的存储空间

时间复杂度
计算时间复杂度的方法：

用常数1代替运行时间中的所有加法常数
修改后的运行次数函数中，只保留最高阶项
去除最高阶项的系数

即O(4n^2+2n)只保留O(n^2)

那么nlog(n)是什么情况呢, 看下面这个例子:

for（int i=1;i<=n;i++）

{

for(int j=1;j<=n;j+=i)

{

..... //复杂度为O(1);

}

求该程序段的时间复杂度。

可以看出: (1) 当i=1时，需要执行n次；

(2) 当i=2时，需要执行n/2次；

(3) 当i=3时，需要执行n/3次；

.............

(4) 当i=n-1时，需要执行n/n-1次；

(5) 当i=n时，需要执行n/n次；

每次的时间复杂度为O（1），则总共的时间复杂度为n(1 +1/2+1/3 +1/4 + 1/5+ 1/6+1/7+1/8 +...1/n), 经过欧拉证明, 得到:

1+1/2+1/3+1/4+...+1/n= ln(n+1)+r(r为常量)

则总共的时间复杂度为：

n(1 +1/2+1/3 +1/4 + 1/5+ 1/6+1/7+1/8 +...1/n)

=n(ln(n+1) + r)

=nln(n+1)+r*n

即复杂度为nlog(n)

同理, 一个数的二分查找的时间复杂度是O(log2(N))

那么O(n²)是什么情况呢, 看下面这个例子:

(1) 当i=1时，需要执行n次；

(2) 当i=2时，需要执行2次；

(3) 当i=3时，需要执行3次；

.............

(4) 当i=n-1时，需要执行n-1次；

(5) 当i=n时，需要执行n次；

那么总的次数就是

1+2+3+…+n-2+n-1+n

根据等差数列求和得到 N²/2+N+1 , 省略低阶项省略系数后即可得 O(N²)

根据排序过程中元素是否完全保存在内存中，可以将算法分为内部排序（internal sort）和外部排序（external sort）。

下图是各个排序算法的复杂度:

排序算法复杂度汇总

1. 冒泡排序

冒泡排序算法的基本思想为：假如待排序线性表的长度为 nn，从前往后两两比较相邻元素的关键字，若 a_{i-1}>a_iai−1>ai，则交换它们，直到线性表比较完成。每趟交换以后最后一个元素一定是最大的，不再参与下一趟交换。也就是对于第 ii 趟交换，只需要比较到 a_{n-i}an−i 即可。直到一趟比较内没有进行交换，算法结束。时间复杂度和插入排序一样，也为 $O(n^2)$ 。

冒泡排序算法的运作如下：

比较相邻的元素，如果前一个比后一个大，就把它们两个调换位置。
对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。看下面动图, 最大的元素会被一次一次往后移动, 这步做完后，最后的元素会是最大的数。
针对所有的元素重复以上的步骤，除了最后一个。
持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

D4C88B8CC620AF6AF67C33910899FCF7.gif

#这个冒泡排序法实现的很凝练, 用了倒数的range的方式, 并且用len(chaos_list)-1避免了之后判断chaos_list[i+1]是否超出范围的麻烦
def bubble_sort(chaos_list):
    for cur_len in range(len(chaos_list)-1,0,-1):
        for i in range(cur_len):
            if chaos_list[i]>chaos_list[i+1]:
                chaos_list[i],chaos_list[i+1]=chaos_list[i+1],chaos_list[i]
    return chaos_list

//这个是正序版的
void sort() {
        for(int i=0;i<length-1;i++){
            bool swapped=false;
            for(int j=0;j<length-i-1;j++){
                if(data[j]>data[j+1]){
                    swap(data[j],data[j+1]);
                    swapped=true;
                }
            }
            if(swapped==false){//过程中一次都没交换说明之前的每个数字的顺序都是对的
                break;
            }
        }
    }

//这是带模板倒序版的, 接收两个迭代器, 一个是begin一个是end
template<typename T>
void BubbleSort(T first, T last)
{
    /* 如果在迭代器的范围里面没有至少两个数字的话，那可以直接返回，不需要排序 */
    if (first == last || next(first) == last) return;
    for(auto i=first;i!=prev(last);i++){
        for(auto j=prev(last);j!=i;j--){
            auto k=prev(j);
            if(*j<*k){
                auto t=*j;
                *j=*k;
                *k=t;
            }
        }
    }
}

//这个是倒序版的
void bubble_sort() {
        for(int i=length-1;i>0;i--){//此处选择i>0, 当i=0时没有排序的意义了
            bool swapped=false;
            for(int j=0;j<i;j++){
                if(data[j]>data[j+1]){
                    swap(data[j],data[j+1]);
                    swapped=true;
                }
            }
            if(!swapped){
                break;
            }
        }
    }

2. 鸡尾酒排序

鸡尾酒排序，也叫定向冒泡排序，是冒泡排序的一种改进。此算法与冒泡排序的不同处在于从低到高然后从高到低，而冒泡排序则仅从低到高去比较序列里的每个元素。他可以得到比冒泡排序稍微好一点的效能。

3. 选择排序

选择排序的思想是，每趟从线性表的待排序区域选取关键字最小的元素，将其放到已排序区域的最后。因为每趟可以让待排序区域的元素数量减少一个，所以总共需要 n-1n−1 趟操作就可以将整个线性表排序完成。很显然，选择排序的时间复杂度也是 $O(n^2)$ 。

在每次查找关键字最小的元素时，可以使用堆对效率进行优化，使用堆来优化的选择排序就是堆排序。由于一共要查找 nn 次最小值，每次查找的时间为O(logn)，所以堆排序的时间复杂度为 O(nlogn)。

选择排序也是一种简单直观的排序算法。它的工作原理很容易理解：初始时在序列中找到最小（大）元素，放到序列的起始位置作为已排序序列；然后，再从剩余未排序元素中继续寻找最小（大）元素，放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

注意选择排序与冒泡排序的区别：冒泡排序通过依次交换相邻两个顺序不合法的元素位置，从而将当前最小（大）元素放到合适的位置；而选择排序每遍历一次都记住了当前最小（大）元素的位置，最后仅需一次交换操作即可将其放到合适的位置。

F20B8898585B3CA03843D93CE2C35A68.gif

选择排序是不稳定的排序算法，不稳定发生在最小元素与A[i]交换的时刻。

比如序列：{ 5, 8, 5, 2, 9 }，一次选择的最小元素是2，然后把2和第一个5进行交换，从而改变了两个元素5的相对次序。

其中稳定性指的是: 假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的。

稳定性的意义:

1、如果只是简单的进行数字的排序，那么稳定性将毫无意义。
2、如果排序的内容仅仅是一个复杂对象的某一个数字属性，那么稳定性依旧将毫无意义（所谓的交换操作的开销已经算在算法的开销内了，如果嫌弃这种开销，不如换算法好了？）
3、如果要排序的内容是一个复杂对象的多个数字属性，但是其原本的初始顺序毫无意义，那么稳定性依旧将毫无意义。
4、除非要排序的内容是一个复杂对象的多个数字属性，且其原本的初始顺序存在意义，那么我们需要在二次排序的基础上保持原有排序的意义，才需要使用到稳定性的算法，例如要排序的内容是一组原本按照价格高低排序的对象，如今需要按照销量高低排序，使用稳定性算法，可以使得想同销量的对象依旧保持着价格高低的排序展现，只有销量不同的才会重新排序。（当然，如果需求不需要保持初始的排序意义，那么使用稳定性算法依旧将毫无意义）。

void sort() {
        int temp;
        for(int i=0;i<length-1;i++){
            temp=i;
            for(int j=i+1;j<length;j++){ //此处选择i+1就可以了, 因为一开始将temp初始化为i, 所以其实i已经比过了
                if(data[temp]>data[j]){
                    temp=j;
                }
            }
            if(temp!=i){
                swap(data[i],data[temp]);
            }
        }
    }

def choice_sort(chaos_list):
    length=len(chaos_list)
    for i in range(length):
        cur_min_ind,cur_min_value=i,chaos_list[i]
        for j in range(i,length):
            if chaos_list[j]<cur_min_value:
                cur_min_ind,cur_min_value=j,chaos_list[j]
        chaos_list[i],chaos_list[cur_min_ind]=chaos_list[cur_min_ind],chaos_list[i]
    return chaos_list
    
#另一种写法
def choice(chaos_list):
    for i in range(len(chaos_list)):
        index=min(range(i,len(chaos_list)),key=lambda x:chaos_list[x])
        chaos_list[index],chaos_list[i]=chaos_list[i],chaos_list[index]
    return chaos_list

4. 插入排序

插入排序每次插入的时间复杂度为 O(n)，一共执行 n-1次，因此总体时间复杂度为 $O(n^2)$ 。在插入时查找插入位置的过程可以使用折半查找算法将查找位置的复杂度优化到 $O(logn)$ ，但因为还需要 $O(n)$ 的时间复杂度来在顺序表上执行移动操作，所以总体时间复杂度依然是 $O(n^2)$ 。

对于未排序数据，在已排序序列(左手已经排好序的手牌)中从后向前扫描，找到相应位置并插入。

插入排序在实现上，通常采用in-place排序（即只需用到O(1)的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。

具体算法描述如下：

从第一个元素开始，该元素可以认为已经被排序
取出下一个元素，在已经排序的元素序列中从后向前扫描
如果该元素（已排序）大于新元素，将该元素移到下一位置
重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
将新元素插入到该位置后
重复步骤2~5

对序列{ 6, 5, 3, 1, 8, 7, 2, 4 }进行插入排序的实现过程如下:

6E67D1C722106442B422EE53E98575B3.gif

插入排序不适合对于数据量比较大的排序应用。但是，如果需要排序的数据量很小，比如量级小于千，那么插入排序还是一个不错的选择。插入排序在工业级库中也有着广泛的应用，在STL的sort算法和stdlib的qsort算法中，都将插入排序作为快速排序的补充，用于少量元素的排序（通常为8个或以下）。

对于插入排序，如果比较操作的代价比交换操作大的话，可以采用二分查找法来减少比较操作的次数，我们称为二分插入排序。

当n较大时，二分插入排序的比较次数比直接插入排序的最差情况好得多，但比直接插入排序的最好情况要差，所当以元素初始序列已经接近升序时，直接插入排序比二分插入排序比较次数少。二分插入排序元素移动次数与直接插入排序相同，依赖于元素初始序列。

void sort(int data[],int length){
    for(int i=0;i<length;i++){
        for(int j=i-1;j>=0;j--){
            if(data[j]>data[j+1]){
                swap(data[j],data[j+1]);
            }
            else{
                break;
            }
        }
    }
}

#这是最优的插入排序!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
def insert_sort(chaos_list):
    for i in range(1,len(chaos_list)):
        j=i
        temp=chaos_list[i]
        while j-1>=0 and temp<chaos_list[j-1]:
            chaos_list[j]=chaos_list[j-1]
            j-=1
        chaos_list[j]=temp
    return chaos_list

#这里实现的是稳定的, 如果把第七行改为小于等于就是不稳定的
#这种插入排序效率太低, 因为如果往list中间插入元素的话, 插入位置的后续元素都需要挪动, 所以不好
def insert_sort(chaos_list):
    sorted_list=[chaos_list.pop(0)]
    for c in chaos_list:
        flag=True
        for ind,s in enumerate(sorted_list):
            if c<s:
                sorted_list.insert(ind,c)
                flag=False
                break
        if flag:
            sorted_list.append(c)
    return sorted_list
    
#或者完全按照图中的顺序
def insert_sort(chaos_list):
    sorted_list=[chaos_list.pop(0)]
    for c in chaos_list:
        ind=len(sorted_list)-1
        while ind>=0 and c<sorted_list[ind]:
            ind-=1
        if ind==len(sorted_list)-1:
            sorted_list.append(c)
        else:
            sorted_list.insert(ind+1,c)
    return sorted_list

5. 希尔排序

希尔排序，也叫递减增量排序，是插入排序的一种更高效的改进版本。希尔排序是不稳定的排序算法。

希尔排序是基于插入排序的以下两点性质而提出改进方法的：

插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率
但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位

希尔排序通过将比较的全部元素分为几个区域来提升插入排序的性能。这样可以让一个元素可以一次性地朝最终位置前进一大步。然后算法再取越来越小的步长进行排序，算法的最后一步就是普通的插入排序，但是到了这步，需排序的数据几乎是已排好的了（此时插入排序较快）。
假设有一个很小的数据在一个已按升序排好序的数组的末端。如果用复杂度为O(n^2)的排序（冒泡排序或直接插入排序），可能会进行n次的比较和交换才能将该数据移至正确位置。而希尔排序会用较大的步长移动数据，所以小数据只需进行少数比较和交换即可到正确位置。

我们来看下希尔排序的基本步骤，在此我们选择增量gap=length/2，缩小增量继续以gap = gap/2的方式，这种增量选择我们可以用一个序列来表示，{n/2,(n/2)/2...1}，称为增量序列。希尔排序的增量序列的选择与证明是个数学难题，我们选择的这个增量序列是比较常用的，也是希尔建议的增量，称为希尔增量，但其实这个增量序列不是最优的。此处我们做示例使用希尔增量。

C52E08027910D98F78EE1D225CF03A8B.png

def shell_sort(chaos_list):
    n = len(chaos_list)
    gap = n/2
    while gap > 0:

        for i in range(gap,n):
            temp = chaos_list[i]
            j = i
            print(temp)
            #当gap=n/2时, 此时就相当于每次for循环往后挪一位就比较两个数chaos_list[j-gap]和chaos_list[j]的大小
            #当gap=n/4时, 因为前面的都排好序了, 所以将后面的调换位置就行, 具体请看print出来的结果
            #原版此处是while而不是if, 不过看起来while跟if功能差不多, while每次也只循环一次
            while  j >= gap and chaos_list[j-gap] >temp:
                #当gap=n/2时, 这一步只是将较大的那个值复制给了后边, 并没有交换两个值, 较小的那个值在后面会被复制到前面
                #当gap小于n/2时, 这个while是逐个向前替换, chaos_list[i]经过最初的替换后之后就不变了， 之后变得都是其前面的元素
                #前面的元素一个接一个被不断的替换, 最后到了一个chaos[j-list]<temp的位置后把temp的值换上去
                #此处用的算法完全就是选择排序那一部分的那个动图, 是从后往前的顺序
                
                #假设现在当前序列为2413, 那么首先在对4排序, i-gap得到2, 4比2大所以不换位置, 接着对1排序, i-gap是4, 那么序列变为2143, 再i-gap得到2, 那么序列变为1243, 依次类推, 在这种情况下, 如果用if, 序列变为2143的时候就不会接着往下变了
                #此处就相当于插入排序
                chaos_list[j] = chaos_list[j-gap]

                j -= gap
            # 当gap=n/2时, 较小的那个值被放在了前面
            chaos_list[j] = temp
            print(chaos_list)
        print('########')
        gap /= 2
    return chaos_list
    
#注意第13行的while不能改成if, 否则对[ 12, 34, 54, 2, 3,-5,192,0,0,0,-0,13] 的排序结果就是:
>>> 0 -5 0 0 0 2 3 12 13 34 54 192

6. 堆排序

堆排序是指利用堆这种数据结构所设计的一种选择排序算法。堆是一种近似完全二叉树的结构（通常堆是通过一维数组来实现的），并满足性质：以最大堆(也叫大根堆、大顶堆) 为例，其中父结点的值总是大于它的孩子节点。

我们可以很容易的定义堆排序的过程：

由输入的无序数组构造一个最大堆，作为初始的无序区
把堆顶元素（最大值）和堆尾元素互换
把堆（无序区）的尺寸缩小1，并调用heapify(A, 0)从新的堆顶元素开始进行堆调整
重复步骤2，直到堆的尺寸为1

堆排序是不稳定的排序算法，不稳定发生在堆顶元素与A[i]交换的时刻。

比如序列：{ 9, 5, 7, 5 }，堆顶元素是9，堆排序下一步将9和第二个5进行交换，得到序列 { 5, 5, 7, 9 }，再进行堆调整得到{ 7, 5, 5, 9 }，重复之前的操作最后得到{ 5, 5, 7, 9 }从而改变了两个5的相对次序。

下图为怎么把一个无序的数组构造成一个大堆顶结构的数组的过程，注意其是从下到上，从右到左，从右边第一个非叶子节点开始构建的。(即将列表按顺序画出一棵树状图)

其中堆的每次创建重构花费 $O(logn)$ ，需要创建n次, 最差、最优平均时间复杂度都为 $O(nlogn)$

步骤一构造初始堆。将给定无序序列构造成一个大顶堆（一般升序采用大顶堆，降序采用小顶堆)。

a.假设给定无序序列结构如下

[初始无序序列结构]

2.此时我们从最后一个非叶子结点开始（叶结点自然不用调整，第一个非叶子结点 arr.length/2-1=5/2-1=1，也就是下面的6结点），从左至右，从下至上进行调整。

第一次

4.找到第二个非叶节点4，由于[4,9,8]中9元素最大，4和9交换。

第二次

这时，交换导致了子根[4,5,6]结构混乱，继续调整，[4,5,6]中6最大，交换4和6。

第三次

此时，我们就将一个无需序列构造成了一个大顶堆。

步骤二将堆顶元素与末尾元素进行交换，使末尾元素最大。然后继续调整堆，再将堆顶元素与末尾元素交换，得到第二大元素。如此反复进行交换、重建、交换。

a.将堆顶元素9和末尾元素4进行交换

交换9和4

b.重新调整结构，使其继续满足堆定义

重新调整结构

c.再将堆顶元素8与末尾元素5进行交换，得到第二大元素8.

交换8和5

后续过程，继续进行调整，交换，如此反复进行，最终使得整个序列有序

3EC855099CCC0F48097A9A1BBFF26DE8.png

def heap_sort(chaos_list):
    #heapify是对一个小的二叉树, 即包含一个父节点和一个或两个子节点的树, 对其构造大顶堆模型
    #后来一次阶一次调用这个heapify函数来对一个一个小的二叉树进行构建
    #注意每个节点的值都是chaos_list中的下标, 而不是具体需要排序的数
    #注意这个n很重要
    def heapify(chaos_list, n, i):
        largest = i # Initialize largest as root
        l = 2 * i + 1     # left = 2*i + 1
        r = 2 * i + 2     # right = 2*i + 2

        #找出两个子节点中的最大值
        if l < n and chaos_list[i] < chaos_list[l]:
            largest = l
        if r < n and chaos_list[largest] < chaos_list[r]:
            largest = r
        #如果找出的最大值不是当前父节点所对应的值, 那么将父节点和最大值所对应的下标交换
        if largest != i:
            chaos_list[i],chaos_list[largest] = chaos_list[largest],chaos_list[i] # swap
            #递归调用一次是确保置换后, 子树的子树能满足大顶堆的要求, 所以又把当前子树作为父节点, 重新调用heapify, 确保子树的子树经过置换后依然满足要求
            #这么一层一层迭代下去, 每置换一次就往下迭代一次
            heapify(chaos_list, n, largest)

    #下面是主函数, 负责调用heapify的
    n = len(chaos_list)
    #首先将整个chaos_list中的一个一个子二叉树输入到heapify中, range选择从后往前是确保从树的底部开始构造
    #这样最终的结果才是满足大顶堆的要求
    #其中i可以从n取起而不会报list out of range的错是因为在heapify中当i=n时, 无论l和r都是不满足小于n的条件的, 所以根本不会调用chaos_list[i]
    #当然此处的n改为n-1也完全没关系
    for i in range(n, -1, -1):
        heapify(chaos_list, n, i)

    #此时从底部开始,将序列的最大值放到最后, 即chaos_list[i]的位置, 随着i--, 最大值一个接一个被拍到了最后
    for i in range(n-1, 0, -1):
        #由于是大顶堆, 所以每次交换并经过heapify后chaos_list[0]都是在0到i这个范围内的序列中的最大的数
        #如动图一样, 将最大的这个数放到最后
        chaos_list[i], chaos_list[0] = chaos_list[0], chaos_list[i] # swap
        print(chaos_list)
        #将其调整为大顶堆模式, 确保chaos_list[0]是[0,i]范围的序列中的最大值
        #注意此处一定要将大顶堆限制在[0,i]的范围内, 不然刚抽取出来的最大值又被放到大顶堆的起始了!!!!!!!
        heapify(chaos_list, i, 0)
        print(chaos_list)
        print('#####################')
    return chaos_list

7. 归并排序

对于归并排序，若当前要排序的区间为 $a_0...a_{n-1}$ ，则首先让 $a_0...a_{\frac{n-1}{2}}$ 和 $a_{\frac{n-1}{2}+1}...a_{n-1}$ 这两个区间内的元素有序，再将这两个区间合并成一个更大的有序区间，直到整个线性表都被排序完成。

归并排序一共需要进行 $O(logn)$ 层归并操作，每层归并操作的总时间复杂度为 $O(n)$ ，因此总体的时间复杂度为 $O(nlogn)$ 。和其他排序有所不同，为了实现归并操作，每次合并都需要开辟额外的空间来临时保存合并后的排序结果，总共需要开辟 nn 个元素的空间，所以归并排序的空间复杂度为 $O(n)$ 。

归并排序是创建在归并操作上的一种有效的排序算法，效率为 $O(nlogn)$ ，1945年由冯·诺伊曼首次提出。

归并排序的实现分为递归实现与非递归(迭代)实现。递归实现的归并排序是算法设计中分治策略的典型应用，我们将一个大问题分割成小问题分别解决，然后用所有小问题的答案来解决整个大问题。非递归(迭代)实现的归并排序首先进行是两两归并，然后四四归并，然后是八八归并，一直下去直到归并了整个数组。

归并排序算法主要依赖归并(Merge)操作。归并操作指的是将两个已经排序的序列合并成一个序列的操作，归并操作步骤如下：

申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
设定两个指针，最初位置分别为两个已经排序序列的起始位置
比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
重复步骤3直到某一指针到达序列尾
将另一序列剩下的所有元素直接复制到合并序列尾

对序列{ 6, 5, 3, 1, 8, 7, 2, 4 }进行归并排序的实例如下

归并排序流程

#include <iostream>
#include <cstring>
using std::cin;
using std::cout;
using std::endl;
class Vector {
private:
    int size, length;
    int *data, *temp;
    void merge_sort(int l,int r){
        if(l==r){
            return;
        }
        int mid=(l+r)/2;
        merge_sort(l,mid);
        merge_sort(mid+1,r);
        //经过上面两个merge后默认区间[l,mid]和[mid,r]内部元素的顺序都已经整理好了
        int x=l,y=mid+1,loc=l;
        while(x<=mid||y<=r){ //此处解决的是two pointer问题
            if(x<=mid&&(y>r||data[x]<=data[y])){//当y>r的时候, 就不用判断后面的data[x]<=data[y]了, (y>r||data[x]<=data[y])这部分直接输出true, 这样防止了溢出的可能, 即不会尝试访问data[y],而当y>时直接令temp[loc]=data[x];
                temp[loc]=data[x];
                x++;
            }
            else{//因为while循环判断的是x和y中间有一个在界内, 所以当x>mid时肯定y<=r, 或者就是x<=mid, 但是data[x]>data[y];所以无论哪种情况此处都应该是temp[loc]=data[y];
                temp[loc]=data[y];
                y++;
            }
            loc++;
        }
        for(int i=l;i<=r;i++){
            data[i]=temp[i];
        }
        
    }
public:
    Vector(int input_size) {
        size = input_size;
        length = 0;
        data = new int[size];
        temp = new int[size];
    }
    ~Vector() {
        delete[] data;
        delete[] temp;
    }
    bool insert(int loc, int value) {
        if (loc < 0 || loc > length) {
            return false;
        }
        if (length >= size) {
            return false;
        }
        for (int i = length; i > loc; --i) {
            data[i] = data[i - 1];
        }
        data[loc] = value;
        length++;
        return true;
    }
    void print() {
        for (int i = 0; i < length; ++i) {
            if (i > 0) {
                cout << " ";
            }
            cout << data[i];
        }
        cout << endl;
    }
    void sort() {
        merge_sort(0,length-1);
        
    }
};
int main() {
    int n;
    cin >> n;
    Vector arr(n);
    for (int i = 0; i < n; ++i) {
        int x;
        cin >> x;
        arr.insert(i, x);
    }
    arr.sort();
    arr.print();
    return 0;
}

#首先定义将两个序列聚合成一个的函数
def merge(chaos_list, l, m, r):
    n1 = m - l + 1
    n2 = r- m
    #此处是m+1的原因是recursion_helper中m是等于(l+(r-1))/2, 其中r减去了1
    #注意, 此处的切片赋值不是将列表的ref赋值过去, 而是将列表中的元素赋值过去
    L=chaos_list[l:m+1]
    #此处的是r+1是因为从最初调用的时候就用的len(chaos_list)-1
    R=chaos_list[m+1:r+1]

    i = 0
    j = 0
    #因为i和j相当于两个移动的pointer, 此时需要另外一个index指向安放两个array中当前最大值的位置
    k = l
    #因为两个需要合并的array内部都是升序, 所以只需要比较两个array中第一个元素的大小, 小的那个放到k所在的位置
    #正常来说应该把两个array中第一个元素较小的那个pop出来, 下一次接着比较两个arrya中第一个元素的大小即可
    #但此处没有pop, 而是用的two pointer方法, 往后移一位, 将pointer所指的位置当做新的第一个元素
    while i < n1 and j < n2 :
        if L[i] <= R[j]:
            #因为L和R用的是切片赋值, 所以改变chaos_list中元素的值不会影响到L和R中的值
            chaos_list[k] = L[i]
            i += 1
        else:
            chaos_list[k] = R[j]
            j += 1
        k += 1

    #当一个array已经用完了, 另外一个array剩下的值全部都拼接到输出结果的末尾
    while i < n1:
        chaos_list[k] = L[i]
        i += 1
        k += 1
    while j < n2:
        chaos_list[k] = R[j]
        j += 1
        k += 1


def merge_sort(chaos_list):
    def recursion_helper(l,r):
        if l < r:
            # Same as (l+r)/2, but avoids overflow for large l and h
            #将待排序的列表一分为二, 得到中间点
            m = (l+(r-1))/2

            #将一分为二的列表前后两半分别再次各自一分为二
            recursion_helper( l, m)
            recursion_helper( m+1, r)
            merge(chaos_list, l, m, r)
    recursion_helper(0,len(chaos_list)-1)
    return chaos_list

8. 快速排序

快速排序是目前应用最广泛的排序算法之一。它的基本思想是，每次从待排序区间选取一个元素（我们在后面的课程中都是选取第一个）作为基准记录，所有比基准记录小的元素都在基准记录的左边，而所有比基准记录大的元素都在基准记录的右边。之后分别对基准记录的左边和右边两个区间进行快速排序，直至将整个线性表排序完成。

快速排序的时间复杂度不是稳定的，可以证明快速排序的平均时间复杂度为 $O(nlogn)$ ，最坏情况为 $O(n^2)$ ，可以通过随机选择基准记录来尽可能避免最坏情况的出现。

有没有既不浪费空间又可以快一点的排序算法呢？那就是“快速排序”。

下面大部分内容转载自 https://www.cnblogs.com/ahalei/p/3568434.html

假设我们现在对“6 1 2 7 9 3 4 5 10 8”这个10个数进行排序。首先在这个序列中随便找一个数作为基准数（不要被这个名词吓到了，就是一个用来参照的数，待会你就知道它用来做啥的了）。为了方便，就让第一个数6作为基准数吧。接下来，需要将这个序列中所有比基准数大的数放在6的右边，比基准数小的数放在6的左边，类似下面这种排列：

3 1 2 5 4 6 9 7 10 8

在初始状态下，数字6在序列的第1位。我们的目标是将6挪到序列中间的某个位置，假设这个位置是k。现在就需要寻找这个k，并且以第k位为分界点，左边的数都小于等于6，右边的数都大于等于6。想一想，你有办法可以做到这点吗？

方法其实很简单：分别从初始序列“6 1 2 7 9 3 4 5 10 8”两端开始“探测”。先从右往左找一个小于6的数，再从左往右找一个大于6的数，然后交换他们。这里可以用两个变量i和j，分别指向序列最左边和最右边。我们为这两个变量起个好听的名字“哨兵i”和“哨兵j”。刚开始的时候让哨兵i指向序列的最左边（即i=1），指向数字6。让哨兵j指向序列的最右边（即=10），指向数字。

开始

首先哨兵j开始出动。因为此处设置的基准数是最左边的数，所以需要让哨兵j先出动，这一点非常重要（请自己想一想为什么）。哨兵j一步一步地向左挪动（即j--），直到找到一个小于6的数停下来。接下来哨兵i再一步一步向右挪动（即i++），直到找到一个数大于6的数停下来。最后哨兵j停在了数字5面前，哨兵i停在了数字7面前。

交换

交换后

现在交换哨兵i和哨兵j所指向的元素的值。交换之后的序列如下：

6 1 2 5 9 3 4 7 10 8

到此，第一次交换结束。接下来开始哨兵j继续向左挪动（再友情提醒，每次必须是哨兵j先出发）。他发现了4（比基准数6要小，满足要求）之后停了下来。哨兵i也继续向右挪动的，他发现了9（比基准数6要大，满足要求）之后停了下来。此时再次进行交换，交换之后的序列如下：

第二次交换

6 1 2 5 4 3 9 7 10 8

第二次交换结束，“探测”继续。哨兵j继续向左挪动，他发现了3（比基准数6要小，满足要求）之后又停了下来。哨兵i继续向右移动，糟啦！此时哨兵i和哨兵j相遇了，哨兵i和哨兵j都走到3面前。说明此时“探测”结束。我们将基准数6和3进行交换。交换之后的序列如下：

3 1 2 5 4 6 9 7 10 8

第一轮最后一次交换

到此第一轮“探测”真正结束。此时以基准数6为分界点，6左边的数都小于等于6，6右边的数都大于等于6。回顾一下刚才的过程，其实哨兵j的使命就是要找小于基准数的数，而哨兵i的使命就是要找大于基准数的数，直到i和j碰头为止。

OK，解释完毕。现在基准数6已经归位，它正好处在序列的第6位。此时我们已经将原来的序列，以6为分界点拆分成了两个序列，左边的序列是“3 1 2 5 4”，右边的序列是“9 7 10 8”。接下来还需要分别处理这两个序列。因为6左边和右边的序列目前都还是很混乱的。不过不要紧，我们已经掌握了方法，接下来只要模拟刚才的方法分别处理6左边和右边的序列即可。现在先来处理6左边的序列现吧。

左边的序列是“3 1 2 5 4”。请将这个序列以3为基准数进行调整，使得3左边的数都小于等于3，3右边的数都大于等于3。好了开始动笔吧

如果你模拟的没有错，调整完毕之后的序列的顺序应该是：

2 1 3 5 4

OK，现在3已经归位。接下来需要处理3左边的序列“2 1”和右边的序列“5 4”。对序列“2 1”以2为基准数进行调整，处理完毕之后的序列为“1 2”，到此2已经归位。序列“1”只有一个数，也不需要进行任何处理。至此我们对序列“2 1”已全部处理完毕，得到序列是“1 2”。序列“5 4”的处理也仿照此方法，最后得到的序列如下：

1 2 3 4 5 6 9 7 10 8

对于序列“9 7 10 8”也模拟刚才的过程，直到不可拆分出新的子序列为止。最终将会得到这样的序列，如下

1 2 3 4 5 6 7 8 9 10

到此，排序完全结束。细心的同学可能已经发现，快速排序的每一轮处理其实就是将这一轮的基准数归位，直到所有的数都归位为止，排序就结束了。

#是two_pointer的理念
def two_pointer(chaos_list,start,end):
    #将第一个元素作为基准点
    benchmark=start
    while start!=end:
        #注意此处必须是while不能是if, 因为要确保右pointer要一直往左走直到遇到了比benchmark小的
        #而且此处要加上start!=end, 虽然在上面已经判断了一遍了, 但随着while都走动说不定会end<start
        while not chaos_list[end]<chaos_list[benchmark] and start!=end:
            end-=1
        while not chaos_list[start]>chaos_list[benchmark] and start!=end:
            start+=1
        if chaos_list[end]<chaos_list[benchmark] and chaos_list[start]>chaos_list[benchmark]:
            chaos_list[start],chaos_list[end]=chaos_list[end],chaos_list[start]
    #将第一个元素即作为基准的元素与两个pointer相遇点上的元素交换
    chaos_list[benchmark],chaos_list[start]=chaos_list[start],chaos_list[benchmark]
    return start


def quick_sort(chaos_list):
    if not chaos_list:return []
    def helper(start,end):
        #每次返回index的位置, 然后基于index将其分为两半, 不把index包进去
        #针对分开的两半分别调用递归
        index=two_pointer(chaos_list,start,end)
        if index>start+1:
            helper(start,index)
        if index<end-1:
            helper(index+1,end)

    start,end=0,len(chaos_list)-1
    helper(start,end)
    return chaos_list
    
    
    
#简易版写法
def quick_sort(chaos_list):
    length=len(chaos_list)
    
    def helper(l,r):
        ptr1,ptr2=l,r
        while ptr1<ptr2:
            #注意此处一定是要大于等于号, 如果是大于号的话会陷入死循环, 譬如假如输入为[5,3,1,6,7,8,2,5], 其中l的值等于r的值,这时如果是小于号ptr2就不会移动
            while ptr1<ptr2 and chaos_list[ptr2]>=chaos_list[l]:
                ptr2-=1
            #同理此处一定要是小于等于
            while ptr1<ptr2 and chaos_list[ptr1]<=chaos_list[l]:
                ptr1+=1
            if chaos_list[ptr1]>chaos_list[l] and chaos_list[ptr2]<chaos_list[l]:
                chaos_list[ptr1],chaos_list[ptr2]=chaos_list[ptr2],chaos_list[ptr1]
        chaos_list[l],chaos_list[ptr1]=chaos_list[ptr1],chaos_list[l]
        return ptr1
        
    def recursion_helper(l,r):
        index=helper(l,r)
        if index>l+1:
            helper(l,index)
        if index<r-1:
            helper(index+1,r)
            
    recursion_helper(0,len(chaos_list)-1)
    return chaos_list

除此之外, 另一种快速排序是每次跟基准线所在位置互换元素, 即:

#include <iostream>
#include <cstring>
using std::cin;
using std::cout;
using std::endl;
using std::swap;
class Vector {
private:
    int size, length;
    int *data;
    void quick_sort(int left,int right){
        if(left>right){
            return;
        }
        int pivot=data[left],low=left,high=right;
        while(low<high){
             while(low<high&&data[high]>=pivot){//此处必须包含等于号, 要不不会移动
                high--;
            }
            data[low]=data[high];//如果没找到比pivot小的, 此时经过上面的循环后, high=low, 所以此步无伤大雅
            while(low<high&&data[low]<=pivot){
                low++;
            }
            data[high]=data[low];
        }
        data[low]=pivot;//基准数应该放在左标记low对应的位置上，当然也是右标记high对应的位置上，因为此时low等于high。
          quick_sort(left,low-1);
        quick_sort(low+1,right);
    }
public:
    Vector(int input_size) {
        size = input_size;
        length = 0;
        data = new int[size];
    }
    ~Vector() {
        delete[] data;
    }
    bool insert(int loc, int value) {
        if (loc < 0 || loc > length) {
            return false;
        }
        if (length >= size) {
            return false;
        }
        for (int i = length; i > loc; --i) {
            data[i] = data[i - 1];
        }
        data[loc] = value;
        length++;
        return true;
    }
    void print() {
        for (int i = 0; i < length; ++i) {
            if (i > 0) {
                cout << " ";
            }
            cout << data[i];
        }
        cout << endl;
    }
    void sort() {
        quick_sort(0,length-1);
    }
};
int main() {
    int n;
    cin >> n;
    Vector arr(n);
    for (int i = 0; i < n; ++i) {
        int x;
        cin >> x;
        arr.insert(i, x);
    }
    arr.sort();
    arr.print();
    return 0;
}

此文与于一年前所写, 文中很多文字引用的出处尝试找却没找到, 若发现我哪部分引用了却未注明来源, 恳请告知我即刻修改。