快速排序演算法例題
排序演算法是《資料結構與演算法》中最基本的演算法之一。排序演算法可以分為內部排序和外部排序,內部排序是資料記錄在記憶體中進行排序,而外部排序是因排序的資料很大,一次不能容納全部的排序記錄,在排序過程中需要訪問外存。常見的內部排序演算法有:插入排序、希爾排序、選擇排序、氣泡排序、歸併排序、快速排序、堆排序、基數排序等。以下是快速排序演算法:
快速排序是由東尼·霍爾所發展的一種排序演算法。在平均狀況下,排序 n 個專案要 Ο(nlogn) 次比較。在最壞狀況下則需要 Ο(n2) 次比較,但這種狀況並不常見。事實上,快速排序通常明顯比其他 Ο(nlogn) 演算法更快,因為它的內部迴圈(inner loop)可以在大部分的架構上很有效率地被實現出來。
快速排序使用分治法(Divide and conquer)策略來把一個序列(list)分為兩個子序列(sub-lists)。
快速排序又是一種分而治之思想在排序演算法上的典型應用。本質上來看,快速排序應該算是在氣泡排序基礎上的遞迴分治法。
快速排序的名字起的是簡單粗暴,因為一聽到這個名字你就知道它存在的意義,就是快,而且效率高!它是處理大資料最快的排序演算法之一了。雖然 Worst Case 的時間複雜度達到了 O(n?),但是人家就是優秀,在大多數情況下都比平均時間複雜度為 O(n logn) 的排序演算法表現要更好,可是這是為什麼呢,我也不知道。好在我的強迫症又犯了,查了 N 多資料終於在《演算法藝術與資訊學競賽》上找到了滿意的答案:
快速排序的最壞執行情況是 O(n?),比如說順序數列的快排。但它的平攤期望時間是 O(nlogn),且 O(nlogn) 記號中隱含的常數因子很小,比複雜度穩定等於 O(nlogn) 的歸併排序要小很多。所以,對絕大多數順序性較弱的隨機數列而言,快速排序總是優於歸併排序。
1. 演算法步驟
從數列中挑出一個元素,稱為 "基準"(pivot);
重新排序數列,所有元素比基準值小的擺放在基準前面,所有元素比基準值大的擺在基準的後面(相同的數可以到任一邊)。在這個分割槽退出之後,該基準就處於數列的中間位置。這個稱為分割槽(partition)操作;
遞迴地(recursive)把小於基準值元素的子數列和大於基準值元素的子數列排序;
2. 動圖演示
程式碼實現
JavaScript
例項
function quickSort(arr, left, right) {var len = arr.length,
partitionIndex,
left = typeof left != 'number' ? 0 : left,
right = typeof right != 'number' ? len - 1 : right;
if (left < right) {
partitionIndex = partition(arr, left, right);
quickSort(arr, left, partitionIndex-1);
quickSort(arr, partitionIndex+1, right);
}
return arr;
}
function partition(arr, left ,right) { // 分割槽操作
var pivot = left, // 設定基準值(pivot)
index = pivot + 1;
for (var i = index; i <= right; i++) {
if (arr[i] < arr[pivot]) {
swap(arr, i, index);
index++;
}
}
swap(arr, pivot, index - 1);
return index-1;
}
function swap(arr, i, j) {
var temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
function partition2(arr, low, high) {
let pivot = arr[low];
while (low < high) {
while (low < high && arr[high] > pivot) {
--high;
}
arr[low] = arr[high];
while (low < high && arr[low] <= pivot) {
++low;
}
arr[high] = arr[low];
}
arr[low] = pivot;
return low;
}
function quickSort2(arr, low, high) {
if (low < high) {
let pivot = partition2(arr, low, high);
quickSort2(arr, low, pivot - 1);
quickSort2(arr, pivot + 1, high);
}
return arr;
}
Python
例項
def quickSort(arr, left=None, right=None):left = 0 if not isinstance(left,(int, float)) else left
right = len(arr)-1 if not isinstance(right,(int, float)) else right
if left < right:
partitionIndex = partition(arr, left, right)
quickSort(arr, left, partitionIndex-1)
quickSort(arr, partitionIndex+1, right)
return arr
def partition(arr, left, right):
pivot = left
index = pivot+1
i = index
while i <= right:
if arr[i] < arr[pivot]:
swap(arr, i, index)
index+=1
i+=1
swap(arr,pivot,index-1)
return index-1
def swap(arr, i, j):
arr[i], arr[j] = arr[j], arr[i]
Go
例項
func quickSort(arr []int) []int {return _quickSort(arr, 0, len(arr)-1)
}
func _quickSort(arr []int, left, right int) []int {
if left < right {
partitionIndex := partition(arr, left, right)
_quickSort(arr, left, partitionIndex-1)
_quickSort(arr, partitionIndex+1, right)
}
return arr
}
func partition(arr []int, left, right int) int {
pivot := left
index := pivot + 1
for i := index; i <= right; i++ {
if arr[i] < arr[pivot] {
swap(arr, i, index)
index += 1
}
}
swap(arr, pivot, index-1)
return index - 1
}
func swap(arr []int, i, j int) {
arr[i], arr[j] = arr[j], arr[i]
}
C++
例項
//嚴蔚敏《資料結構》標準分割函式Paritition1(int A[], int low, int high) {
int pivot = A[low];
while (low < high) {
while (low < high && A[high] >= pivot) {
--high;
}
A[low] = A[high];
while (low < high && A[low] <= pivot) {
++low;
}
A[high] = A[low];
}
A[low] = pivot;
return low;
}
void QuickSort(int A[], int low, int high) //快排母函式
{
if (low < high) {
int pivot = Paritition1(A, low, high);
QuickSort(A, low, pivot - 1);
QuickSort(A, pivot + 1, high);
}
}
Java
例項
public class QuickSort implements IArraySort {@Override
public int[] sort(int[] sourceArray) throws Exception {
// 對 arr 進行拷貝,不改變引數內容
int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);
return quickSort(arr, 0, arr.length - 1);
}
private int[] quickSort(int[] arr, int left, int right) {
if (left < right) {
int partitionIndex = partition(arr, left, right);
quickSort(arr, left, partitionIndex - 1);
quickSort(arr, partitionIndex + 1, right);
}
return arr;
}
private int partition(int[] arr, int left, int right) {
// 設定基準值(pivot)
int pivot = left;
int index = pivot + 1;
for (int i = index; i <= right; i++) {
if (arr[i] < arr[pivot]) {
swap(arr, i, index);
index++;
}
}
swap(arr, pivot, index - 1);
return index - 1;
}
private void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
PHP
例項
function quickSort($arr){
if (count($arr) <= 1)
return $arr;
$middle = $arr[0];
$leftArray = array();
$rightArray = array();
for ($i = 1; $i < count($arr); $i++) {
if ($arr[$i] > $middle)
$rightArray[] = $arr[$i];
else
$leftArray[] = $arr[$i];
}
$leftArray = quickSort($leftArray);
$leftArray[] = $middle;
$rightArray = quickSort($rightArray);
return array_merge($leftArray, $rightArray);
}
C
例項
typedef struct _Range {int start, end;
} Range;
Range new_Range(int s, int e) {
Range r;
r.start = s;
r.end = e;
return r;
}
void swap(int *x, int *y) {
int t = *x;
*x = *y;
*y = t;
}
void quick_sort(int arr[], const int len) {
if (len <= 0)
return; // 避免len等於負值時引發段錯誤(Segment Fault)
// r[]模擬列表,p為數量,r[p++]為push,r[--p]為pop且取得元素
Range r[len];
int p = 0;
r[p++] = new_Range(0, len - 1);
while (p) {
Range range = r[--p];
if (range.start >= range.end)
continue;
int mid = arr[(range.start + range.end) / 2]; // 選取中間點為基準點
int left = range.start, right = range.end;
do {
while (arr[left] < mid) ++left; // 檢測基準點左側是否符合要求
while (arr[right] > mid) --right; //檢測基準點右側是否符合要求
if (left <= right) {
swap(&arr[left], &arr[right]);
left++;
right--; // 移動指標以繼續
}
} while (left <= right);
if (range.start < right) r[p++] = new_Range(range.start, right);
if (range.end > left) r[p++] = new_Range(left, range.end);
}
}
遞迴法
例項
void swap(int *x, int *y) {int t = *x;
*x = *y;
*y = t;
}
void quick_sort_recursive(int arr[], int start, int end) {
if (start >= end)
return;
int mid = arr[end];
int left = start, right = end - 1;
while (left < right) {
while (arr[left] < mid && left < right)
left++;
while (arr[right] >= mid && left < right)
right--;
swap(&arr[left], &arr[right]);
}
if (arr[left] >= arr[end])
swap(&arr[left], &arr[end]);
else
left++;
if (left)
quick_sort_recursive(arr, start, left - 1);
quick_sort_recursive(arr, left + 1, end);
}
void quick_sort(int arr[], int len) {
quick_sort_recursive(arr, 0, len - 1);
}
C++
函式法
sort(a,a + n);// 排序a[0]-a[n-1]的所有數.
迭代法
例項
// 參考:http://www.dutor.net/index.php/2011/04/recursive-iterative-quick-sort/struct Range {
int start, end;
Range(int s = 0, int e = 0) {
start = s, end = e;
}
};
template <typename T> // 整數或浮點數皆可使用,若要使用物件(class)時必須設定"小於"(<)、"大於"(>)、"不小於"(>=)的運運算元功能
void quick_sort(T arr[], const int len) {
if (len <= 0)
return; // 避免len等於負值時宣告堆疊陣列當機
// r[]模擬堆疊,p為數量,r[p++]為push,r[--p]為pop且取得元素
Range r[len];
int p = 0;
r[p++] = Range(0, len - 1);
while (p) {
Range range = r[--p];
if (range.start >= range.end)
continue;
T mid = arr[range.end];
int left = range.start, right = range.end - 1;
while (left < right) {
while (arr[left] < mid && left < right) left++;
while (arr[right] >= mid && left < right) right--;
std::swap(arr[left], arr[right]);
}
if (arr[left] >= arr[range.end])
std::swap(arr[left], arr[range.end]);
else
left++;
r[p++] = Range(range.start, left - 1);
r[p++] = Range(left + 1, range.end);
}
}
遞迴法
例項
template <typename T>void quick_sort_recursive(T arr[], int start, int end) {
if (start >= end)
return;
T mid = arr[end];
int left = start, right = end - 1;
while (left < right) { //在整個範圍內搜尋比樞紐元值小或大的元素,然後將左側元素與右側元素交換
while (arr[left] < mid && left < right) //試圖在左側找到一個比樞紐元更大的元素
left++;
while (arr[right] >= mid && left < right) //試圖在右側找到一個比樞紐元更小的元素
right--;
std::swap(arr[left], arr[right]); //交換元素
}
if (arr[left] >= arr[end])
std::swap(arr[left], arr[end]);
else
left++;
quick_sort_recursive(arr, start, left - 1);
quick_sort_recursive(arr, left + 1, end);
}
template <typename T> //整數或浮點數皆可使用,若要使用物件(class)時必須設定"小於"(<)、"大於"(>)、"不小於"(>=)的運運算元功能
void quick_sort(T arr[], int len) {
quick_sort_recursive(arr, 0, len - 1);
}
參考地址:
https://github.com/hustcc/JS-Sorting-Algorithm/blob/master/6.quickSort.md
https://zh.wikipedia.org/wiki/%E5%BF%AB%E9%80%9F%E6%8E%92%E5%BA%8F
以下是熱心網友對快速排序演算法的補充,僅供參考:
熱心網友提供的補充1:
上方沒有C#實現,我補充一下,如下所示:
//快速排序(目標陣列,陣列的起始位置,陣列的終止位置)static void QuickSort(int[] array, int left = 0, int right = -1){ if (right.Equals(-1)) right = array.Length - 1; try { int keyValuePosition; //記錄關鍵值的下標 //當傳遞的目標陣列含有兩個以上的元素時,進行遞迴呼叫。(即:當傳遞的目標陣列只含有一個元素時,此趟排序結束) if (left < right) { keyValuePosition = Partion(array, left, right); //獲取關鍵值的下標(快排的核心) QuickSort(array, left, keyValuePosition - 1); //遞迴呼叫,快排劃分出來的左區間 QuickSort(array, keyValuePosition + 1, right); //遞迴呼叫,快排劃分出來的右區間 } } catch (Exception ex) { Console.WriteLine("Exception: {0}", ex); }}///快速排序的核心部分:確定關鍵值在陣列中的位置,以此將陣列劃分成左右兩區間,關鍵值遊離在外。(返回關鍵值應在陣列中的下標)static int Partion(int[] array, int left, int right){ int leftIndex = left; //記錄目標陣列的起始位置(後續動態的左側下標) int rightIndex = right; //記錄目標陣列的結束位置(後續動態的右側下標) int keyValue = array[left]; //陣列的第一個元素作為關鍵值 int temp; //當 (左側動態下標 == 右側動態下標) 時跳出迴圈 while (leftIndex < rightIndex) { while (leftIndex < rightIndex && array[leftIndex] <= keyValue) //左側動態下標逐漸增加,直至找到大於keyValue的下標 { leftIndex++; } while (leftIndex < rightIndex && array[rightIndex] > keyValue) //右側動態下標逐漸減小,直至找到小於或等於keyValue的下標 { rightIndex--; } if (leftIndex < rightIndex) //如果leftIndex < rightIndex,則交換左右動態下標所指定的值;當leftIndex==rightIndex時,跳出整個迴圈 { temp = array[leftIndex]; array[leftIndex] = array[rightIndex]; array[rightIndex] = temp; } } //當左右兩個動態下標相等時(即:左右下標指向同一個位置),此時便可以確定keyValue的準確位置 temp = keyValue; if (temp < array[rightIndex]) //當keyValue < 左右下標同時指向的值,將keyValue與rightIndex - 1指向的值交換,並返回rightIndex - 1 { array[left] = array[rightIndex - 1]; array[rightIndex - 1] = temp; return rightIndex - 1; } else //當keyValue >= 左右下標同時指向的值,將keyValue與rightIndex指向的值交換,並返回rightIndex { array[left] = array[rightIndex]; array[rightIndex] = temp; return rightIndex; }}
熱心網友提供的補充2:
補充 scala 實現版本:
/** * @Auther: huowang * @Date: 19:34:47 2020/12/10 * @DES: 分割槽交換演算法(快速排序發) * @Modified By: */object PartitionExchange { /** * 分割槽內切割 * @param arr * @param left * @param right * @return */ def partition(arr:Array[Int],left:Int,right: Int):Int={ // 獲取基準元素 直接選取最右側一個元素為基準元素 val pv=arr(right) // 把最左邊一個索引作為堆疊索引 var storeIndex=left //運算元組 -1是因為 最右邊一個元素是基準元素 for (i <- left to right-1 ){ if(arr(i)<=pv){ //把小於基準元素的元素 都堆到集合左端 swap(arr,storeIndex,i) // 把用於堆疊索引往前移動一個 storeIndex=storeIndex+1 } //如果出現了比基準元素大的元素,那麼則不會移動堆疊索引 // 但是如果之後又出現了比基準元素小的元素,那邊會與這個大的元素交換位置 // 進而使大的元素永遠出現在堆疊索引右側 } // 這裡最有右的元素,其實是基準元素,我們把基準元素和最後堆疊索引對應的元素調換位置 // 這樣基準元素左邊就都是大於它的元素了 swap(arr,right,storeIndex) // 返回堆疊索引位置,目前堆疊索引指向的就是基準元素 storeIndex }def quicksort(arr:Array[Int],left: Int,right: Int):Array[Int]={ if(right>left){ // 左右索引不重合 // 隨便選擇一個元素作為基準 就選擇最左邊的吧 var pivotIndex=0 // 切割返回基準元素 pivotIndex= partition(arr,left,right) // 遞迴對切割形成的兩個子集進行排序 quicksort(arr,left,pivotIndex-1) quicksort(arr,pivotIndex,right) } arr } /** * 調換 a b 元素在陣列中的位置 * @param arr * @param a * @param b */ def swap(arr:Array[Int],a:Int,b:Int)={ val tmp=arr(a) arr(a)=arr(b) arr(b)=tmp }def main(args: Array[String]): Unit = { // 測試 val arr=Array(5, 2, 9,11,3,6,8,4,0,0) val arrNew=quicksort(arr,0,arr.size-1) println(arrNew.toList.mkString(",")) }}
熱心網友提供的補充3:
補充一下迭代法的 python 實現:
def _partition(array:list, start:int, end:int) -> int: """ 將陣列指定片段進行左右劃分,首先選擇中位元素為中值。 比中位元素小的置於其左,與中位元素相等或比中位元素大的置於其右, 最後返回中位元素的下標位置。 """ # 以中位元素為中值劃分,儘量避免極端情況 mid = (start + end) >> 1 array[start], array[mid] = array[mid], array[start] # 劃分的實現 i, j = start, end x = array[start] while (i < j): if (i < j and array[j] >= x): j -= 1 array[i] = array[j] if (i < j and array[i] < x): i += 1 array[j] = array[i] array[i] = x return idef quickSort(array:list) -> list: """ 迭代法快速排序,佇列結構輔助實現。 """ sorted_array = array.copy() length = len(sorted_array) # 使用佇列儲存每次劃分的二元組:(起始下標,終止下標) queue = [] queue.append((0, length - 1)) # 佇列為空,則所有劃分操作執行完畢 while len(queue): left, right = queue.pop(0) pos = _partition(sorted_array, left, right) # 預設長度為 1 的序列有序,那麼區間長度 > 1 才需要劃分,才需要儲存到佇列中 if (left < pos - 1): queue.append((left, pos - 1)) if (pos + 1 < right): queue.append((pos + 1, right)) return sorted_arrayif __name__ == "__main__": array = [21, -17, 1, -27, 41, 17, -5, -49] sorted_array = quickSort(array) print("排序前:{array1}排序後:{array2}".format(array1=array, array2=sorted_array))以上為快速排序演算法詳細介紹,插入排序、希爾排序、選擇排序、氣泡排序、歸併排序、快速排序、堆排序、基數排序等排序演算法各有優缺點,用一張圖概括:
關於時間複雜度
平方階 (O(n2)) 排序 各類簡單排序:直接插入、直接選擇和氣泡排序。
線性對數階 (O(nlog2n)) 排序 快速排序、堆排序和歸併排序;
O(n1+§)) 排序,§ 是介於 0 和 1 之間的常數。 希爾排序
線性階 (O(n)) 排序 基數排序,此外還有桶、箱排序。
關於穩定性
穩定的排序演算法:氣泡排序、插入排序、歸併排序和基數排序。
不是穩定的排序演算法:選擇排序、快速排序、希爾排序、堆排序。
名詞解釋:
n:資料規模
k:"桶"的個數
In-place:佔用常數記憶體,不佔用額外記憶體
Out-place:佔用額外記憶體
穩定性:排序後 2 個相等鍵值的順序和排序之前它們的順序相同
-
微博怎麼顯示手機型號,微博如何顯示手機型號
微博怎麼顯示手機型號:1、首先需要點選手機桌面中的微博。2、然後再點選螢幕右下方的我的。3、然後再點選螢幕上方的設定圖示。4、然後再點選會員專屬設定。5、然後再點選微博來源。6、最後選擇想要顯示的手機型號就可以了。...
-
qq空間無訪問許可權怎麼進入
如果你的qq好友設定了qq空間許可權,那麼是沒有辦法強制進入對方的空間的,只能通過正當方式訪問,得到空間許可權主人許可後進入;或者是通過回答問題,只要回答正確即可進入空間。QQ空間就像我們的日記本一樣,我們可以自由地在裡面記錄自己的心情,也可以把具有紀念意義的照片...
-
清潔手機的方法
1、準備溼紙巾、手機清潔劑、細小的清潔毛刷、清潔布(或像眼鏡布這類超細纖維材質的布)、吸塵貼紙。2、溼紙巾用於簡單清潔手機表面的汙垢和灰塵;手機清潔劑用於對手機外殼一些頑固的汙垢進行清理;毛刷可以用於對耳機孔、充電口或者機身一些縫隙進行灰塵清理;清潔布...
-
微信群裡怎麼拍一拍,具體操作步驟
1、操作步驟:首先開啟手機上的【微信】。2、開啟微信之後,我們點選開啟群好友【聊天視窗】。3、開啟聊天視窗後,我們快速雙擊【好友的頭像】。4、雙擊好友後,對方就收到訊息【拍了拍你】雙方的聊天視窗都會有提示。...