快速排序

快速排序

根据王道书上的代码，对快速排序做整理。

快速排序的思想是：

• 使用双指针法，将第一个元素放在表中合适的位置，使得这个位置左面的元素都小于这个元素，右面的元素都大于等于这个元素。
• 递归的处理这个元素分割而成的两个子表，使得有序。

在编写相关的额代码的时候，一定一定一定要注意函数的退出条件和循环的退出条件

快速排序调用的深度和对应二叉树的深度相同。

快速排序的最好时间复杂度是O(log2n)，最坏时间复杂度是O(n^2)

快速排序的最好空间复杂度是O(log2n)，最坏空间复杂度是O(n)

# include <stdio.h>
# include <stdlib.h>
# include <time.h>
 
# define LENGTH 10
int i = 0;

void CreateList(int * data, int len)
{
	int i = 0;
	srand(time(NULL));
	for (i=0; i<len; i++) {
		data[i] = rand() % 100;
	}
	return;
}
 
void PrintList(int * data, int len)
{
	int i = 0;
	for (i=0; i<len; i++) {
		printf("%d ", data[i]);
	}
	printf("\n");
	return;
}

// 将首元素放在合适的位置，返回放置的位置
int Partition(int * data, int low, int high)
{
	int middle = data[low];								// 提前将元素保存出来，防止覆盖
	while (low < high) {
		while(low < high && data[high] >= middle) {		// 注意每次移动指针都需要判断指针的关系
			high--;
		}
		data[low] = data[high];
		while (low < high && data[low] < middle) {
			low++;
		}
		data[high] = data[low];
	}
	data[low] = middle;
	return low;
}

// 快速排序主函数
void QuickSort(int * data, int low, int high)
{
	if (low < high) {
		int middle = Partition(data, low, high);
		printf("%2d th sort: ", ++i);
		PrintList(data, LENGTH);
		QuickSort(data, low, middle - 1);				// 左子序列
		QuickSort(data, middle + 1, high);				// 右子序列
	}
	return;
}
 
int main(void)
{
	int * data = (int *)malloc(sizeof(int) * LENGTH);
	CreateList(data, LENGTH);
 
	printf("Before sort: ");
	PrintList(data, LENGTH);
	QuickSort(data, 0, LENGTH - 1);
	printf("After sort: ");
	PrintList(data, LENGTH);
	
	return 0;
}