24-伪代码详解

3.4.4　伪代码详解

（1）划分函数

我们编写划分函数对原序列进行分解，分解为两个子序列，以基准元素pivot为界，左侧子序列都比pivot小，右侧子序列都比pivot大。先从右向左扫描，找小于等于pivot的数，找到后两者交换（r[i]和r[j]交换后i++）；再从左向右扫描，找比基准元素大的数，找到后两者交换（r[i]和r[j]交换后j−−）。扫描交替进行，直到i=j停止，返回划分的中间位置i。

int Partition(int r[],int low,int high)   //划分函数
{
     int i=low,j=high,pivot=r[low];       //基准元素
     while(i<j) 
     {
         while(i<j&&r[j]>pivot) 
             j--;                         //向左扫描
         if(i<j) 
         {
             swap(r[i++],r[j]);           //r[i]和r[j]交换后i右移一位
         }
         while(i<j&&r[i]<=pivot) 
             i++;                         //向右扫描
         if(i<j) 
         {
              swap(r[i],r[j--]);          //r[i]和r[j]交换后j左移一位
         }
     }
     return i;                            //返回最终划分完成后基准元素所在的位置
}

（2）快速排序递归算法

首先对原序列执行划分，得到划分的中间位置mid，然后以中间位置为界，分别对左半部分（low，mid−1）执行快速排序，右半部分（mid+1，high）执行快速排序。递归结束的条件是lowhigh。

void QuickSort(int R[],int low,int high){ 
     int mid; 
     if(low<high) 
     {
          mid=Partition(R,low,high);      //返回基准元素位置
          QuickSort(R,low,mid-1);         //左区间递归快速排序
          QuickSort(R,mid+1,high);        //右区间递归快速排序
     }
}