排序-快速排序

快排的基本思想

该方法基于分治的策略，基本思想是：
1．先从数列中取出一个数作为主元。
2．分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。
3．再对左右区间重复第二步，直到各区间只有一个数。

快速排序的最好的情况就是：每次取的主元，恰好平均将数组分成两个长度相同的子数组，此时的时间复杂度为O(nlogn).

主元的选择

很容易想到，直接选择第一个元素作为主元，这种对于一个已经排序的数组而言，由于每次它的左半部分没有元素，所以选了一个元素作为主元以后，对剩余的n-1个元素递归，最终时间复杂度是$O(n^2)$

其他的策略：

• 一种策略就是随机选择，rand()函数需要花时间
• 另一种策略也是经常使用的：取头、中、尾的中位数

上述流程在处理的过程中有一些更加灵活的tip，当left，center，right从小到大排完序后，我们将center（主元）放到right的左边，因为center肯定比left大，比right小，所以划分的时候，left和right不用再划分了，只需要考虑[left+1, right-2]这个区间的划分就可以了。

具体的执行过程：
假定如下是选完主元之后的数组，6为主元，因为6右边的那个元素一定比6大，所以不考虑，而left肯定比6小也不考虑，下图中是区间[left+1, right-1]，其中right-1位置放的是6（主元）。

• 1：首先我们定义i,j分别指向left+1, right-2
• 2：i指针的元素如果比6小，i++，如果大于6则停止
• 3：right指针的元素如果比6大，j–，如果小于6则停止
• 4：如果i<j，i与j指针指的元素交换位置，然后返回步骤2
• 5：如果i>j，表明此时已经划分好，i所指的位置是第一个大于6的位置，令i位置的元素与6交换
• 6：对[left, i-1]区间进行划分
• 7：对[i, right]区间进行划分
  

这里有几个点需要注意：
如果有元素正好等于主元怎么办，最好的方法就是停下来进行交换（该算法是不稳定的）。因为对于全为1的一个数组而言，我们利用快排时，此时每次找到的主元都会将数组平均分成两部分，此时时间复杂度为O(nlogn)。而如果遇到了元素等于主元，此时不理它，继续移动指针，那么会使i指到数组最后的位置，此时数组只划分了一个子数组，子数组长度为n-1，此时的时间复杂度为$O(n^2)$（类似于排好序的数组，每次选取第一个元素为主元的情况）。

对于小规模数据排序时：相比快速排序，其效果不如插入排序，因为快速排序使用的是递归，开销相对大。因此可以定义一个cutoff阈值，对于数据规模比小于该阈值，使用插入排序，数据规模大于该阈值时，再使用快速排序。

算法实现

下述代码没有设置阈值，上述的算法伪代码中没有递归终止的条件设置，主要是因为当计算规模小时，调用插入排序，所以进入插入排序了，然后return。

#include<stdio.h>
#include<iostream>
#include<algorithm>
using namespace std;
int getPivot(int a[], int left, int right);
void quickSort(int a[], int left, int right);
void Quick_Sort2(int a[], int N);

int main(void)
{
    
     int a[10] = {
    8, 1, 4, 9, 0, 3, 5, 2, 7, 6};
     Quick_Sort2(a, 10);
     for(int i=0; i<10; i++)
          cout<<a[i]<<" ";
     return 0;
}
int getPivot(int a[], int left, int right)
{
    
     int center = (left+right)/2;
     if(a[left] > a[center])
          swap(a[left], a[center]);
     if(a[left] > a[right])
          swap(a[left], a[right]);
     if(a[center] > a[right])
          swap(a[center], a[right]);
     swap(a[center], a[right-1]);
     return a[right-1];
}
void quickSort(int a[], int left, int right)
{
    
     if(right - left < 1)
          return;
     int pivot = getPivot(a, left, right);
     int i = left;
     int j = right-1;
     while(i < j) //i如果不比j小没必要进入下面的循环，这主要对应两个元素的情况，这种情况在选主元的时候已经排好序了。
     {
    
          while(a[++i] < pivot);
          while(a[--j] > pivot);
          if(i < j)
          {
    
               swap(a[i], a[j]);
          }
          else break;
     }
     swap(a[i], a[right-1]);
     quickSort(a, left, i-1);
     quickSort(a, i+1, right);

}
void Quick_Sort2(int a[], int N)
{
    
     quickSort(a, 0, N-1);
}

python版本的代码

第一种方式：和上面c版本的代码对应

def getPivot(a, left, right):
    """选择主元：前中后三个位置的中位数，并将主元放到right的前一个位置"""
    center = (left + right) // 2
    if a[left] > a[center]:
        a[left], a[center] = a[center], a[left]
    if a[left] > a[right]:
        a[left], a[right] = a[right], a[left]
    if a[center] > a[right]:
        a[center], a[right] = a[right], a[center]

    a[center], a[right - 1] = a[right - 1], a[center]
    return a[right - 1]


def qsort2(a, left, right):
    """排序，left与right为数组左右索引位置"""
    # 递归终止条件
    if right - left < 1:
        return None
    # 选取主元
    pivot = getPivot(a, left, right)
    i = left
    j = right - 1
    # 根据主元的选取规则，主元放在了right-1位置，left的位置小于right-1
    # 对于两个元素的情况，主元的位置和left的位置相同，right-1等于left，此时选主元的时候已经排好序，故对于这种情况不进入循环中
    while i < j:
        # 因为i表示的left位置一定比主元小，right-1的位置为主元，right比主元大
        # 所以我们需要比较的是[left+1, right-1]的元素
        i += 1
        j -= 1
        while a[i] < pivot:
            i += 1
        while a[j] > pivot:
            j -= 1
        if i < j:
            a[i], a[j] = a[j], a[i]
    # 循环终止时，j指向小于pivot的元素，i指向大于pivot的元素
    # 由于我们最开始把pivot放到了right-1的位置，故把right-1和i的位置交换，此时划分就完成了
    a[i], a[right - 1] = a[right - 1], a[i]
    qsort2(a, left, i - 1)
    qsort2(a, i + 1, right)

第二种方式：选择最左边的元素为主元，这种情况对于已有序的数组而言，效率没有第一种高。

def qsort(a, left, right):
    if right - left < 1:
        return None
    pivot = a[left]
    i = left
    j = right+1
    while True:
        i += 1
        j -= 1
        while i < j and a[i] < pivot:  # i < j，避免当两个元素时，i本身为left+1，此时等于right，如果++，会导致出界
            i += 1
        while a[j] > pivot:  # 最多在最左边停下，不会越界，所以不用加i<j
            j -= 1
        if i < j:
            a[i], a[j] = a[j], a[i]
        else:
            break
    a[left], a[j] = a[j], a[left]
    qsort(a, left, j - 1)
    qsort(a, j + 1, right)

更多可以参考：
https://www.runoob.com/w3cnote/quick-sort.html