快速排序

快速排序

交换排序：

冒泡排序
快速排序

算法思想：

先找一个基准元素，比它小的往左去，比它大的往右去。

分成左右两块重复操作。

不断划分，左边都小于基准元素，右边都大于基准元素。

代码（非常重要！！！）

//用第一个元素将待排序序列划分成左右两个部分
int Partition(int A[],int low,int high){
    int pivot=A[low];		//第一个元素作为枢纽
    while(low<high){		//用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;				//返回存放枢纽的最终位置
}

//快速排序
void QuickSort(int A[],int low,int high){
    if(low<high){		//边界条件
        int pivotpos=Partition(A,low,high);
        QuickSort(A,low,pivotpos-1);
        QuickSort(A,pivotpos+1,high);
    }
}