void quick_sort1(int a[],int l,int r) 
{ 
 if(l >= r) 
  return; 
 int i, j, p; 
 i = l-1, j = l,p = a[r]; 
 while(j < r) 
 { 
  if(a[j] < p) 
   swap(a[++i], a[j]); 
  j++; 
 } 
 swap(a[++i], a[r]); 
 quick_sort1(a, l, i-1); 
 quick_sort1(a, i+1, r); 
} 

void quick_sort2(int a[],int l,int r) 
{ 
 if(l >= r) 
  return; 
 int i,j,p; 
 i = l-1,j = l; 
 
 p=l + rand()%(r-l); //随机产生[l,r)之间的数 
 swap(a[p], a[r]); 
 p = a[r]; 
 while(j < r) 
 { 
  if(a[j] < p) 
   swap(a[++i], a[j]); 
  j++; 
 } 
 swap(a[++i], a[r]); 
 quick_sort2(a, l, i-1); 
 quick_sort2(a, i+1, r); 
} 

void quick_sort3(int a[],int l,int r) 
{ 
 if(l >= r) 
  return; 
 int i,j,p; 
 i = l-1, j = r, p = a[r]; 
 while(1) 
 { 
  do { i++; } while(a[i] < p && i < r); 
  do { j--; } while(a[j] > p && j > l); 
  if(i >= j) 
   break; 
  swap(a[i], a[j]); 
 } 
 swap(a[i],a[r]); 
 quick_sort3(a, l, i-1); 
 quick_sort3(a, i+1, r); 
} 

void quick_sort4(int a[],int l,int r) 
{ 
 if(l >= r) 
  return; 
 int i,j,p; 
 i = l-1, j = r; 
 
 p = l + rand()%(r-l); 
 swap(a[p],a[r]); 
 p = a[r]; 
 while(1) 
 { 
  do { i++; } while(a[i] < p && i < r); 
  do { j--; } while(a[j] > p && j > l); 
  if(i >= j) 
   break; 
  swap(a[i], a[j]); 
 } 
 swap(a[i], a[r]); 
 quick_sort4(a, l, i-1); 
 quick_sort4(a, i+1, r); 
} 

void bubble_sort1(int a[],int n) 
{ 
 int i,j; 
 for(i = 0; i < n-1; i++) 
 { 
  for(j = i+1; j < n; j++) 
  { 
   if(a[i] > a[j]) 
    swap(a[i], a[j]); 
  } 
 } 
} 

void bubble_sort2(int a[],int n) 
{ 
 int i,j; 
 for(i = 0; i < n-1; i++) 
 { 
  bool exchange = false; 
  for(j = i+1; j < n; j++) 
  { 
   if(a[i] > a[j]) 
   { 
    exchange = true; 
    swap(a[i], a[j]); 
   } 
  } 
  if(exchange == false) 
   break; 
 } 
} 

void bubble_sort2(int a[],int n) 
{ 
 int i,j; 
 for(i = 0;i < n-1; i++) 
 { 
  bool exchange = false; 
  for(j = n-1;j > i; j--) 
  { 
   if(a[j-1] > a[j]) 
   { 
    exchange = true; 
    swap(a[j-1], a[j]); 
   } 
  }  
  if(exchange == false) 
   break; 
 } 
} 

void select_sort1(int a[],int n) 
{ 
 int i,j; 
 for(i = 0; i < n-1; i++) 
 { 
  int min = i; 
  for(j = i+1; j < n; j++) 
  { 
   if(a[j] < a[min]) 
    min = j; 
  } 
  if(min != i) 
   swap(a[i], a[min]); 
 } 
} 

void heap_siftdown(int a[],int n,int p) //调整算法 
{ 
 int i = p,j = i*2+1; 
 int tmp = a[i]; 
 while(j < n) 
 { 
  if(j+1 < n && a[j] < a[j+1]) 
   j++; 
  if(a[j] <= tmp) 
   break; 
  else 
  { 
   a[i] = a[j]; 
   i = j;j = j*2+1; 
  } 
 } 
 a[i] = tmp; 
} 
void heap_sort1(int a[],int n) 
{ 
 int i; 
 for(i = (n-1)/2; i >= 0;i--) 
  heap_siftdown(a, n, i); 
 for(i = n-1;i >= 0; i--) 
 { 
  swap(a[i], a[0]); 
  heap_siftdown(a, i, 0); 
 } 
} 

void insert_sort1(int a[],int n) 
{ 
 int i,j; 
 for(i = 1; i < n; i++) 
 { 
  for(j = i; j > 0 && a[j]<a[j-1]; j--) 
   swap(a[j-1], a[j]); 
 } 
} 

void insert_sort2(int a[],int n) 
{ 
 int i,j; 
 for(i = 1; i < n; i++) 
 { 
  for(j = i; j > 0 && a[j] < a[j-1]; j--) 
  { 
   int t = a[j-1]; 
   a[j-1] = a[j]; 
   a[j] = t; 
  } 
 } 
} 

void insert_sort3(int a[],int n) 
{ 
 int i,j; 
 for(i = 1;i < n; i++) 
 { 
  int t = a[i]; 
  for(j = i; j > 0 && a[j-1] > t; j--) 
   a[j] = a[j-1]; 
  a[j] = t; 
 } 
} 

void shell_sort1(int a[],int n) 
{ 
 int i = n; 
 do{ 
  i = i/3 + 1; 
  shell_pass1(a, n, i); 
 }while(i > 1); 
} 
void shell_pass1(int a[],int n,int inc) //inc为1时，其实就是直接插入排序 
{ 
 int i,j; 
 for(i = inc; i < n; i++) 
 { 
  int t=a[i]; 
  for(j = i;j >= inc && a[j-inc] > t; j-= inc) 
   a[j] = a[j-inc]; 
  a[j] = t; 
 } 
} 

void merge_sort1(int a[],int b[],int l,int r) 
{ 
 if(l >= r) 
  return; 
 int m = (l+r)/2; 
 merge_sort1(a, b, l, m); 
 merge_sort1(a, b, m+1, r); 
 merge1(a, b, l, m, r); 
} 
void merge1(int a[],int b[],int l,int m,int r) 
{ 
 int i,j,k; 
 for(i = l; i <= r; i++) 
  b[i] = a[i]; 
 i = l; j = m+1; k = l; 
 while(i <= m && j <= r) 
 { 
  if(b[i] <= b[j]) a[k++] = b[i++]; 
  else a[k++] = b[j++]; 
 } 
 while(i <= m) a[k++] = b[i++]; 
 while(j <= r) a[k++] = b[j++]; 
} 

#include <iostream> 
#include <ctime> 
using namespace std; 
const int N = 100; 
int a[N]; 
int b[N]; 
 
int main() 
{ 
 int i; 
 srand(time(0)); 
 //for(i=0;i<N;i++) 
 // a[i]= N-i; 
 for(i = 0;i < N; i++) 
  a[i]=rand()%N; 
 long start,end; 
 start = clock(); 
 
 //quick_sort1(a,0,N-1); 
 //quick_sort2(a,0,N-1); 
 //quick_sort3(a,0,N-1); 
 //quick_sort4(a,0,N-1); 
 //bubble_sort1(a,N); 
 //bubble_sort2(a,N); 
 //merge_sort1(a,b,0,N-1); 
 //heap_sort1(a,N); 
 //shell_sort1(a,N); 
 //select_sort1(a,N); 
 //insert_sort1(a,N); 
 //insert_sort2(a,N); 
 //insert_sort3(a,N); 
 
 end = clock(); 
 print_array(a, N); 
 cout<<"total time is : "<<(end-start)/1000.0<<'s'<<endl; 
 return 0; 
} 
 
void swap(int a[],int i,int j) //交换元素 
{ 
 int t = a[i]; 
 a[i] = a[j]; 
 a[j] = t; 
} 
 
void print_array(int a[],int n) //打印元素值 
{ 
 for(int i = 0; i < n; i++) 
 { 
  cout<<a[i]<<' '; 
  if(i==0 && i!=0) 
   cout<<endl; 
 } 
 cout<<endl; 
}