#include <iostream> using namespace std; void quickPass(int* q, int l, int r, int k) { int i = l - 1, j = r + 1, x = q[k]; while(i < j) { do i ++; while(q[i] < x); do j --; while(q[j] > x); if(i < j) swap(q[i], q[j]); } } int main() { int arr[10] = {1, 3, 4, 5, 7, 9, 2, 10, 8, 6}; quickPass(arr, 0, 9, 6); for(int i = 0; i < 10; i ++) cout << arr[i] << ' '; return 0; }
设有一组初始记录关键字序列(K1 ,K2 ,…,Kn ),要求设计一个算法能够在O(n)的时间复杂度内将线性表划分成两部分,其中左半部分的每个关键字均小于Ki ,右半部分的每个关键字均大于等于Ki 。
void quickpass(int r[], int s, int t)
{
int i=s, j=t, x=r[s];
while(i<j){
while (i<j && r[j]>x) j=j-1; if (i<j) {r[i]=r[j];i=i+1;}
while (i<j && r[i]<x) i=i+1; if (i<j) {r[j]=r[i];j=j-1;}
}
r[i]=x;
}
#include void quickpass(int r[], int low, int high){ //low、high分别是当前操作的最小下标和最大下标,设初始关键字的第一个数为Ki int i=low, j=high, Ki=r[low]; while(i<j){ /*右边关键字比Ki大则下标j左移,否则把其值交换到左边位置、并让下标i右移*/ while(iKi) j-=1; if(i<j){ r[i]=r[j]; i+=1; } /*左边关键字比Ki小则下标i右移,否则把其值交换到右边位置,并让下标j左移*/ while(i<j && r[i]<Ki) i+=1; if(i<j){ r[j]=r[i]; j-=1; } } r[i]=Ki;//此时i==j,指向Ki的最终位置 } int main(){ int arr[] = {7,4,2,8,6,1,10},i; quickpass(arr,0,6); for(i=0;i<=6;i++) printf("%d,",arr[i]); return 0; }