[排序]快速排序算法實作

作者	zhonglihao
算法名	快速排序 Quick Sort
分類	排序
複雜度	nlogn型
形式與資料結構	C++代碼，一維數組
特性	原址排序特性
具體參考出處	《算法導論》
備注

// quick_sort.cpp : 定義控制台應用程式的入口點。
//

#include "stdafx.h"
#include <iostream>
#include <stdlib.h>
#include <time.h>

#define data_num 20

void quick_sort(unsigned int *data, int p, int r);
int partition(unsigned int *data, int p, int r);

int _tmain(int argc, _TCHAR* argv[])
{
	int i, j, k;
	unsigned int data_array[data_num];

	srand(83301546);
	for (i = 0; i < data_num; i++)
	{
		data_array[i] = rand();
		printf("%d ", data_array[i]);
	}
	printf("\n\n");

	quick_sort(data_array, 0, data_num - 1);

	for (i = 0; i < data_num; i++)
	{
		printf("%d ", data_array[i]);
	}
	printf("\n\n");

	while (1);
	return 0;
}

void quick_sort(unsigned int *data, int p, int r)
{
	int q = 0;

	if (p < r)
	{
		q = partition(data, p, r);
		quick_sort(data, p, q-1);
		quick_sort(data, q+1, r);
	}
}

//總是把比哨兵小的放左邊，不斷遞歸，分治
int partition(unsigned int *data, int p, int r)
{
	int i, j;
	unsigned int x, temp;

	x = data[r];
	i = p - 1;

	for (j = p; j <= (r - 1);j++)
	{
		if (data[j] < x)
		{
			i = i + 1;
			temp = data[j];
			data[j] = data[i];
			data[i] = temp;
		}
	}
	temp = data[r];
	data[r] = data[i+1];
	data[i+1] = temp;

	return (i + 1);
}