quiksort.cpp

数据结构课程中快速排序实现

// quiksort.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <stdio.h>

int partition(int array[10], int l, int r) 
{
	int X; 
	int i, j; 
	i = l; j = r; 
	X = array[j];

	while (i != j) 
	{
		while ((array[i] < X) && (j > i)) 
			i++;
		if (i < j) 
		{ 
			array[j] = array[i]; 
			j--; 
		}
		while ((array[j] > X) && (j > i)) 
			j--;
		if (i < j) 
		{ 
			array[i] = array[j]; 
			i++; 
		}
	}
	array[i] = X; 
	return i; 
}

void qsort(int array[10], int i, int j) 
{
	int k ;
	
	k = partition(array, i, j);

	if ((k-i) > 1) qsort(array, i, k-1); 
	if ((j-k) > 1) qsort(array, k+1, j); 
}

int main(int argc, char* argv[])
{
	int array[10]={2,6,1,7,3,5,4,8,3,9}; 
	int i,j;

	for(i=0;i<10;i++)
		printf("%5d",array[i]);
	printf("\n");

	qsort(array,0,9);

	for(i=0;i<10;i++)
		printf("%5d",array[i]);
	printf("\n");

	return 0;
}