quicksort.cpp

包含各种测试,查找和算法等代码,如冒泡算法,树的遍历,链表,队列,堆栈等

#include <iostream.h>
#include "datatype.h"

void QuickSort(datatype a[], int low, int high)
//用递归方法对对象a[low]--a[high]进行快速排序
{
	int i, j;
	datatype temp;

	i = low;
	j = high;
	temp = a[low];

	while(i < j)
	{
		//在数组的右端扫描
		while(i < j && temp.key <= a[j].key) j--;
		if(i < j)
		{
			a[i] = a[j];
			i++;
		}

		//在数组的左端扫描
		while(i < j && a[i].key < temp.key) i++;
		if(i < j)
		{
			a[j] = a[i];
			j--;
		}
	}
	a[i] = temp;

	//对子对象数组进行递归快速排序
	if(low < i) QuickSort(a, low, i-1);
	if(i < high) QuickSort(a, j+1, high);
}

void main(void)
{
	datatype test[]={60,55,48,37,10,90,84,36};
	int n = 8;
	QuickSort(test, 0, 7);
	for(int i = 0; i < n; i++)
		cout << test[i].key << "  ";
}