#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 阅读(160)
评论(0) 编辑 收藏 所属分类:
C/C++学习