復習データ構造:並べ替えアルゴリズム(5)――快速並べ替えの各種バージョン
前にはすでにファーストクラスの基本思想を熟知していました.その実現の方法もいろいろあります.いくつかの一般的な実現方法を羅列します.
アルゴリズム導論上の一方向スキャンは、最後の要素を主成分として選択します.
#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]の3つの要素のうち、2番目の大きさの要素を中心にしている場合、高速なソートアルゴリズムはO(N^2)の最悪の状況にならないように最大限に保証します.これはいわゆる三数取中分割の方法です.もちろん、そのパートナーシップの過程に対してです.
//
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_JULYv/articale/detail/6262915