view plaincopy to clipboardprint?#include <iostream> #include <cstdlib> #include <time.h> using namespace std; void swap(int array[] , int i , int j) { if(i!=j) //This comparision is most important. { //Because function Partition always let its element exchang itself. //cout << array[i] << ' ' << array[j] << endl; array[i] = array[i]+array[j]; array[j] = array[i]-array[j]; array[i] = array[i]-array[j]; //cout << array[i] << ' ' << array[j] << endl; } } int Partition(int array[] , int begin , int end) { int sentinel = array[end]; int i = begin-1; for(int j=begin ; j<end ; j++) { if(array[j] <= sentinel) { i++; swap(array , i , j); } } swap(array , i+1 , end); return i+1; } void QuickSort(int array[] , int begin , int end) { int q; if(begin < end) { q = Partition(array , begin , end); QuickSort(array , begin , q-1); QuickSort(array , q+1 , end); } } int main() { const int n = 10; int a[n]; srand(time(0)); for(int i=1 ; i<n ; i++) { a[i] = rand()%100; } for(int i=1 ; i<n ; i++) { cout << a[i] << ' '; } cout << endl; QuickSort(a , 1 , n-1); for(int i=1 ; i<n ; i++) { cout << a[i] << ' '; } cout << endl; return 0; } #include <iostream>#include <cstdlib>#include <time.h>using namespace std;
void swap(int array[] , int i , int j){ if(i!=j) //This comparision is most important. { //Because function Partition always let its element exchang itself. //cout << array[i] << ' ' << array[j] << endl; array[i] = array[i]+array[j]; array[j] = array[i]-array[j]; array[i] = array[i]-array[j]; //cout << array[i] << ' ' << array[j] << endl; }}
int Partition(int array[] , int begin , int end){ int sentinel = array[end]; int i = begin-1; for(int j=begin ; j<end ; j++) { if(array[j] <= sentinel) { i++; swap(array , i , j); } } swap(array , i+1 , end); return i+1;}
void QuickSort(int array[] , int begin , int end){ int q; if(begin < end) { q = Partition(array , begin , end); QuickSort(array , begin , q-1); QuickSort(array , q+1 , end); }}int main(){ const int n = 10; int a[n]; srand(time(0)); for(int i=1 ; i<n ; i++) { a[i] = rand()%100; }
for(int i=1 ; i<n ; i++) { cout << a[i] << ' '; } cout << endl;
QuickSort(a , 1 , n-1);
for(int i=1 ; i<n ; i++) { cout << a[i] << ' '; } cout << endl; return 0;}
以上是算法导论上的快速排序的实现。
view plaincopy to clipboardprint?#include <iostream> #include <cstdlib> #include <time.h> using namespace std; void swap(int array[] , int i , int j) { if(i != j) //This comparision is most important. { //Because function Partition always let its element exchang itself. array[i] = array[i]+array[j]; array[j] = array[i]-array[j]; array[i] = array[i]-array[j]; } } int Partition(int array[] , int begin , int end) { int sentinel = array[end]; int i = begin-1; for(int j=begin ; j<end ; j++) { if(array[j] <= sentinel) { i++; swap(array , i , j); } } swap(array , i+1 , end); return i+1; } int RandomizedPartition(int array[] , int begin , int end) { srand(time(0)); int i = rand()%(end-begin+1)+begin; swap(array , i , end); return Partition(array , begin , end); } void QuickSort(int array[] , int begin , int end) { int q; if(begin < end) { q = RandomizedPartition(array , begin , end); QuickSort(array , begin , q-1); QuickSort(array , q+1 , end); } } int main() { const int n = 100; int a[n]; srand(time(0)); for(int i=1 ; i<n ; i++) { a[i] = rand()%100; } for(int i=1 ; i<n ; i++) { cout << a[i] << ' '; } cout << endl; QuickSort(a , 1 , n-1); for(int i=1 ; i<n ; i++) { cout << a[i] << ' '; } cout << endl; return 0; } #include <iostream>#include <cstdlib>#include <time.h>using namespace std;
void swap(int array[] , int i , int j){ if(i != j) //This comparision is most important. { //Because function Partition always let its element exchang itself. array[i] = array[i]+array[j]; array[j] = array[i]-array[j]; array[i] = array[i]-array[j]; }}
int Partition(int array[] , int begin , int end){
int sentinel = array[end]; int i = begin-1; for(int j=begin ; j<end ; j++) { if(array[j] <= sentinel) { i++; swap(array , i , j); } } swap(array , i+1 , end); return i+1;}
int RandomizedPartition(int array[] , int begin , int end){ srand(time(0)); int i = rand()%(end-begin+1)+begin; swap(array , i , end); return Partition(array , begin , end);}void QuickSort(int array[] , int begin , int end){ int q; if(begin < end) { q = RandomizedPartition(array , begin , end); QuickSort(array , begin , q-1); QuickSort(array , q+1 , end); }}int main(){ const int n = 100; int a[n]; srand(time(0)); for(int i=1 ; i<n ; i++) { a[i] = rand()%100; }
for(int i=1 ; i<n ; i++) { cout << a[i] << ' '; } cout << endl;
QuickSort(a , 1 , n-1);
for(int i=1 ; i<n ; i++) { cout << a[i] << ' '; } cout << endl; return 0;}
这段代码是随机快排。当数据基本有序，或数据大小相差悬殊时，采用这种算法。
以上两种算法都是递归执行的，如果系统栈有限，可以采取非递归实现的快排。
非递归实现的快排在另一篇博文里写过。
发表于 @ 2011年02月19日 10:04:00 | 评论( 0 ) | 编辑| 举报| 收藏
旧一篇:算法导论 Exercise 4.2-2查看最新精华文章 请访问博客首页相关文章
本文来自博客，转载请标明出处：http://blog.csdn.net/rockerman_shane/archive/2011/02/19/6194607.aspx
