快速排序 基本思想是:在待排序序列中选定一个元 素X(可以任选,也可以选第一个元素,称 为划分元素,用它将原序列整理—划分 ( partitioning)为两个子序列,使其右边 的元素不比它大(小),使其左边的元素 不比它大(小);然后再对两个子序列进 y行上述划分;经过不断划分,直至将原序 列整理完毕为止如果是升序的话,此处应 为小
16 快速排序 基本思想是：在待排序序列中选定一个元 素X(可以任选，也可以选第一个元素)，称 为划分元素，用它将原序列整理——划分 （partitioning）为两个子序列，使其右边 的元素不比它大（小），使其左边的元素 不比它大（小）；然后再对两个子序列进 行上述划分；经过不断划分，直至将原序 列整理完毕为止如果是升序的话，此处应 为小
快速排序 初始状态 8 ∠第1次划分结 4 1 「4 8 41 17
17 快速排序 5 7 9 8 1 6 3 4 2 2 4 3 1 5 6 8 9 7 1 2 3 4 6 8 9 7 3 4 7 8 9 初始状态 第1次划分结 果
二分分治算法 asSort( Int m, int n)∥序列由m到n if(m <n) 调用划分函数 part(m,n,i); 递归调用 gkSort(,i-1); 递归调用 qk sort(i+1,m else 输出排序结束信息 return 8
18 二分分治算法 qkSort(int m,int n) // 序列由m到n { if(m < n) { 调用划分函数part(m,n,i); 递归调用qkSort(m, i - 1); 递归调用qkSort(i + 1, m); } else { 输出排序结束信息 return; } }
划分函数 int part(int low, int high) Int 1 float i=low;j=high ∥准备 P=allowI while(i<j while(ij&&a[订>=p)∥逐步减小j while(i<j&&a[<=p)∥/逐步增大i a[=aj []=p; ∥放置划分元素 return(i) 19
19 划分函数 int part(int low,int high) { int i,j; float p; i = low; j = high; // 准备 P = a[low]; while(i < j) { while(i < j && a[j] >= p) // 逐步减小j j --; a[i] = a[j]; while(i < j && a[i] <= p) // 逐步增大i i ++; a[j] = a[i]; } a[i] = p; // 放置划分元素 return(i); }
程序 include <iostream h #define n 10 double a={2.1,17,1.5,29,2.7,2.3,1.3,2.5,1,1,1,9 class QuickSort Ivate low, high p QuickSort( int, int void qksorto int parto void pinto QuickSort: Quick Sort( int I, int h) low=l high=h, void QuickSort: qkSorto if( low < high parto
20 程序 #include <iostream.h> #define N 10 double a[] = {2.1,1.7,1.5,2.9,2.7,2.3,1.3,2.5,1.1,1.9}; class QuickSort { private: int low,high; public: QuickSort( int , int ); void qkSort(); int part(); void prnt(); }; QuickSort::QuickSort( int l , int h ) { low = l; high = h; } void QuickSort::qkSort() { int i; if( low < high ) { i = part(); high = i - 1;