根据网上查的一些有关快速排序原理的文章做的，不知道这样是不是正确。。。 #include <iostream> #include <iomanip>

using namespace std;

const int block_size = 12; const int PRINT_WIDTH = 4;

//交换两个元素 void swap(double &a,double &b); //指定区间内的插入排序 void ins_sort(double *dArrayObj,long id_begin,long id_end);

//分割函数 long partition(double *dArrayObj,long id_begin,long id_end); //快速排序主函数 void qsort(double *dArrayObj,long id_begin,long id_end);

//打印数组 void print_array(double *dArrayObj,long size);

int main() { //测试驱动 double n_queue[] = {5,1,17,6,43,20,9,65,10,22,12,64,39,70,3,54,98,192,184}; cout << "Before sort :" << endl; print_array(n_queue,19); qsort(n_queue,0,18); cout << "After sort :" << endl; print_array(n_queue,19); return 0; }

void swap(double &a,double &b) { double temp; temp = a; a = b; b = temp; }

void ins_sort(double *dArrayObj,long id_begin,long id_end) { double poster; //临时哨 long i,j; for(i = id_begin + 1; i <= id_end; i++) { poster = dArrayObj[i]; j = i - 1; while(dArrayObj[j] > poster) { dArrayObj[j+1] = dArrayObj[j]; j--; if(j < 0) break; } dArrayObj[j+1] = poster; } }

long partition(double *dArrayObj,long id_begin,long id_end) { double base_value = dArrayObj[id_begin]; long base_position = id_begin;

long i; for(i = id_begin + 1; i <= id_end; i++) { if(dArrayObj[i] < base_value) { if(i == base_position + 1) { swap(dArrayObj[base_position],dArrayObj[i]); base_position++; } else if(i > base_position + 1) { swap(dArrayObj[base_position],dArrayObj[base_position+1]); swap(dArrayObj[base_position],dArrayObj[i]); base_position++; } } }

return base_position; }

void qsort(double *dArrayObj,long id_begin,long id_end) { if(id_end - id_begin + 1 <= block_size) { ins_sort(dArrayObj,id_begin,id_end); } else { long p_point = partition(dArrayObj,id_begin,id_end);

//递归调用 qsort(dArrayObj,id_begin,p_point); qsort(dArrayObj,p_point+1,id_end); } }

void print_array(double *dArrayObj,long size) { long i; for(i = 0; i < size; i++) cout << setw(PRINT_WIDTH) << dArrayObj[i]; cout << endl; }