// 快速排序的实现版本// 其中median3 是从头，尾部，和中部取出值，再相互比较// 得到枢纽元#include <stdio.h>#define Cutoff (7)int median3(int A[] , int Left , int Right);void Qsort(int A[] , int Left , int Right);void Swap(int *A , int *B);void InsertSort(int *A , int N);int main(int argc, const char * argv[]) {        int A[15] = {9,8,7,6,5,4,3,2,1,9,8,7,6,5,4};        Qsort(A, 0, 14);    //InsertSort(A, 15);        for (int i = 0 ; i < 15 ; i++)        printf("%d " , A[i]);    return 0;}int median3(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]);        /* Invariant: A[Left] < A[center] < A[Right] */    Swap(&A[center], &A[Right -1]); //此时A[Right]已经在合适的位置了，就                                    //把枢纽元放在A【Right -1]的位置上    return A[Right - 1];    return 0 ;}void Qsort(int A[] , int Left , int Right){    int i , j ;    int pivot ;        if(Left + Cutoff <= Right)    {        i = Left;        j = Right - 1;        pivot = median3(A, Left, Right);        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 piovt*/        Qsort(A, Left, i-1);        Qsort(A, i + 1, Right);            }        else /* 小于10的时候，用插入排序代替快速排序 */        InsertSort(A + Left , Right - Left + 1);}void Swap(int *A , int *B){    int temp = *A ;    *A = *B ;    *B = temp ;}void InsertSort(int A[] , int N){    int i , j ;        int Tmp ;    for (i = 1 ; i < N ; i++) {        Tmp = A[i];        for (j = i ; j > 0 && A[ j - 1 ] > Tmp; j --)            A[j] = A[j - 1 ];   //使用数据移动代替数据交换,很重要的技巧        A[j] = Tmp ;    }}/* *************************************************快速排序总结  ***************************************************//* * 1 选取枢纽元        * 选取第一个或最后一个作为枢纽元  // 当输入数据是预排序的，则会一直产生很差的                                     // 划分，而这经常发生,所以，不能采用        * 随机选取一个枢纽元            // 代价有点大         * 三数中值分割法               // 选取第一个，最后一个和中间一个，然后排序                                     // 选取中间的那个数作为枢纽元，由于，第一个和                                    // 最后一个已经在何时的位置了，所以，将中间的那个数同A【Right-1】交换即可                                    //  函数median3 即选出枢纽元                                    //  * 2 分割策略        * i= -1 , j = 0 ,然后追赶  不是一个好策略                * i = 0 ， j = N -1 , 然后迎面相迎  是一个好策略    * 3 如何处理与枢纽元相等的元素        * 当 i  和  j 遇到与枢纽元相等的时候，是否应该停止？            * 1 不停止                      如果不停止的话，如果有很多相等的，会产生很坏的划分，还需要额外的                    判断是否到头了，增加了开销            * 2 停止                    做了n / 2 次交换，但是i 和 j 在中间交错，产生一个好的划分         ** 结论： 我们应该遇到相等就停下  * 4 当遇到小数组的时候，改变递归快速排序，改用插入排序     插入排序在N （ 5 15）的时候速度比快速排序快 推荐N= 10    * 5 时间复杂度分析        看算法导论的时间复杂度分析 */