快速排序的实现

快速排序的实现

 快速排序是1962年提出的一种划分交换排序。它采用了一种分治的策略，通常称其为分治法。分治法的思想是：将原问题分解为若干个规模更小但结构与原问题相似的子问题。递归地解这些子问题，然后将这些子问题的解组合为原问题的解。

一种快速排序的简单实现：

template<class T>
void quick_sort(T array[],int low,int high){
    int i,j,pivot;
    if(low<high){
        pivot=array[low];
        i=low;
        j=high;
        while(i<j){
            while(i<j&&array[j]>=pivot])
                j--;
            if(i<j)
               array[i++]=array[j];
            while(i<j&&array[i]<=pivot)
                i++;
            if(i<j)
              array[j--]=a[i];
        }
       a[i]=pivot;
       quick_sort(a,low,i-1);
       quick_sort(a,i+1,high);
    }
}

 

这里pivot代表基准值，它的初始值为a[low]，经过依次循环后，就确定了a[i]