快速排序（Quick Sort）C語言

背景

已知數組

src

如下：

快速排序1

在數組 src[low, high] 中，取 src[low] 作為 關鍵字（key） 。

通過 一趟快速排序 找到 key 的位置 keypos 。

keypos

将數組劃分為兩部分：

src[low, keypos - 1]

和

src[keypos + 1, high]

。

src[low, keypos - 1]

中的元素都 不大于

key

。

src[keypos + 1, high]

中的元素都 不小于

key

。

一趟快速排序 步驟如下：

1、定義兩個指針

left

和

right

， 初值為

low

和

high

。

2、定義關鍵字

key

， 初值為

src[low]

。

3、

right

向前搜尋，找到第 1 個 小于

key

的元素時，将

src[left]

和

src[right]

互換。

4、

left

向後搜尋，找到第 1 個 大于

key

的元素時，将

src[left]

和

src[right]

互換。

5、 重複 3，4，直到

left = right

時結束。

快速排序2

通過上面的步驟可以發現，我們互換的資料有 1 個數關鍵字，但是關鍵字我們已經記錄在 key 中，是以不需要将關鍵字不停的互換。隻需要将另一個值移動即可。

快速排序2（C代碼）

/*********************************************************************
Function: 快速排序2
Description：将數組src[low,high]升序排序
Parameters: src:  待排序數組
			low:  起始下标
			high: 結束下标
Return Value: 排序完成傳回0，否則-1
Author: wowpH
Date: 2019-11-12 21:57:42
Reference: 資料結構（C語言版）嚴蔚敏 吳偉民 清華大學出版社
*********************************************************************/
int quick_sort_two(int src[], int low, int high) {
	if (low < 0 || low >= high) {
		return -1;// 下标不合法
	}
	int key = src[low];// 将第1個作為關鍵字
	int left = low;// 左邊界
	int right = high;// 右邊界
	while (left < right) {// 兩端交替向中間掃描
		// 在右邊查找比關鍵字小的資料
		while (left < right && src[right] >= key) {
			--right;
		}
		src[left] = src[right];// 将比關鍵字小的移動到左邊
		// 在左邊查找比關鍵字大的資料
		while (left < right && src[left] <= key) {
			++left;
		}
		src[right] = src[left];// 将比關鍵字大的移動到右邊
	}
	src[left] = key;// 此時left就是一趟快速排序後的關鍵字所在的位置
	quick_sort_two(src, low, left - 1);// 對左邊的資料遞歸排序
	quick_sort_two(src, left + 1, high);// 對右邊的資料遞歸排序
	return 0;
}
           

快速排序視訊

- End - wowpH - pfdvnah -