資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
服裝學
法學C++快速排序程式？
快速排序是一種使用比較來對未排序列表（陣列）進行排序的排序技術。快速排序也稱為分割槽交換排序。
它不是穩定的排序，因為相等排序項的相對順序不會保留。快速排序可以在陣列上執行，只需要少量額外的記憶體來執行排序。它與選擇排序非常相似，只是它並不總是選擇最壞情況下的分割槽。因此，我們可以將其視為改進的選擇排序。
快速排序是最有效的排序演算法之一，它基於將陣列分成更小的陣列。名稱來源於快速排序能夠比任何常見的排序演算法更快地對資料元素列表進行排序的事實。與歸併排序一樣，快速排序也屬於分治法解決問題的範疇。
快速排序演算法的工作方式如下：
從類比的角度來看，考慮一下需要按姓名對印有學生姓名的紙張進行排序的情況。可以使用如下方法：
選擇一個分割值，例如L。分割值也稱為**樞軸**。
將紙張分成兩堆：A-L和M-Z。這兩堆不必大小相等。
對A-L堆重複上述兩個步驟，將其分成兩半。同樣對M-Z堆進行劃分。重複此過程，直到堆足夠小，易於排序。
最終，可以將較小的堆疊在一起，形成一個完全排序的有序紙張集合。
這裡使用的方法是在每次分割時使用**遞迴**來得到單元素陣列。
在每次分割中，堆都被劃分，然後對較小的堆使用相同的方法。
由於這些特性，快速排序也稱為**分割槽交換排序**。
Input: arr[] = {7,4,2,6,3,1,5}
Output: 1 2 3 4 5 6 7解釋
一個例子可能有助於理解這個概念。考慮以下陣列：50, 23, 9, 18, 61, 32
**步驟1** - 從列表中決定任何值作為樞軸（通常是最後一個值）。假設有兩個值“Low”和“High”，分別對應第一個索引和最後一個索引。
在我們的例子中，low為0，high為5。
low和high處的值分別為50和32，樞軸值為32。
因此，呼叫分割槽函式，重新排列陣列，使樞軸（32）到達其實際位置。並且在樞軸的左側，陣列的所有元素都小於它，在右側大於它。
在分割槽函式中，我們從第一個元素開始，並將其與樞軸進行比較。由於50大於32，我們不做任何更改，並繼續下一個元素23。
再次與樞軸進行比較。由於23小於32，我們交換50和23。陣列變為23, 50, 9, 18, 61, 32。
我們繼續下一個元素9，它也小於樞軸（32），因此與50交換後，我們的陣列變為：
23, 9, 50, 18, 61, 32.
類似地，對於下一個元素18（小於32），陣列變為：
23, 9, 18, 50, 61, 32 現在61大於樞軸（32），因此沒有變化。
最後，我們將樞軸與50交換，使其到達正確的位置。
因此，樞軸（32）到達其實際位置，其左側的所有元素都小於它，右側的所有元素都大於它。
**步驟2** - 因此，第一步之後的陣列變為：
23, 9, 18, 32, 61, 50，取32作為樞軸。
**步驟3** - 現在列表被分成兩部分：
1. 樞軸之前的子列表：23, 9, 18
2. 樞軸之後的子列表：61, 50
**步驟4** - 對這些子列表再次重複這些步驟。
因此，最終陣列變為9, 18, 23, 32, 50, 61。
示例
#include <stdio.h>
void swap(int *a, int *b) {
int temp;
temp = *a;
*a = *b;
*b = temp;
}
int Partition(int a[], int low, int high) {
int pivot, index, i;
index = low;
pivot = high;
for(i=low; i < high; i++) {
if(a[i] < a[pivot]) {
swap(&a[i], &a[index]);
index++;
}
}
swap(&a[pivot], &a[index]);
return index;
}
int RandomPivotPartition(int a[], int low, int high) {
int pvt, n, temp;
n = rand();
pvt = low + n%(high-low+1);
swap(&a[high], &a[pvt]);
return Partition(a, low, high);
}
int QuickSort(int a[], int low, int high) {
return 0;
}
int main() {
int n, i;
n=7;
int arr[]={7,4,2,6,3,1,5};
int high = n-1;
int low = 0 ;
int pindex;
if(low < high) {
pindex = RandomPivotPartition(arr, low, high);
QuickSort(arr, low, pindex-1);
QuickSort(arr, pindex+1, high);
}
for (i = 0; i < n; i++)
printf("%d ", arr[i]);
return 0;
}
1K+ 次瀏覽
