quicksort.cpp

来自「此文件夹中共包括十二个小程序 AVL创建平衡二叉树,通过加入一个个的结点创建,」· C++ 代码 · 共 69 行

#include <stdio.h>
#include <iostream.h>
#include <stdlib.h>

//对A[s]至A[t]的元素进行快速排序
void QuickSort(int A[],int s,int t)
{
	int i=s,j=t;
	int temp;
	if(s<t)  //区间内至少存在一个元素的情况
	{
		temp=A[s];  //用区间的第1个记录作为基准
		while(i!=j)  //从区间两端交替向中间扫描，直至i=j为止
		{
			while(j>i&&A[j]>temp)
				j--;  //从右向左扫描，找第1个关键字小于temp的A[j]
			if(i<j)  //表示找到这样的A[j],A[i]与A[j]交换
			{
				A[i]=A[j]; 
				i++;
			}

			while(i<j&&A[i]<temp)
				i++;  //从左向右扫描，找第1个关键字大于temp的A[i]
			if(i<j)  //表示找到这样的A[i],A[i]与A[j]交换
			{
				A[j]=A[i]; 
				j--;
			}
		}
		A[i]=temp;  //将基准放入适当的位置

		cout<<endl;  //输出每一趟排序结果
		for(int k=0;k<10;k++)
			if(k==i)
				printf("  [%d]",A[k]);
			else
				printf("%4d",A[k]);
	
		QuickSort(A,s,i-1);  //对左区间递归排序
		QuickSort(A,i+1,t);  //对右区间递归排序
	}
}

void main()
{
	int k,n=10;
	int a[10]={6,18,7,9,10,1,3,12,4,5};

	cout<<"初始关键字为："<<endl;
	for(k=0;k<n;k++)
		printf("%4d",a[k]);
	cout<<endl;

	cout<<"快速排序过程为："<<endl;
	QuickSort(a,0,n-1);

	cout<<endl;
	cout<<"最后结果为： "<<endl;
	for(k=0;k<n;k++)
		printf("%4d",a[k]);
	cout<<endl;

	system("PAUSE");
}