随笔 - 100  文章 - 50  trackbacks - 0
<2019年12月>
24252627282930
1234567
891011121314
15161718192021
22232425262728
2930311234

常用链接

留言簿(3)

随笔分类

随笔档案

文章分类

文章档案

收藏夹

我收藏的一些文章!

搜索

  •  

最新评论

阅读排行榜

评论排行榜

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

只有注册用户登录后才能发表评论。


网站导航: