劃分交換排序

劃分交換排序又稱為快速排序，是在冒泡排序基礎上改進的一種排序方法，它利用不斷分割排序區間的方法進行排序，即通過一趟排序，將待排序的數據序列分割為獨立的兩個部分，其中一部分元素的關鍵字均比另一部分元素的關鍵字小，然後再分別對這兩個部分的元素繼續排序，直到整個數據序列有序。

基本介紹

• 中文名：劃分交換排序
• 外文名：partition exchange sorting
• 別名：快速排序
• 基礎：冒泡排序
• 定義：通過排序，直到數據序列有序
• 套用學科：計算機原理

基本原理

快速排序是C.R.A.Hoare於1962年提出的一種劃分交換排序。它採用了一種分治的策略，通常稱其為分治法(Divide-and-ConquerMethod)。

快速排序由於排序效率在同為O(N*logN)的幾種排序方法中效率較高，因此經常被採用，再加上快速排序思想----分治法也確實實用。

快速排序的基本思想是：

1. 先從數列中取出一個數作為基準數。
2. 分區過程，將比這個數大的數全放到它的右邊，小於或等於它的數全放到它的左邊。
3. 再對左右區間重複第二步，直到各區間只有一個數，達到整個序列有序。

具體方法描述

具體的方法描述如下：在當前無序區R[1]到R[h]到中任取一個記錄作為比較的“基準”(通常取第一個記錄的值為基準值，記為pivot)，用此基準將當前無序區劃分為左右兩個較小的無序子區：R[1]到R[i—1]和R[i+1]到R[h]．且左邊的無序子區中記錄的關鍵字均小於或等於基準pivot的關鍵字，右邊的無序子區中記錄的關鍵字均大於或等於基準pivot的關鍵字，而基準pivot則位於最終排序的位置i上，這個過程稱為一次劃分。

為方便實現該算法。附設兩個指針low和high，初值分別指向第一個記錄和最後一個記錄。首先從high所指位置起向前搜尋，找到第一個小於基準值的記錄與基準記錄交換，然後從low所指位置起向後搜尋，找到第一個大於基準值的記錄與基準記錄交換，重複這兩步直至low=high為止。當R[l]到R[i一1]和R[i+1]到R[h]均非空時，分別對它們進行上述的劃分過程，直至所有無序子區中記錄均已排好序為止。