快速排序

简介：

　快速排序(QuickSort)是对冒泡排序的一种改进的交换排序算法，又称　分区交换排序(partition-exchange sort)．
在平均状况下，快速排序排序n个项目要Ο(n log n)次比较。在最坏状况下则需要Ο(n2)次比较，但这种状况并不常见。
事实上，快速排序通常明显比其他Ο(n log n)算法更快，因为它的内部循环（inner loop）可以在大部分的架构上很有效率地被实现出来。因此称为快速排序．

算法描述：

快速排序使用分治法（Divide and conquer）策略来把一个序列（list）分为两个子序列（sub-lists）。

步骤为：

从数列中挑出一个元素，称为”基准”（pivot），
重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区结束之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。
递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。

递归的最底部情形，是数列的大小是零或一，也就是永远都已经被排序好了。虽然一直递归下去，但是这个算法总会结束，因为在每次的迭代（iteration）中，它至少会把一个元素摆到它最后的位置去。

化简得：

先从数列中取出一个数作为基准数。
分区过程,将比这个数大的数全放到它的右边,小于或等于它的数全放到它的左边。
再对左右区间重复第二步,直到各区间只有一个数。

快速排序视频演示　
 备份链接１　

过程演示：

首先：
       a[0]  a[1]  a[2]  a[3]  a[4]  a[5]  a[6]  a[7]  a[8]  a[9]
　　　　 3     0     1     8     7     2     5     4     9     6
- 第一次：
　　　　 　　　                                                         // 取出tmp = a[0],　
　　　　                                                             // i = 0, j = 9, 比较 tmp与 a[j](a[9]) , 3 <---> 6, 小, j--, 得：
　　　　 3     0     1     8     7     2     5     4     9     6 
　　　　 　　　                                                         // i = 0, j = 8, 比较 tmp与 a[j](a[8]) , 3 <---> 9, 小, j--, 得：
　　　　 3     0     1     8     7     2     5     4     9     6 
　　　　 　　　                                                         // i = 0, j = 7, 比较 tmp与 a[j](a[7]) , 3 <---> 4, 小, j--, 得：
　　　　 3     0     1     8     7     2     5     4     9     6 
　　　　 　　　                                                         // i = 0, j = 6, 比较 tmp与 a[j](a[6]) , 3 <---> 5, 小, j--, 得：
　　　　 3     0     1     8     7     2     5     4     9     6 
　　　　 　　　                                                         // i = 0, j = 5, 比较 tmp与 a[j](a[5]) , 3 <---> 2, 大, a[i] = a[j], i++, 得：
　　　　 2     0     1     8     7     2     5     4     9     6 
　　　　 　　　                                                         // i = 1, j = 5, 比较 tmp与 a[i](a[1]) , 3 <---> 0, 大, i++, 得：
　　　　 2     0     1     8     7     2     5     4     9     6 
　　　　 　　　                                                         // i = 2, j = 5, 比较 tmp与 a[i](a[2]) , 3 <---> 1, 大, i++, 得：
　　　　 2     0     1     8     7     2     5     4     9     6 
　　　　 　　　                                                         // i = 3, j = 5, 比较 tmp与 a[i](a[3]) , 3 <---> 8, 小,a[j] = a[i], j--, 得：
　　　　 2     0     1     8     7     8     5     4     9     6 
　　　　 　　　                                                         // i = 3, j = 4, 比较 tmp与 a[j](a[4]) , 3 <---> 7, 小, j--, 得：
　　　　 2     0     1     8     7     2     5     4     9     6 
　　　　 　　　                                                         // i = 3, j = 3, a[i] = a[j] = tmp;得：
　　　　 2     0     1     3     7     2     5     4     9     6 　
　　　　 
　　　这时，经过一次排序，我们得到两组，一组比tmp小的区域，一组比tmp大的区域，接下来，分别在两组区域内再进行区分，重复这样的操作，即可获得有序序列。
　　　　
- 第二次：
       a[0]  a[1]  a[2]  a[3]  a[4]  a[5]  a[6]  a[7]  a[8]  a[9]
　　　　 2     0     1     [3]    7     2     5     4     9     6
       a[0]  a[1]  a[2]
　　　　 2     0     1
　　　　 　　　                                                         // 取出tmp = a[0],　

　　　　 　　　                                                         // i = 0, j = 2, 比较 tmp与 a[j](a[2]) , 2 <---> 1,  大, a[i] = a[j], i++, 得：

　　　　 1     0     1 
　　　　 　　　                                                         // i = 1, j = 2, 比较 tmp与 a[i](a[1]) , 2 <---> 0,  大, i++, 得：

　　　　 1     0     1 
　　　　 　　　                                                         // i = 2, j = 2, a[i] = a[j] = tmp;得：

        1     0     2
　
- 第三次：
　　　　 　　　                                                       　　　　 　　　                                                         //这时，左边的仍没有结束，再进行分区。         
        1     0    [2]
　      
        1     0
　　　　 　　　                                                         //tmp = 1
　　　　 　　　                                                         // i = 0, j = 1, 比较 tmp与 a[j](a[1]) , 1 <---> 0,  大, a[i] = a[j], i++, 得：
        0     0
　　　　 　　　                                                         // i = 1, j = 1, a[i] = a[j] = tmp;得：
        0     1
　　　　 　　　                                                         //至此，左边的顺序已经排序完成
　　　　[0     1     2     3]    7     2     5     4     9     6
　　　　 　　　                                                         //再对右边进行同样的操作即可。
　　　 　　     ．．．

　　　　我们可以看到，通过每次将序列分成将比这个数大的数全放到它的右边,小于或等于它的数全放到它的左边。
再对左右区间重复,直到各区间只有一个数两部分，即可完成排序过程．

程序代码：

// 快排思路：
//
// 1，选取一个数值为关键值并且记录下来
// 2. 给定两个下标i,j分别指向头和尾(0, length - 1)
//
// 3.循环操作：
// 从后向前找遇到比关键值小的放在i下标；
// 从前向后找遇到比关键值大的放在j下标；
// 当i和j相等，退出
// 把关键值填充进去
//
// 4.对关键值两边做递归处理
按照此定义，我们很容易写出快速排序的程序代码：

//划分算法
int Partition(int s[], int left, int right) //返回调整后基准数的位置
{//以ｓ[left]作为基准划分
    int i = left;
    int j = right;
    int x = s[left];   //s[left]即s[i]就是基准
    while (i < j)　　　 //从表(即序列s[i]~s[j])的两端交替向中间扫描
    {
        // 从右向左扫描查找第一个小于x的数s[ｊ]
         while(i < j && s[j] >= x)
             j--;
         if(i < j)　　　　　//当i < j时，则若s[j] < x 
         {
             s[i] = s[j]; //将s[j]填到s[i]中,将s[j]交换到表的左端
             i++;
         }
         // 从左向右扫描查找第一个大于x的数s[i]
         while(i < j && s[i] < x)
             i++;
         if(i < j)         //当i < j时，则若s[i] > x 
         {
             s[j] = s[i]; //将s[ｉ]填到s[ｊ]中,将s[ｉ]交换到表的左端
             j--;
         }
     }
     //退出时,i等于j。将x填到排好序时应放的位置。
     s[i] = x;
     return i;
}
//再写分治法的代码:
void quick_sort1(int s[], int left, int right)
{
    int i = 0;
    if (left < right)
    {
        i = Partition(s, left, right);//先成挖坑填数法调整s[]
        quick_sort1(s, left, i - 1); // 递归调用
        quick_sort1(s, i + 1, right);
    }
}

算法Partition完成在给定区间s[i]~s[j]中，一趟快速排序的划分．
１．设置两个搜索指针i和j来指向给定区间的第一个和最后一个记录，并将第一个作为基准．
２．首先，从ｊ指针开始向左搜索比基准小的记录（即，该记录应该位于基准的左侧），找到后将其交换到ｉ指针处（此时位于基准的左侧）；
３．ｉ指针右移一个位置，由此开始自左向右搜索比基准大的记录（即，该记录应该位于基准的右侧）；
４．ｊ指针左移一个位置，并继续上述自右向左搜索，交换的过程．
５．如此由两端交替向中间搜索交换，直到ｉ，ｊ相等，表明，ｉ记录的左侧都比基准小，ｊ右侧都比基准值大．而ｉ，ｊ指向的同一个位置，就是基准值最终要放置的位置．

对其合并整理，优化代码如下：

void QuickSort2(int *a, int left, int right)
{
    if(left >= right)
    {
        return ;
    }
    int i = left;
    int j =right;
    int key = a[left];

    while(i < j)
    {
        while(i <j && key <= a[j])
        {
            j--;
        }
        a[i] = a[j];

        while(i <j && key>= a[i])
        {
            i++;
        }
        a[j] = a[i];
    }

    a[i] = key;
    QuickSort2(a , left, i-1);
    QuickSort2(a, i+1, right);
}

int QuickSort2(int *a, int left, int right)
{
    if(left >= right)
    {
        return -1;
    }
    int i = left;
    int j =right;
    int flag = 0;
    int key = a[left];

    while(i < j)
    {
        if(flag == 0)
        {
            if( key <= a[j])
            {
                j--;
            }
            else
            {
                a[i] = a[j];
                flag = 1;
            }
        }
        if(flag == 1)
        {
            if( key>= a[i])
            {
                i++;
            }
            else
            {
                a[j] = a[i];
                flag = 0;
            }
        }
    }

    a[i] = key;
    QuickSort2(a , left, i-1);
    QuickSort2(a, i+1, right);
    return i;
}

算法分析

功能检测

检测代码：

int main()
{
    int i =0;
    int a[] = {3,0,1,8,7,2,5,4,6,9};
    int n = sizeof(a)/sizeof(a[0]);
    quicksort1(a, 0, n-1);
//  QuickSort2(a, 0, n-1);

    printf("\n");
    for(i = 0; i < n ; ++i)
    {
        printf("%3d",a[i]);
    }
    printf("\n");
    return 0;
}

运行结果：

root@aemonair:~/Desktop# cc.sh QuickSort.c 
Compiling ...
-e CC      QuickSort.c -g -lpthread
-e         Completed .
-e         Sun Jul 24 16:46:53 CST 2016
root@aemonair:~/Desktop# ./QuickSort 

  0  1  2  3  4  5  6  7  8  9

总结：

快速排序被认为是在所有同数量级(O(n lg n))的排序算法中平均性能最好．
但是如果初始序列有序或基本有序时，快速排序将退化成冒泡排序，此时的时间复杂度上升到Ｏ(n^2)．
对此我们有如下优化方案：
如以中间的数作为基准数的,or随机选择基准数,and区间内数据较少时直接用另的方法排序以减小递归深度。

三平均分区法
关于这一改进的最简单的描述大概是这样的：与一般的快速排序方法不同，它并不是选择待排数组的第一个数作为基准，而是选用待排数组最左边、最右边和最中间的三个元素的中间值作为基准。这一改进对于原来的快速排序算法来说，主要有两点优势：
　　（1）首先，它使得最坏情况发生的几率减小了。
　　（2）其次，未改进的快速排序算法为了防止比较时数组越界，在最后要设置一个哨点。
根据分区大小调整算法
这一方面的改进是针对快速排序算法的弱点进行的。快速排序对于小规模的数据集性能不是很好。可能有人认为可以忽略这个缺点不计，因为大多数排序都只要考虑大规模的适应性就行了。但是快速排序算法使用了分治技术，最终来说大的数据集都要分为小的数据集来进行处理。
　　由此可以得到的改进就是，当数据集较小时，不必继续递归调用快速排序算法，而改为调用其他的对于小规模数据集处理能力较强的排序算法来完成.
　　另一种快速排序的改进策略是在递归排序子分区的时候，总是选择优先排序那个最小的分区。这个选择能够更加有效的利用存储空间从而从整体上加速算法的执行。

文章作者: Air

文章链接: http://aemonair.github.io/2016/07/24/Sort_2_QuickSort/

DataStruct Sort