复习数据结构：排序算法（五）——快速排序的各种版本-蒲公英云

复习数据结构：排序算法（五）——快速排序的各种版本

迷南。 2022-08-07 01:55 225阅读 0赞

之前已经比较熟悉快排的基本思想了，其实现的方式也有很多种。下面我们罗列一些常见的实现方式：

版本一：算法导论上的单向扫描，选取最后一个元素作为主元

#include<iostream>
using namespace std; 
int partition(int data[], int low, int high)
{
    int pivot = data[high];  // let the last atom be the pivot 
    int i = low - 1;  // mark the pivot's true index: i+1
    for(int j = low; j < high; j++)  // 数组是从low ~ high, 这里就要到high-1截止
    {
        if(data[j] <= pivot)
        {
            i++;  // 说明pivot的位置要后移一位
            swap(data[i], data[j]);  // 较小的数放前面，由于pivot是i+1, 所以把data[j]放在i的位置
        }
    }
    swap(data[i+1], data[j]);  // 把主元放在合适的位置i+1，记住不是pivot，而是data[j]
    return i+1;  // return the true index of pivot, that is, i+1
}
void quickSort(int data[], int low, int high)
{
    if(low < high)
    {
        int k = partition(data, low, high); 
        quickSort(data, low, k-1); 
        quickSort(data, k+1, high); 
    }
}
int main()
{
    int data[] = {2, 6, 3, 8, 1, 4}; 
    quickSort(data, 0, 5); 
    for(int i = 0; i < 6; i++)
        cout<<data[i]<<' '; 
    cout<<endl; 
    return 0; 
}

版本二：双向扫描，选取第一个元素作为主元

#include<iostream>
using namespace std; 
void print(int a[], int n){  
    for(int j= 0; j<n; j++){  
        cout<<a[j] <<"  ";  
    }  
    cout<<endl;  
}  
void swap(int *a, int *b)  
{  
    int tmp = *a;  
    *a = *b;  
    *b = tmp;  
}  
// 双向扫描法  
int partition(int a[], int low, int high)  
{  
    int privotKey = a[low];                             //基准元素  
    while(low < high){                                   //从表的两端交替地向中间扫描  
        while(low < high  && a[high] >= privotKey) --high;  //从high 所指位置向前搜索，至多到low+1 位置。将比基准元素小的交换到低端  
        swap(&a[low], &a[high]);  
        while(low < high  && a[low] <= privotKey ) ++low;  
        swap(&a[low], &a[high]);  
    }  
    print(a,10);  
    return low;  
}  
void quickSort(int a[], int low, int high){  
    if(low < high){  
        int privotLoc = partition(a,  low,  high);  //将表一分为二  
        quickSort(a,  low,  privotLoc -1);          //递归对低子表递归排序  
        quickSort(a,   privotLoc + 1, high);        //递归对高子表递归排序  
    }  
}  
int main(){  
    int a[10] = {3,1,5,7,2,4,9,6,10,8};  
    cout<<"初始值：";  
    print(a,10);  
    quickSort(a,0,9);  
    cout<<"结果：";  
    print(a,10);  
    return 0; 
}

版本三：随机选取一个元素作为主元

//随机选择主元的快排主要步骤是先随机选择主元的位置，然后把该主元与第一个元素调换，之后的步骤与拿第一个元素当做主元的算法一样
#include<iostream>
using namespace std; 
//交换两个元素值，咱们换一种方式，采取引用“&” 
void swap(int& a , int& b)
{
 int temp = a;
 a = b;
 b = temp;
}
//返回属于[lo,hi)的随机整数 
int rand(int lo,int hi)
{
 int size = hi-lo+1;
 return  lo+ rand()%size; 
}
//分割，换一种方式，采取指针a指向数组中第一个元素 
int RandPartition(int* data, int lo , int hi)
{    
 //普通的分割方法和随机化分割方法的区别就在于下面三行       
 swap(data[rand(lo,hi)], data[lo]);
    int key = data[lo];
 int i = lo;
    for(int j=lo+1; j<=hi; j++)
 {
  if(data[j]<=key)
  {
   i = i+1;
   swap(data[i], data[j]);
  }            
 } 
 swap(data[i],data[lo]);
 return i;
}
//逐步分割排序 
void RandQuickSortMid(int* data, int lo, int hi)
{
 if(lo<hi)
 {
  int k = RandPartition(data,lo,hi);
  RandQuickSortMid(data,lo,k-1);
  RandQuickSortMid(data,k+1,hi);
 }
}
int main()
{
 const int N = 100; //此就是上文说所的“极限”测试。为了保证程序的准确无误，你也可以让N=10000。
 int *data = new int[N];      
    for(int i =0; i<N; i++)
  data[i] = rand();   //同样，随机化的版本，采取随机输入。 
    for(i=0; i<N; i++)
  cout<<data[i]<<" ";
    RandQuickSortMid(data,0,N-1);
 cout<<endl;
 for(i=0; i<N; i++)
  cout<<data[i]<<" ";
 cout<<endl;
    return 0;
}

版本四：三数取中作为主元

上面的程序版本，其中算法导论上采取单向扫描中，是以最后一个元素为枢纽元素，即主元，而在Hoare版本及其几个变形中，都是以第一个元素、或中间元素为主元，最后，上述给的快速排序算法的随机化版本，则是以序列中任一一个元素作为主元。

那么，枢纽元素的选取，即主元元素的选取是否决定快速排序最终的效率列?

答案是肯定的，当我们采取data[lo],data[mid],data[hi]三者之中的那个第二大的元素为主元时，便能尽最大限度保证快速排序算法不会出现O（N^2）的最坏情况。这就是所谓的三数取中分割方法。当然，针对的还是那个Partition过程。

//三数取中分割方法 
int RandPartition(int* a, int p , int q)
{    
 //三数取中方法的关键就在于下述六行，可以得到a[p], a[m], a[q]三个数中的中位数
 int m=(p+q)/2;
 if(a[p]<a[m])
  swap(a[p],a[m]);
 if(a[q]<a[m])
  swap(a[q],a[m]);
 if(a[q]<a[p])
  swap(a[q],a[p]);
 int key = a[p];
 int i = p;
 for(int j = p+1; j <= q; j++)
 {
  if(a[j] <= key)
  {
   i = i+1;
   if(i != j) 
    swap(a[i], a[j]);                 
  }            
 } 
 swap(a[i],a[p]);  
 return i;
}
void QuickSort(int data[], int lo, int hi)
{
    if (lo<hi)
    {
        int k = RandPartition(data, lo, hi);
        QuickSort(data, lo, k-1);
        QuickSort(data, k+1, hi);
    }
}

版本五：非递归版本

//递归的本质是什么?对了，就是借助栈，进栈，出栈来实现的。
   if( (key-lo)<(key-hi) )
   {
    st.push(key+1);    
    st.push(hi);
    hi=key-1;
   }
   else
   {
    st.push(lo);
    st.push(key-1);
    lo=key+1;
   }   
  }
  if(st.empty()) 
   return;
  hi=st.top();
  st.pop();  
  lo=st.top();
  st.pop();  
 }while(1);
}