快速排序（快排）——C語言實作

時間複雜度： 快速排序（quicksort）的平均運作時間是O(N·logN)，最壞情形是O(N^2)。

算法思想： 是一種分治的遞歸算法。如果是升序排序，則首先選取一個元素key，将小于key的元素放在左邊，小于key的元素放在右邊。再對左右進行類似的操作，直到排序完成。

個人覺得快排涉及的還挺多，如key的選取，程式的遞歸與非遞歸實作等。

我的代碼是簡單的遞歸實作，後續學習再一點點補充吧。

①先動右指針，找到比key小的元素，此時右指針指向這個元素，然後用這個元素的值覆寫掉左指針指向的元素；

②再動左指針，找到比key大的元素，此時左指針指向這個元素，然後用這個元素的值覆寫掉右指針指向的元素；

③直到左右指針相遇（i==j），此時用key的值覆寫目前左或右指針指向的元素；

④左遞歸；

⑤右遞歸。

/*	快排1.0
*	作者：Talentq
*	日期：2020.8.15
*/
#include <stdio.h>

void quickSort(int array[], int left, int right);

int main(void)
{
	int i;
	int array[] = { 5,4,3,2,1,10,9,8,7,6 };	//待排序數組
	int len = sizeof(array) / sizeof(int);	//數組的長度

	quickSort(array, 0, len - 1);	//排序

	for (i = 0; i < 10; i++)	//列印排序後的數組
		printf("%d\n", array[i]);

	return 0;
}

void quickSort(int array[], int left, int right)
{
	int i, j, key;
	if (left >= right)
		return;
	i = left; j = right;
	key = array[i];	//取最左邊的元素作為key
	while (i < j)
	{	//始終保持i < j
		while (i < j && array[j] > key)//右指針向左
			j--;
		if (i < j)	//小于key的放左邊
			array[i++] = array[j];

		while (i < j && array[i] < key)//左指針向右
			i++;
		if (i < j)	//大于key的放右邊
			array[j--] = array[i];
	}
	array[i] = key;	//最終将key放入i==j處

	quickSort(array, left, i - 1);	//左邊遞歸
	quickSort(array, i + 1, right);	//右邊遞歸
}