quicksort.cpp

来自「是各种常用算法的集合」· C++ 代码 · 共 56 行

//快速排序
#include <iostream.h>
#include <stdlib.h>
#include <time.h>

typedef int ELEM;
typedef int KEY;

extern long count1;

void swap(ELEM& a ,ELEM& b){
	ELEM c = b; 
	b = a ;
	a = c ;
}

int partition(ELEM* array, int l, int r, KEY pivot) {
  do {               
    while ( array[++l] < pivot);
    while (r && (array[--r] > pivot)); 
    swap(array[l], array[r]);      
  } while (l < r);                   
  swap(array[l], array[r]);          
  return l;          
}

int findpivot(ELEM* array, int i, int j)  { return (i+j)/2; }

//快速排序算法
void qsort(ELEM* array, int i, int j) { 
  int pivotindex = findpivot(array, i, j);
  swap(array[pivotindex], array[j]);   
  int k = partition(array, i-1, j, array[j]);
  swap(array[k], array[j]);            
  if ((k-i) > 1) qsort(array, i, k-1);  
  if ((j-k) > 1) qsort(array, k+1, j); 
}

void sort(ELEM* array, int listsize) {
  qsort(array, 0, listsize-1);
}

int main()
{
	int n;
	cout<<"输入数组的大小 ：    ";
	cin>>n;
	ELEM * array = new ELEM[n];
	srand((unsigned) time(NULL));
	for( int i = 0 ; i < n ; i++ )
		array[i] = rand();   //随机生成数
	sort( array , n);
	return 0;
}