设有一组初始记录关键字序列（ K1 ， K2 ，…， Kn

#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;
}

设有一组初始记录关键字序列（K₁ ，K₂ ，…，K_n ），要求设计一个算法能够在O(n)的时间复杂度内将线性表划分成两部分，其中左半部分的每个关键字均小于K_i ，右半部分的每个关键字均大于等于K_i 。

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;
}