编辑代码

#include <stdio.h>

#define CutOff 100

void Quick_sort(int a[],int N);
void QuickSort(int a[],int Left,int Right);
int Median3(int a[],int Left,int Right);
void swap(int a[],int x,int y);
void Insertion_Sort(int a[],int N);

void Insertion_Sort(int a[],int N){
    int p,i,temp;
    for(int p = 1;p < N;p++){
        //摸下一张牌
        temp = a[p];
        //默认手上有一张牌,新摸的牌比手上的要小，空出位置
        for(i = p;i > 0 && a[i-1] > temp;i--){
            //移出空位
            a[i] = a[i-1];
        }
        //新牌落位
        a[i] = temp;   
    }
}

void swap(int a[],int x,int y){
    int temp;
    temp = a[x];
    a[x] = a[y];
    a[y] = temp;
}

/*
  选主元，取头，中，尾的中位数
*/
int Median3(int a[],int Left,int Right){
    int Center = (Left + Right) /2;
    //a[Left]<=a[Center]<=a[Right]
    if(a[Left] > a[Center]){
        //swap(&a[Left],&a[Center]);
        swap(a,Left,Center);
    }
    if(a[Left] > a[Right]){
        //swap(&a[Left],&a[Right]);
        swap(a,Left,Right);
    }
    if(a[Center] > a[Right]){
        //swap(&a[Center],&a[Right]);
        swap(a,Center,Right);
    }
    /*
      将pivot藏到右边（Right-1），这样
      只需要考虑a[Left+1]到a[Right-2]这
      个范围之间的数
    */
    //swap(&a[Center],&a[Right-1]);
    swap(a,Center,Right-1);
    return a[Right-1];
}

//划分子集
void QuickSort(int a[],int Left,int Right){
  /*
    定义一个阈值，当数据规模小于这个值的时
    候，停止递归，直接调用简单排序
  */
  if(CutOff <= Right-Left){
    int Pivot = Median3(a,Left,Right);
    int i = Left + 1;
    int j = Right - 2;
    // int i = Left;
    // int j = Right - 1;
    for(;;){
        while(a[i] < Pivot){
            i += 1;
        }
        while(a[j] > Pivot){
            j += 1;
        }
        if(i < j){
            //swap(&a[i],&a[j]);
            swap(a,i,j);
        }else{
            break;
        }
    }
    //一趟排序把主元放到正确且最终的位置
    //swap(&a[i],&a[Right-1]);
    swap(a,i,Right-1);
    QuickSort(a,Left,i-1);
    QuickSort(a,i+1,Right);
  }else{
      Insertion_Sort(a+Left,Right-Left+1 );
  }
}

void Quick_sort(int a[],int N){
    QuickSort(a,0,N-1);
    for(int i = 0;i < 11;i++){
        printf("%d ",a[i]);
    }
}

int main () {
    int a[11] = {25,52,30,56,66,12,15,26,80,101,580};
    printf("排序前的元素为：\n");
    for(int i = 0;i < 11;i++){
        printf("%d ",a[i]);
    }
    printf("\n");
    printf("排序后的元素为：\n");
    Quick_sort(a,11);
}