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

迷南。 2022-08-07 01:55 159阅读 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);
    }

参考：

http://blog.csdn.net/hguisu/article/details/7776068

http://blog.csdn.net/xiazdong/article/details/8462393

http://blog.csdn.net/v\_JULY\_v/article/details/6262915