#include<iostream>
#include<stdio.h>
#include<conio.h>
#include<string.h>
using namespace std;
typedef int* SeqList;
int partition(SeqList r,int i,int j){
//調用partition(R,low,high)時，對R[low...high]做劃分并返回基準記錄的位置。
int pivot =r[i];//用區間的第一個記錄作為基準
//pivot 相當于在位置i上。
while(i<j){ //從區間兩端交替向中間掃描，直至i=j
while(i<j&&r[j]>=pivot)
j--;//從右向左掃描，查找第一個關鍵字小于pivot的記錄r[j]
if(i<j) //表示找到的r[j]<pivot
r[i++]=r[j]; //相當于交換r[i]和r[j],交換后i指針加1
while(i<j&&r[i]<=pivot) //從左向右掃描，查找第1個關鍵字大于pivot的記錄r[i]
i++;
if(i<j)//表示找到了r[i],使r[i]>pivot
r[j--]=r[i];//相當于交換r[i]和r[j],交換后指針減一。
}
r[i]=pivot;//基準記錄已被最后定位。
return i;
}
void quicksort(SeqList r,int low,int high){ //對R[low....high]快速排序。
int pivot;//劃分后的基準記錄的位置。
if(low<high){//僅當區間的長度大于1時，才排序。
pivot=partition(r,low,high);
//對R[low...high]做劃分。
quicksort(r,low,pivot-1);//對左區間遞歸排序。
quicksort(r,pivot+1,high);//對右區間遞歸排序。
}
}
int main(){
int a[]={1,4,5,7,9,10,2,3,8,6};
printf("\nbegin sort:");
for(int i=0 ;i<10;i++)
printf("%3d ",a[i]);
quicksort(a,0,9);
printf("\nafert sort:");
for(int i=0 ;i<10;i++)
printf("%3d ",a[i]);
}
posted on 2008-07-28 19:35
fly 閱讀(165)
評論(0) 編輯 收藏 所屬分類:
C/C++學習