排序算法有很多，包括插入排序，冒泡排序，堆排序，归并排序，选择排序，计数排序，基数排序，桶排序，快速排序等。
十种常见排序算法可以分为两大类：
非线性时间比较类排序：通过比较来决定元素间的相对次序，由于其时间复杂度不能突破O(nlogn)，因此称为非线性时间比较类排序。
线性时间非比较类排序：不通过比较来决定元素间的相对次序，它可以突破基于比较排序的时间下界，以线性时间运行，因此称为线性时间非比较类排序。

算法优劣评价术语
稳定性:

稳定：如果 a 原本在 b 前面，而 a = b，排序之后 a 仍然在 b 的前面；

不稳定：如果 a 原本在 b 的前面，而 a = b，排序之后 a 可能会出现在 b 的后面；
排序方式:

内排序：所有排序操作都在内存中完成，占用常数内存，不占用额外内存。

外排序：由于数据太大，因此把数据放在磁盘中，而排序通过磁盘和内存的数据传输才能进行，占用额外内存。
复杂度:

时间复杂度: 一个算法执行所耗费的时间。

空间复杂度: 运行完一个程序所需内存的大小。




冒泡排序
冒泡排序（Bubble Sort）是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。
这个算法的名字由来是因为越大的元素会经由交换慢慢“浮”到数列的顶端，故名。
依次比较相邻的两个数，将小数放在前面，大数放在后面。即在第一趟：首先比较第1个和第2个数，将小数放前，大数放后。然后比较第2个数和第3个数，将小数放前，大数放后，如此继续，直至比较最后两个数，将小数放前，大数放后。至此第一趟结束，将最大的数放到了最后。
在第二趟：仍从第一对数开始比较（因为可能由于第2个数和第3个数的交换，使得第1个数不再小于第2个数），将小数放前，大数放后，一直比较到倒数第二个数（倒数第一的位置上已经是最大的），第二趟结束，在倒数第二的位置上得到一个新的最大数（其实在整个数列中是第二大的数）。如此下去，重复以上过程，直至最终完成排序。
由于在排序过程中总是小数往前放，大数往后放，相当于气泡往上升，所以称作冒泡排序。
选择排序
选择排序（Selection sort）是一种简单直观的排序算法。它的工作原理如下。 首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素， 然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。 选择排序的思想其实和冒泡排序有点类似，都是在一次排序后把最小的元素放到最前面。但是过程不同， 冒泡排序是通过相邻的比较和交换。而选择排序是通过对整体的选择。
插入排序
有一个已经有序的数据序列，要求在这个已经排好的数据序列中插入一个数，但要求插入后此数据序列仍然有序，这个时候就要用到一种新的排序方法–插入排序法,插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中，从而得到一个新的、个数加一的有序数据，算法适用于少量数据的排序，时间复杂度为O(n^2)。是稳定的排序方法。插入算法把要排序的数组分成两部分:第一部分包含了这个数组的所有元素，但将最后一个元素除外(让数组多一个空间才有插入的位置)，而第二部分就只包含这一个元素(即待插入元素)。在第一部分排序完成后，再将这个最后元素插入到已排好序的第一部分中。
插入排序的基本思想是:每步将一个待排序的纪录，按其关键码值的大小插入前面已经排序的文件中适当位置上，直到全部插入完为止。
它的 工作原理是通过构建有序序列，对于未排序数据， 在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用in-place排序 （即只需用到O(1)的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位， 为最新元素提供插入空间。

1.从第一个元素开始，该元素可以认为已经被排序

2.取出下一个元素，在已经排序的元素序列中从后向前扫描

3.如果该元素（已排序）大于新元素，将该元素移到下一位置

4.将新元素插入到该位置后
快速排序
快速排序(Quicksort)是对冒泡排序的一种改进。
快速排序由C. A. R. Hoare在1962年提出。它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
快速排序（英语：Quicksort），又称划分交换排序（partition-exchange sort）， 一种排序算法， 最早由东尼·霍尔提出。在平均状况下，排序n个项目要Ο(n log n)次比较。在最坏状况下则需要Ο(n2)次比较， 但这种状况并不常见。事实上，快速排序通常明显比其他Ο(n log n)演算法更快， 因为它的内部循环（inner loop）可以在大部分的架构上很有效率地被实现出来。 快速排序使用分治法（Divide and conquer）策略来把一个序列（list）分为两个子序列（sub-lists）。
步骤为：

从数列中挑出一个元素，称为"基准"（pivot），

重新排序数列，所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准后面（相同的数可以到任一边）。在这个分割结束之后，该基准就处于数列的中间位置。这个称为分割（partition）操作。

递归地（recursively）把小于基准值元素的子数列和大于基准值元素的子数列排序。

递归到最底部时，数列的大小是零或一，也就是已经排序好了。这个演算法一定会结束，因为在每次的迭代（iteration）中，它至少会把一个元素摆到它最后的位置去。
换一种表述：
快速排序的基本思想是，通过一轮的排序将序列分割成独立的两部分，其中一部分序列的关键字（这里主要用值来表示）均比另一部分关键字小。继续对长度较短的序列进行同样的分割，最后到达整体有序。在排序过程中，由于已经分开的两部分的元素不需要进行比较，故减少了比较次数，降低了排序时间。
详细描述：首先在要排序的序列 a 中选取一个中轴值，而后将序列分成两个部分，其中左边的部分 b 中的元素均小于或者等于 中轴值，右边的部分 c 的元素 均大于或者等于中轴值，而后通过递归调用快速排序的过程分别对两个部分进行排序，最后将两部分产生的结果合并即可得到最后的排序序列。
“基准值”的选择有很多种方法。最简单的是使用第一个记录的关键字值。但是如果输入的数组是正序或者逆序的，就会将所有的记录分到“基准值”的一边。较好的方法是随机选取“基准值”，这样可以减少原始输入对排序造成的影响。但是随机选取“基准值”的开销大。
参考：
https://blog.csdn.net/weixin_40205234/article/details/86699088
课本（教材）原话（清华大学出版社《数据结构》严蔚敏、吴伟民）：
以上排序均属于内部排序，运行在RAM中。

交换排序：利用交换元素的位置进行排序的方法称为交换排序。常用的交换排序有冒泡排序和快速排序。

 

冒泡排序算法：

基本思想：n个元素，序列进行N-1次循环，依次比较相邻两个元素的大小，如果array[i]>array[i+1]，则交换两个元素，反之则不交换。这样每次循环都能比较出数值最大的那个元素。

 

最好最坏情况：

最好情况是正序，时间复杂度是O（N），比较次数为n-1次

最坏情况是逆序，时间复杂度是O(N2)，比较次数为n(n-1)/2

步骤：

初始序列：49 38 65 97 76 13 27 49*


	
      38 49 65 76 13 27 49* 97
	
	

	
      38 49 65 13 27 49* 76 97
	
	

	
      38 49 13 27 49* 65 76 97
	
	

	
      38 13 27 49 49* 65 76 97
	
	

	
      13 27 38 49 49* 65 76 97
	
	

	
      13 27 38 49 49* 65 76 97
	
	

	
      13 27 38 49 49* 65 76 97
	
	

	
      13 27 38 49 49* 65 76 97
	
根据过程可以看出冒泡排序是一个稳定排序算法。

算法代码:

//冒泡排序（稳定算法）
void MaoPaoSort(int *array,int len)
{
        int i, j;
        int temp;
        for (i = 0; i < len; ++i)
        {
               for (j = 1; j < len - i; j++)
               {
                       if (array[j] <array[j-1])
                       {
                              temp = array[j];
                              array[j] = array[j - 1];
                              array[j - 1] = temp;
                       }
               }
        }
}

可以将冒泡排序进行优化：

如果某一趟已经将序列排好，程序再继续运行就是多余的，我们可以将其终止。

算法代码：

void MaoPaoSort(int *array,int len)
{
        int i, j;
        int temp;
        int flag = 0;
        for (i = 0; i < len&&flag==0; ++i)
        {
               flag = 1;
               for (j = 1; j < len - i; j++)
               {
                       if (array[j] <array[j-1])
                       {
                              temp = array[j];
                              array[j] = array[j - 1];
                              array[j - 1] = temp;
                              flag = 0;
                       }
               }
        }
}

快速排序是冒泡排序的一种改进。

基本思想：

在待排序的序列中选取一个基准值，通常为第一个数字

然后经过一趟排序将这个序列分割成独立的两部分，

其中，比基准值小的数字放在左边，比基准值大的数字放在右边，

则可对这两部分记录继续递归进行排序，以达到整个序列有序。

 

步骤过程（动图）：



算法代码：


//从两端交替扫描
int Partition(int *array, int low, int high)
{
        //选取一个基准值
        int pivokey = array[low];
        while (low < high)//当low==high时循环结束，按照基准值排序两边完成
        {
               //扫描右边,直至遇到一个小于基准值的数停止
               while (low<high&&array[high]>=pivokey)
                       --high;
               //将这个小于基准值的数取出放入左边
               array[low] = array[high];
               //扫描左边，直至遇到一个大于基准值的数停止扫描
               while (low < high&&array[low]<=pivokey)
                       ++low;
               //将这个大于基准值的数放入右边
               array[high] = array[low];
        }
        array[low] = pivokey;//将基准值填入
        return low;//返回基准值所在的位置
}
//快速排序(不稳定算法)
void QSort(int *array,int low,int high)
{
        if (low < high)//长度大于1
        {
               //找到最后填入基准值位置
               int pivotic = Partition(array,low,high);
               //再对左边序列进行排序
               QSort(array,low,pivotic-1);
               //对序列右边进行排序
               QSort(array,pivotic+1,high);
        }
        return;
}


   快速排序最佳情况下时间复杂度是 O(nlogn)。但是最坏情况下可能达到O(n^2)。说明快速排序达到最坏情况的原因。并提出改善方案并实现之。

 

快速排序算法的几种改进：

1.随机化算法

    基本的快速排序选取第一个元素作为主元。这样在数组已经有序的情况下，每次划分将得到最坏的结果。一种常见的优化方法是随机化算法，即随机选取一个元素作为主元。这种情况下虽然最坏情况仍然是O(n^2)，但最坏情况不再依赖于输入数据，而是由于随机函数取值不佳。实际上，随机化快速排序得到理论最坏情况的可能性仅为1/(2^n)。所以随机化快速排序可以对于绝大多数输入数据达到O(nlogn)的期望复杂度。

随机化快速排序的唯一缺点在于，一旦输入数据中有很多的相同数据，随机化的效果将直接减弱。对于极限情况，即对于n个相同的数排序，随机化快速排序的时间复杂度将毫无疑问的降到O(n^2)。

算法描述：

void swap(int *array, int index, int n)
{
        int temp;
        temp = array[index];
        array[index] = array[n];
        array[n] = temp;
}
int Partition1(int *array,int low,int high)
{
        if (array == nullptr || low <0)
               throw new std::exception("Invalid parameters\n");
        //选取一个随机值
        int index = (rand() % (high - low)) + low;
        //将随机数与第一位交换，接着就是经典的partition
        swap(array, index, low);
        //保存这个随机数
        int privokey = array[low];
        while (low < high)
        {
               //找到小于基准值的数
               while (low<high&&array[high]>=privokey)
                       high--;
               if (low < high)
               {
                       array[low] = array[high];
               }
               
               while (low < high&&array[low] <=privokey)
                       low++;
               if (low < high)
               {
                       array[high] = array[low];
               }
               
        }
        array[low] = privokey;
        return low;
}

2.三平均分区法

    与一般的快速排序方法不同，它并不是选择待排数组的第一个待排数组第一个数作为中轴。而是选用待排数组最左边、最右边和最中间的三个元素的中间值作为轴。

 

算法代码：

//求三个数中位数，并将其放在初始位置。       
void GetThreeValue(int *array, int low, int high)
{
        int mid = (low + (high - low)) >> 1;
        //先把最大的数放入到high位置，然后比较mid和low,如果mid比low大，则说明mid是中间值，放入low位置
        if (array[mid] > array[high])
        {
               swap(array,mid,high);
        }
        if (array[low] > array[high])
        {
               swap(array,low,high);
        }
        if (array[mid] > array[low])
        {
               swap(array,mid,low);
        }
}
//三平均分区法，可以使最坏情况的几率大大减小（减小退化问题）
int Partition2(int *array, int low, int high)
{
        if (array == nullptr || low < 0||low>high)
               throw new std::exception("Invalid Parameters\n");
        
         GetThreeValue(array, low, high);
         int privokey = array[low];
        while (low < high)
        {
               while (low < high&&array[high] >= privokey)
                       high--;
               if (low<high)
               {
                       array[low] = array[high];
               }
               while (low < high&&array[low] <= privokey)
               {
                       low++;
               }
               if (low < high)
               {

                    array[high] =array[low];                       }
        }
        array[low] = privokey;
        return low;
}

 

3.每次选取数据集中的中位数做基准值。

其他可以改进的地方（网络搜集） ：

1、  快速排序在处理小规模数据时的表现不好.

这个时候可以改用插入排序。

当数据规模小于一定程度时，改用插入排序。具体小到何种规模时，采用插入排序，这个理

论上还不解，一些文章中说是 5 到 25 之间。SGI STL 中的快速排序采用的值是 10.

2、对于一个每个元素都完全相同的一个序列来讲，快速排序也会退化到 O(n^2)。

要将这种情况避免到，可以这样做：

在分区的时候，将序列分为 3 堆，一堆小于中轴元素，一堆等于中轴元素，一堆大于中轴元

素，下次递归调用快速排序的时候，只需对小于和大于中轴元素的两堆数据进行排序，中间

等于中轴元素的一堆已经放好。

参考博客：https://blog.csdn.net/lingfengtengfei/article/details/12376889

快速排序



1.基本思想


  
快速排序采用分治思想。经过一趟排序将待排序序列分割为独立的两部分，其中一部分的所有排序关键字均小于另一部分的所有排序关键字，再按上述方法对序列的两部分分别进行快速排序，整个排序过程可以递归执行，最终达到整个序列有序的目的。




2.算法概述


  
分解：在待排序数列按照某种特定选取一个元素作为主元。利用主元对序列进行重排，使得序列分成独立的两个部分，其中一部分的所有排序关键字均小于另一部分的所有排序关键字，即序列所有排序关键字小于主元的排序关键字的元素置于主元的左侧，其他元素置于右侧。 

  。 
解决：通过递归对主元左侧的序列已经右侧的序列进行快速排序来去求解子问题。 
合并：因为快速排序是原址操作，所以不需要执行合并操作，同时也节省了部分空间。




3.算法实现（Python)



# coding = utf-8

"""
快速排序的一些优化方式
"""
import random
import time


def quick_sort(lst, first=0, last=0):
    # 快速排序
    if first >= last:
        return lst
    low = first
    high = last
    pivot = lst[first]  # 选取第一个为主元
    while first < last:
        while first < last and lst[last] >= pivot:
            last -= 1
        lst[first] = lst[last]
        while first < last and lst[first] <= pivot:
            first += 1
        lst[last] = lst[first]
    lst[last] = pivot
    quick_sort(lst, low, first - 1)
    quick_sort(lst, first + 1, high)



4. 算法分析


  
运行时间 

  快速排序的最坏时间复杂度是Θ(n2)，平均情况下的时间复杂度为Θ(nlgn)。快速排序的渐近时间复杂度介于最坏情况和平均情况。 

  这里分别采用确定的快速排序（即选取序列的第一个元素或最后一个序列为主元）分别针对输入规模>500万的序列进行排序，获得确定的快速排序的运行时间。
  
  
输入规模500万的序列排序运行时间
  
  
算法
  
随机序列
  
重复序列
  
升序序列
  
降序序列
确定的快速排序
  
36084ms
  
递归深度过大，堆栈溢出
  
同左
  
同左
python内置sort方法
  
5372ms
  
93ms
  
184ms
  
99ms



  
测试数据分析 

  在针对输入序列的数据是随机的时，我们设计的快速排序的效率是可以接受的。针对输入序列是有序的时候，虽然因为递归深度过大，导致堆栈溢出（Python的解释器没有针对做优化），无法成功执行完程序，但是我们也可以预料到，每次排序划分长度都是1，也就是说我们需要将序列划分500万次，才能使序列重新有序，其时间复杂度和空间复杂度可想而知。此时的情况为最坏的情况即时间复杂度为Θ(n2)，即沦为普通的冒泡排序。在实际情况中，输入序列很有可能是有序的或者是部分有序的，这时我们可以通过在算法中引入随机性，使得算法对所有的输入都能获得较好的期望性能，同时将随机化版本的快速排序被更多的人运用在大数据输入情况下的排序算法。


优化方式1：引入随机性

随机选取主元元素



# coding = utf-8

"""
优化方法1：引入随机性
"""

import random
import time


def quick_sort(lst, first=0, last=0):
    # 快速排序
    if first >= last:
        return lst
    low = first
    high = last
    pivot_index = random.randint(first, last)  # 随机选取主元位置
    lst[first], lst[pivot_index] = lst[pivot_index], lst[first]  # 将主元置于首位
    pivot = lst[first]
    while first < last:
        while first < last and lst[last] >= pivot:
            last -= 1
        lst[first] = lst[last]
        while first < last and lst[first] <= pivot:
            first += 1
        lst[last] = lst[first]
    lst[last] = pivot
    quick_sort(lst, low, first - 1)
    quick_sort(lst, first + 1, high)


  
输入规模500万的序列排序的运行时间
  
  
算法
  
随机序列
  
重复序列
  
升序序列
  
降序序列
随机化快速排序
  
45830ms
  
递归深度过大，堆栈溢出
  
29147ms
  
29363ms
python内置sort方法
  
6027ms
  
139ms
  
113ms
  
122ms



  
测试数据分析 

  通过引入随机性，我们较好的解决了序列有序的时候出现的问题，但是仍然存在一个问题那就是如果序列为重复的数据或者数据大量重复的情况，只引入随机化并不能很好的解决问题。这时候我们可以通过将排序关键字与主元相等的元素聚集在一起，下次不再对这些元素进行分割，这不仅可以解决目前的设计的算法在重复序列上存在的问题，也可以一定程度上优化对其他序列排序的效率。


优化方式2：聚集



# coding = utf-8

"""
优化方法1：引入随机性
优化方法2：聚集
"""

import random
import time


def quick_sort(lst, first=0, last=0):
    # 快速排序
    if first >= last:
        return lst
    low = first
    high = last
    left_lst_len = 0  # 分割后第一个序列和第二个序列与主元相等元素的长度
    right_lst_len = 0
    # 选取随机的主元，并将主元元素与第一个元素置换
    pivot_index = random.randint(first, last)
    lst[first], lst[pivot_index] = lst[pivot_index], lst[first]
    pivot = lst[first]
    while first < last:
        while first < last and lst[last] >= pivot:
            if lst[last] == pivot:
                right_lst_len += 1
            last -= 1
        lst[first] = lst[last]
        while first < last and lst[first] <= pivot:
            if lst[first] == pivot:
                left_lst_len += 1
            first += 1
        lst[last] = lst[first]
    lst[last] = pivot
    lst1_last = first - 1  # 保存分割后第一个序列的最后位置和第二个序列的最开始的位置
    lst2_first = first + 1
    flag = low
    while lst1_last - low > 0 and flag < lst1_last and left_lst_len > 0:  # 将第一个序列中与主元相等的元素置于主元左侧
        if pivot == lst[flag]:
            while lst[lst1_last] == pivot and left_lst_len > 0 and lst1_last - low > 0:
                left_lst_len -= 1
                lst1_last -= 1
            if lst1_last > 0 and left_lst_len > 0:
                lst[flag], lst[lst1_last] = lst[lst1_last], lst[flag]
                left_lst_len -= 1
                lst1_last -= 1
            else:
                break
        flag += 1
    flag = high
    while high - lst2_first > 0 and flag > lst2_first and right_lst_len > 0:  # 将第二个序列中与主元相等的元素置于主元右侧
        if pivot == lst[flag]:
            while lst[lst2_first] == pivot and right_lst_len > 0 and high - lst2_first > 0:
                right_lst_len -= 1
                lst2_first += 1
            if lst2_first < high and right_lst_len > 0:
                lst[flag], lst[lst2_first] = lst[lst2_first], lst[flag]
                right_lst_len -= 1
                lst2_first += 1
            else:
                break
        flag -= 1
    quick_sort(lst, low, lst1_last)
    quick_sort(lst, lst2_first, high)


  
输入规模500万的序列排序的运行时间
  
  
算法
  
随机序列
  
重复序列
  
升序序列
  
降序序列
随机化快速排序+聚集
  
63856ms
  
2272ms
  
38797ms
  
42183ms
python内置sort方法
  
7682ms
  
88ms
  
95ms
  
103ms



  
测试数据分析 

  通过将排序关键字与主元相等的元素聚集在一起，下次不再对这些元素进行分割，这不仅可以解决目前的设计的算法在重复序列上存在的问题，也可以一定程度上优化对其他序列排序的效率，如果序列的重复度（即重复出现的数据所占比例）越大，聚集所提高的效率越大。




优化方式3：三位数取中

取序列中lst[first]、lst[mid]、lst[last]中的中位数作为主元



# coding = utf-8

"""
优化方法2：聚集
优化方法3：三位数取中
"""

import random
import time


def quick_sort(lst, first=0, last=0):
    # 快速排序
    if first >= last:
        return lst
    low = first
    high = last
    left_lst_len = 0  # 分割后第一个序列和第二个序列与主元相等元素的长度
    right_lst_len = 0
    select_pivot_median(lst, first, last)  # 选择主元并将置于首位
    pivot = lst[first]
    while first < last:
        while first < last and lst[last] >= pivot:
            if lst[last] == pivot:
                right_lst_len += 1
            last -= 1
        lst[first] = lst[last]
        while first < last and lst[first] <= pivot:
            if lst[first] == pivot:
                left_lst_len += 1
            first += 1
        lst[last] = lst[first]
    lst[last] = pivot
    lst1_last = first - 1  # 保存分割后第一个序列的最后位置和第二个序列的最开始的位置
    lst2_first = first + 1
    flag = low
    while lst1_last - low > 0 and flag < lst1_last and left_lst_len > 0:  # 将第一个序列中与主元相等的元素置于主元左侧
        if pivot == lst[flag]:
            while lst[lst1_last] == pivot and left_lst_len > 0 and lst1_last - low > 0:
                left_lst_len -= 1
                lst1_last -= 1
            if lst1_last > 0 and left_lst_len > 0:
                lst[flag], lst[lst1_last] = lst[lst1_last], lst[flag]
                left_lst_len -= 1
                lst1_last -= 1
            else:
                break
        flag += 1
    flag = high
    while high - lst2_first > 0 and flag > lst2_first and right_lst_len > 0:  # 将第二个序列中与主元相等的元素置于主元右侧
        if pivot == lst[flag]:
            while lst[lst2_first] == pivot and right_lst_len > 0 and high - lst2_first > 0:
                right_lst_len -= 1
                lst2_first += 1
            if lst2_first < high and right_lst_len > 0:
                lst[flag], lst[lst2_first] = lst[lst2_first], lst[flag]
                right_lst_len -= 1
                lst2_first += 1
            else:
                break
        flag -= 1
    quick_sort(lst, low, lst1_last)
    quick_sort(lst, lst2_first, high)


def select_pivot_median(lst, first, last):
    # 将选取的主元即lst[first],lst[mid],lst[last]的中位数置于first坐标位置
    mid = first + ((last - first) >> 1)  # 计算序列中间元素的下标
    if lst[mid] > lst[last]:
        lst[mid], lst[last] = lst[last], lst[mid]
    if lst[first] > lst[last]:
        lst[first], lst[last] = lst[last], lst[first]
    if lst[mid] > lst[first]:
        lst[mid], lst[first] = lst[first], lst[mid]


  
输入规模500万的序列排序的运行时间
  
  
算法
  
随机序列
  
重复序列
  
升序序列
  
降序序列
三数取中的快速排序+聚集
  
53375ms
  
2550ms
  
30123ms
  
35552ms
python内置sort方法
  
5767ms
  
88ms
  
126ms
  
103ms



  
测试数据分析 

  通过引入随机性提高序列分割的效率，但是其最坏情况下的时间复杂度仍然是Θ(n2)。最佳情况下的划分是可以将待排序的序列划分为等长的序列，也就是说我们选取的主元是整个序列的中位数，但是如果要求整个序列的中位数那必定会花费更多的时间，有点得不偿失的感觉。我们可以选取折中的办法，选择最左端、中心位置、最右端的元素中的中位数作为组元，能一定程度上快速排序的比较次数。




优化方式4：引入插入排序

插入排序在待排序序列长度一定时效率高于插入排序，我们可以在快速排序分割的子序列长度达到一定时采用插入排序进行排序



# coding = utf-8

"""
优化方法2：聚集
优化方法3：三位取中
优化方法4：插入排序
"""

import random
import time


def quick_sort(lst, first=0, last=0):
    if last - first + 1 > 10:
        insert_sort(lst, first, last)
    else:
        # 快速排序
        if first >= last:
            return lst
        low = first
        high = last
        left_lst_len = 0  # 分割后第一个序列和第二个序列与主元相等元素的长度
        right_lst_len = 0
        select_pivot_median(lst, first, last)  # 选择主元并将置于首位
        pivot = lst[first]
        while first < last:
            while first < last and lst[last] >= pivot:
                if lst[last] == pivot:
                    right_lst_len += 1
                last -= 1
            lst[first] = lst[last]
            while first < last and lst[first] <= pivot:
                if lst[first] == pivot:
                    left_lst_len += 1
                first += 1
            lst[last] = lst[first]
        lst[last] = pivot
        lst1_last = first - 1  # 保存分割后第一个序列的最后位置和第二个序列的最开始的位置
        lst2_first = first + 1
        flag = low
        while lst1_last - low > 0 and flag < lst1_last and left_lst_len > 0:  # 将第一个序列中与主元相等的元素置于主元左侧
            if pivot == lst[flag]:
                while lst[lst1_last] == pivot and left_lst_len > 0 and lst1_last - low > 0:
                    left_lst_len -= 1
                    lst1_last -= 1
                if lst1_last > 0 and left_lst_len > 0:
                    lst[flag], lst[lst1_last] = lst[lst1_last], lst[flag]
                    left_lst_len -= 1
                    lst1_last -= 1
                else:
                    break
            flag += 1
        flag = high
        while high - lst2_first > 0 and flag > lst2_first and right_lst_len > 0:  # 将第二个序列中与主元相等的元素置于主元右侧
            if pivot == lst[flag]:
                while lst[lst2_first] == pivot and right_lst_len > 0 and high - lst2_first > 0:
                    right_lst_len -= 1
                    lst2_first += 1
                if lst2_first < high and right_lst_len > 0:
                    lst[flag], lst[lst2_first] = lst[lst2_first], lst[flag]
                    right_lst_len -= 1
                    lst2_first += 1
                else:
                    break
            flag -= 1
        quick_sort(lst, low, lst1_last)
        quick_sort(lst, lst2_first, high)


def select_pivot_median(lst, first, last):
    # 将选取的主元即lst[first],lst[mid],lst[last]的中位数置于first坐标位置
    mid = first + ((last - first) >> 1)  # 计算序列中间元素的下标
    if lst[mid] > lst[last]:
        lst[mid], lst[last] = lst[last], lst[mid]
    if lst[first] > lst[last]:
        lst[first], lst[last] = lst[last], lst[first]
    if lst[mid] > lst[first]:
        lst[mid], lst[first] = lst[first], lst[mid]


def insert_sort(lst, first, last):
    # 插入排序
    for index in range(first + 1, last + 1):
        key = lst[index]
        j = index - 1
        while j >= first:
            if lst[j] > key:
                lst[j + 1] = lst[j]
                lst[j] = key
            j -= 1



  
输入规模500万的序列排序的运行时间
  
  
算法
  
随机序列
  
重复序列
  
升序序列
  
降序序列
三数取中的快速排序+聚集+插入排序
  
40934ms
  
2549ms
  
21389ms
  
34769ms
python内置sort方法
  
5690ms
  
88ms
  
119ms
  
124ms



  
测试数据分析 

  针对长度较小或者部分有序数组时，插入排序的效率优于快速排序，引入插入排序将会使算法整体效率略有提高，而且这个方法适用于大部分序列。




其他优化方式


  
优化递归操作 

  我们可以使用尾递归的方式对快速排序的递归操作进行处理，来减少递归层次，避免堆栈溢出的发生，可以解决确定的快速排序无法处理已排序序列的问题 

  【待完成】。 
使用并行算法或者多线程算法处理子序列 

  【待完成】




总结


  
快速排序的优化细节没有处理好，导致算法的整体效率没有很大的提升，以后有时间对算法细节进行处理，可以达到更佳的效果。另外输入数据都是随机生成的，导致有的优化甚至比没优化之前排序所花费的时间更多，这除了细节问题，还有数据特征不符合现实生活。现实生活中的数据经常是部分有序的序列，所以如果采用优化后的算法，实际运行情况会比当前测试的情况更佳。
  
  
参考资料 
http://blog.csdn.net/hacker00011000/article/details/52176100

主要思想是：类似快速排序的划分方法, N个数存储在数组S中, 再从数组中随机选取一个数X(随机选取枢纽元, 可做到线性期望时间O(N)的复杂度), 把数组划分为Sa和Sb俩部分, Sa<=X<=Sb, 如果要查找的k个元素小于Sa的元素个数, 则返回Sa中较小的k个元素, 否则返回Sa中所有元素+Sb中小的k-|Sa|个元素. 像上述过程一样, 这个运用类似快速排序的partition的快速选择SELECT算法寻找最小的k个元素, 在最坏情况下亦能做到O(N)的复杂度.
 不过值得一提的是, 这个快速选择SELECT算法是选取数组中"中位数的中位数"作为枢纽元, 而非随机选取枢纽元.


1. If |S| = 1, then k = 1 and return the elements in S as the answer. If a cutoff for small files is being used and |S| <=CUTOFF, then sort S and return the kth smallest element.

    2. Pick a pivot element, v (- S.（选取一个枢纽元v属于S）

    3. Partition S - {v} into S1 and S2, as was done with quicksort.

（将集合S-{v}分割成S1和S2，就像我们在快速排序中所作的那样）

    4. If k <= |S1|, then the kth smallest element must be in S1. In this case, return quickselect (S1, k). If k = 1 + |S1|, then the pivot is the kth smallest element and we can return it as the answer. Otherwise, the kth smallest element lies in S2, and it
 is the (k - |S1| - 1)st smallest element in S2. We make a recursive call and return quickselect (S2, k - |S1| - 1).

（如果k<=|S1|，那么第k个最小元素必然在S1中。在这种情况下，返回quickselect(S1,k)。如果k=1+|S1|，那么枢纽元素就是第k个最小元素，即找到，直接返回它。否则，这第k个最小元素就在S2中，即S2中的第(k-|S1|-1)个最小元素，我们递归调用并返回quickselect(S2，k-|S1|-1))。


/*利用快速排序的思想实现寻找数组中最小的k个元素*/
/*
1. If |S| = 1, then k = 1 and return the elements in S as the answer. If a cutoff for small files is being used and |S| <=CUTOFF, then sort S and return the kth smallest element.
2. Pick a pivot element, v (- S.（选取一个枢纽元v属于S）
3. Partition S - {v} into S1 and S2, as was done with quicksort.(将集合S-{v}分割成S1和S2，就像我们在快速排序中所作的那样)
4. If k <= |S1|, then the kth smallest element must be in S1. In this case, return quickselect (S1, k). If k = 1 + |S1|, then the pivot is the kth smallest element and we can return it as the answer. Otherwise, the kth smallest element lies in S2, and it is the (k - |S1| - 1)st smallest element in S2. We make a recursive call and return quickselect (S2, k - |S1| - 1).
*/

//q_select places the kth smallest element in a[k]
void q_select(input_type a[], int k, int left, int right)
{
	int i,j;
	input_type pivot;
	if( left+CUTOFF <= right)
	{
		pivot = median3( a, left, right);
		//取三数中值作为枢纽元,可以消除最坏情况而保证此算法是O(N)的.不过,这还只局限在理论意义上.
		
		i = left; j = right-1;
		for(;;)
		{
			while(a[++i]<pivot);
			while(a[--j]>pivot);
			if(i<j)
				swap(&a[i],&a[j]);
			else
				break;
		}
		swap(&a[i],&a[right-1]);	//restore pivot
		if(k<i)
			q_select(a,k,left,i-1);
		else
			if(k>i)
				q_select(a,k-i,i+1,right);
	}
	else
		insert_sort(a,left,right);
}

1. 与快速排序相比, 快速选择只做了一次递归调用而不是两次. 快速选择的最坏情况和快速排序的相同, 也是O(N^2), 最坏情况发生在枢纽元的选取不当, 以致S1，或S2中有一个序列为空;
2. 这就好比快速排序的运行时间与划分时否对称有关, 划分的好或对称, 那么快速排序可达最佳的运行时间O(n*logn), 划分的不好或不对称, 则会有最坏的运行时间为O(N^2). 而枢纽元的选择完全决定快速排序的partition过程是否划分对称.
3. 快速选择也是一样, 如果枢纽元的选取不当, 则依然会有最坏的运行时间为O(N^2)的情况发生. 那么, 怎么避免这个最坏情况的发生, 或者说就算是最坏情况下, 亦能保证快速选择的运行时间为O(N)? 关键, 还是看你的枢纽元怎么选取.
4. 像上述程序使用三数中值作为枢纽元的方法可以使得最坏情况发生的概率几乎可以忽略不计. 然而, 通过一种更好的方法, 如“五分化中项的中项”, 或"中位数的中位数"等方法选取枢纽元, 我们将能彻底保证在最坏情况下依然是线性O(N)的复杂度.