18.4 快速排序

18.4 快速排序

快速排序分两步进行：
1: 把长度为n的输入数列分为两部分，分割条件是先从数列中找到一个哨兵(通常可以将数列中的首元素作为哨兵)，要求数列前半部分的值全部比哨兵小，后半部分全部比哨兵值大。
2: 将分割完的两部分分别进行快速排序。

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define LEN 9

void init(int num[], int len)
{
	int i;

	srand(time(NULL));
	for (i = 0; i < len; i++)
		printf("%d ",num[i] = rand() % 100);
	printf("\n");
}

void swap(int num[], int i, int j)
{
	int tmp = num[i];
	num[i] = num[j];
	num[j] = tmp;
}

int partition(int num[], int start, int end)
{
	int last, key, i;

	key = num[start];
	last = start;

	for (i = last + 1; i <= end; i++) {
		if (num[i] < key)
			swap(num, ++last, i);
	}
	swap(num, start, last);
	return last;
}

void sort(int num[], int start, int end)
{
	int mid;
	
	if (start < end) {
		mid = partition(num, start, end);
		sort(num, start, mid - 1);
		sort(num, mid + 1, end);
	}
}

int main(void)
{
	int num[LEN], i;

	init(num, LEN);
	sort(num, 0, LEN);
	for (i = 0; i < LEN; i++)
		printf("%d ", num[i]);
	printf("\n");

	return 0;
}