数据结构——快速排序

快速排序

1、选出一个key，一般是最左边或是最右边的。

2、定义一个begin和一个end，begin从左向右走，end从右向左走。（需要注意的是：若选择最左边的数据作为key，则需要end先走；若选择最右边的数据作为key，则需要bengin先走）。

3、在走的过程中，若end遇到小于key的数，则停下，begin开始走，直到begin遇到一个大于key的数时，将begin和right的内容交换，end再次开始走，如此进行下去，直到begin和end最终相遇，此时将相遇点的内容与key交换即可。（选取最左边的值作为key）

4.此时key的左边都是小于key的数，key的右边都是大于key的数

5.将key的左序列和右序列再次进行这种单趟排序，如此反复操作下去，直到左右序列只有一个数据，或是左右序列不存在时，便停止操作，此时此部分已有序

void QuickSort(int A[],int low,int high){
    if(low<high){    //递归跳出的条件
    //Partition()就是划分操作，将表A[]划分为满足上述条件的两个子表
    int pivotpos=Partition(A,low,high);//划分
    QuickSort(A,low,pivotpos-1);//依次对两个子表进行递归排序
    QuickSort(A,pivotpos+1,high);
    }
}

int Partition(int A[],int low,int high){
    int pivot=A[low];   //将当前表中第一个元素设为枢轴，对表进行划分
    while(low<high){    //循环跳出条件
        while(low<high&&A[high]>=pivot) --high;
        A[low]=A[high];     //将比枢轴小的元素移到左边
        while(low<high&&A[low]<=pivot) ++low;
        A[high]=A[low];     //将比枢轴大的元素移到右边
    }
    A[low]=pivot;   //枢轴元素存放到最终元素
    return low;     //返回存放枢轴的最终元素
}