快速排序

学习之后，自己练习手写一下排序算法，加深印象

原理：通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序的目的。

#define MAXSIZE 10
#include <stdio.h>
struct a{
    int array[MAXSIZE];    //数组用于存储排序数据 
    int length;           //用于存储数组长度信息， 
};

void init_array(struct a *L){   //初始化数组 
    int i;
    L->length = MAXSIZE-1;
    for (i=1;i<=L->length;i++){     //索引为0的项留作备用 
        scanf("%d",&(L->array[i]));
    }
}

void swap(struct a *L,int i,int j){   //交换数组项 
    int temp = L->array[i];
    L->array[i] = L->array[j];
    L->array[j] = temp;
}

void print(struct a *L){    //打印数组项 
    int i;
    for (i=1;i<=L->length;i++){
        printf("%d ",L->array[i]);
    }
}

int Partition(struct a *L, int low, int high){   //将一个序列划分为两个子序列 
    int middleValue; 
    middleValue = L->array[low];      //选取序列的第一项为枢纽值 
    while(low < high){                  
        while(low < high && middleValue <= L->array[high]){
            high--;       //从序列的尾部向前，依次和枢纽值比较，若当前项比枢纽值小，则退出循环 
        }
        swap(L,low,high);     //交换当前项和枢纽值 

        while(low < high && middleValue >= L->array[low]){
            low++;      //从序列的开头向后，依次枢纽值比较 ，若当前项比枢纽值大，则退出循环 
        }
        swap(L,low,high);   //交换当前项和枢纽值 
    }
    return low;   //最终low等于high，返回枢纽值 
}

void QSort(struct a*L, int low, int high){
    int middle;     
    if (low < high){ 
        middle = Partition(L,low,high);   //将序列划分为两个子序列，返回中点索引 
        QSort(L,low,middle-1);          //对值较小的子序列递归排序 
        QSort(L,middle+1,high);        //对值较大的子序列递归排序 
    } 
}

void QuickSort(struct a *L){   //排序算法 
    QSort(L,1,L->length);
} 

int main(){
    struct a List;
    init_array(&List);
    printf("排序前:");
    print(&List);
    QuickSort(&List);
    printf("\n排序后:");
    print(&List);
    return 0;
}

Partition函数的作用就是选取一个记录，例如第一个关键字50，然后将其放到一个位置，使得它左边的值都比它小，右边的值都比它大，这样的关键字称为枢纽
第一次划分子序列后，结果如下：

算法时间复杂度：O(nlogn)

优化
1.优化选取枢纽值

middleValue = L->array[low];

不再选取序列的第一项，而是选取三个数里中间大小的那个数

int m = low + (high -low)/2;
if (L->array[low] > L->array[high]){
    swap(L,low,high);
}
if (L->array[m] > L->array[high]){
    swap(L,m,high);
}
if (L->array[m] > L->array[low]){
    swap(L,low,m);
}
//排序过后保证了，枢纽值取得是三个数里面中间大小的数
pivotkey = L->array[low]
....   

2.优化不必要的交换

int Partition(struct a *L, int low, int high){   //将一个序列划分为两个子序列 
    int middleValue; 
    middleValue = L->array[low];      //选取序列的第一项为枢纽值
    while(low < high){                  
        while(low < high && middleValue <= L->array[high]){
            high--;       //从序列的尾部向前，依次和枢纽值比较，若当前项比枢纽值小，则退出循环 
        }
        L->array[low] = L->array[high];   //替换而不是交换

        while(low < high && middleValue >= L->array[low]){
            low++;      //从序列的开头向后，依次枢纽值比较 ，若当前项比枢纽值大，则退出循环 
        }
        L->array[high] = L->array[low];  //替换而不是交换
    }
    L->array[low] = middleValue;   //将枢纽值替换回L->array[low] 
    return low;   //最终low等于high，返回枢纽值 
}

3优化递归次数（尾递归优化）

void QSort(struct a*L, int low, int high){
    int middle;     
    While (low < high){ 
        middle = Partition(L,low,high);   //将序列划分为两个子序列，返回中点索引 
        QSort(L,low,middle-1);          //对值较小的子序列递归排序 
        low = middle+1             //尾递归 
    } 
}