quicksort.cpp

快速排序(Quick Sort)是一种有效的排序算法。虽然算法在最坏的情况下运行时间为O(n^2)

#include<iostream>
#include<ctime>

using namespace std;

const static int ARRAYLENGTH = 50;

void quickSort(int array[] , int beg , int end);
int partition(int [] , int ,int );
void print(int[]);
void initial(int []);

int main()
{
	int array[ARRAYLENGTH];
	initial(array);
	print(array);
	quickSort(array , 0  ,ARRAYLENGTH-1);
	print(array);
	return 0;
}

void quickSort(int array[] , int beg , int end )
{
	if(beg < end)
	{
		int pos = partition(array , beg , end);
		quickSort(array, beg , pos - 1);
		quickSort(array , pos + 1 , end);
	}
}

void change(int array[] , int i , int j)
{
	int temp = array[i] + array[j];
	array[i] = temp - array[i];
	array[j] = temp - array[i];
}

int partition(int array[] , int beg , int end)
{
	int key = array[beg];
	int i = beg , j = i+1;
	for(;j<=end;++j)
	{
		if(array[j]<key)
		{
			++i;
			change(array , i , j);
		}
	}
	change(array , beg , i);
	return i;
}

void print(int array[])
{
	for(int i = 0 ; i < ARRAYLENGTH ; ++i )
	{
		cout<<array[i]<<" ";
	}
	cout<<endl;
}

void initial(int array[])
{
	srand(time(NULL));
	for(int i = 0 ; i < ARRAYLENGTH ; ++i )
	{
		array[i] = rand() % 100;
	}
}