(65)王道数据结构-快速排序

基本概念

快速排序是对冒泡排序的一种改进，其基本思想是基于分治法的：在待排序表L[1…n]中任取一个元素pivot作为基准，通过一趟排序将待排序表划分为独立的两部分L[1…k-1]和 L[k+1…n]，使得L[1…k-1]1中的所有元素小于pivot, L[k+1…。n]中的所有元素大于等于pivot，则pivot放在了其最终位置L(k)上，这个过程称为一趟快速排序。而后分别递归地对两个子表重复上述过程，直至每部分内只有一个元素或空为止，即所有元素放在了其最终位置上。

注意: 在快速排序算法中，并不产生有序子序列，但每趟排序后会将一个元素(基准元素)放到其最终的位置上。

代码逻辑

首先假设划分算法已知，记为Partition()，返回的是上述的k，注意到L(k)已在最终的位置，因此可以先对表进行划分，而后对两个表调用同样的排序操作。因此可以递归地调用快速排序算法进行排序

假设每次总以当前表中第一个元素作为枢轴值(基准)来对表进行划分，则必须将表中比枢轴值大的元素向右移动，将比枢轴值小的元素向左移动，使得一趟Partition()操作后，表中的元素被枢轴值一分为二

int Partition(ElemType A[], int low, int high) {
   ElemType 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; //返回存放枢轴的最终位置
}

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