快速排序

步骤

• 先从数列中取出一个数作为基准数。

• 分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。

• 再对左右区间重复第二步，直到各区间只有一个数。

三数中值分割法

选枢纽元时 采取左端 中心 右端 三值的中值，减少大概百分之五的运算时间

代码

void quick_sort(int array[], int left, int right)
{
    int i, j;
    int temp;       // 用来存放临时的元素值
    int control;    // 快速排序的控制值
 
    if(left < right)    // 判断数组下标的界限
    {
        i = left;
        j = right + 1;
        control = array[left];  // 将最左边的值作为控制值
        
        do{
            do{
                i++;
            }while(array[i] < control);
 
            do{
                j--;
            }while(array[j] > control);
 
            if(i < j)   // 将不符合control值条件的值进行交换
            {
                temp     = array[i];
                array[i] = array[j];
                array[j] = temp;
            }
            
        }while(i < j);
 
        /* 确定control值所在元素在序列中的位置 */
        temp = array[left];
        array[left] = array[j];
        array[j] = temp;
 
        /* 递归进行快速排序 */
        quick_sort(array, left, j - 1);
        quick_sort(array, j + 1, right);
        
    }

算法分析

• 最好情况为O(NlogN)
• 最坏情况O(N^2)
• 平均情况O(NlogN)

对于小数组来说 快速排序没有插入排序来的好