什么是快速排序？

快速排序（Quick Sort） 是一種高效的分治法排序算法。它通過選擇一個基準元素，將數組分成小于基準的部分和大于基準的部分，然后遞歸地對這些部分進行排序，最終將它們合并起來，完成排序。

快速排序的步驟

1、選擇樞軸（基準元素）：從待排序的數組中選擇一個元素作為樞軸。常見的選擇方式是取第一個元素、最后一個元素、隨機元素或通過三數取中法選擇中間值作為樞軸。

2、劃分操作：將數組中的元素按照與樞軸的大小關系進行劃分，將小于等于樞軸的元素放在樞軸的左側，大于樞軸的元素放在樞軸的右側。這一步驟通常使用雙指針法來實現，即從數組的兩端同時向中間遍歷，交換不符合條件的元素，直到兩個指針相遇。

3、遞歸排序：對劃分后的左側子數組和右側子數組分別進行遞歸調用快速排序算法，重復上述步驟，直到子數組的長度為1或為空，即無法再繼續劃分。

4、合并結果：當遞歸調用完成后，所有的子數組都已經有序。最后，將左側子數組、樞軸元素和右側子數組依次合并起來，即可得到完整的有序數組。

舉例說明

假設我們有以下待排序的數組：[49, 38, 65, 97, 76, 27, 13, 49]

1、選擇基準： 選擇數組的第一個元素 49 作為基準。

2、分割： 將數組分割成兩部分，小于 49 的部分為 [38, 27, 13]，大于 49 的部分為 [65, 97, 76, 49]。

3、遞歸排序： 對小于基準的部分 [38, 27, 13] 進行遞歸排序。
????????????選擇基準： 在小于部分中，選擇第一個元素 38 作為基準。
????????????分割： 分割后，小于 38 的部分為 [27, 13]，大于 38 的部分為空。
????????????遞歸排序： 對小于 38 的部分 [27, 13] 進行排序，得到 [13, 27]。

4、遞歸排序： 對大于基準的部分 [65, 97, 76, 49] 進行遞歸排序。
????????????選擇基準： 在大于部分中，選擇第一個元素 65 作為基準。
????????????分割： 分割后，小于 65 的部分為 [49]，大于 65 的部分為 [97, 76]。
????????????遞歸排序： 對小于 65 的部分 [49] 進行排序，得到 [49]。
????????????遞歸排序： 對大于 65 的部分 [97, 76] 進行排序，得到 [76, 97]。

5、合并： 將小于基準的部分 [13, 27]、基準 38、大于基準的部分 [49] 合并，得到 [13, 27, 38, 49]。

6、合并： 將小于基準的部分 [13, 27, 38, 49]、基準 49、大于基準的部分 [65, 97, 76] 合并，得到 [13, 27, 38, 49, 65, 97, 76]。

最終，數組 [49, 38, 65, 97, 76, 27, 13, 49] 經過快速排序變為有序數組 [13, 27, 38, 49, 65, 76, 97, 49]。

示例代碼

#include <stdio.h>// 快速排序算法
void QuickSort(int A[], int low, int high);// 劃分函數：將數組劃分為兩個子數組
int Partition(int A[], int low, int high);// 交換數組中的兩個元素
void Swap(int A[],int a,int b);// 打印數組元素
void PrintfArray(int A[], int length);int main()
{int arr[] = {49, 38, 65, 97, 76, 27, 13, 49};int length = sizeof(arr) / sizeof(arr[0]);int i;QuickSort(arr, 0, length - 1);printf("排序后的數組：");PrintfArray(arr,length);return 0;
} 劃分函數的實現
//int Partition(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 pivotpos = Partition(A, low, high);  // 劃分數組
//		QuickSort(A, low, pivotpos - 1);  // 對樞軸左側子數組進行快速排序
//		QuickSort(A, pivotpos + 1, high);  // 對樞軸右側子數組進行快速排序
//	}
//}// 劃分函數的實現
// 參數:
//   A: 數組
//   start: 子數組的起始索引
//   end: 子數組的結束索引
// 返回值:
//   劃分后樞軸的索引位置// 規則：如果當前元素小于基準數時，首先分割指示器右移一位；
// 在A的基礎之上，如果當前元素下標大于分割指示器下標時，當前元素和分割指示器所指元素交換 
int Partition(int A[], int start, int end)
{if(start==end)return start;int pivot=start; // 選擇第一個元素作為樞軸int zoneIndex=start-1; // 將小于樞軸的元素放在左側區域Swap(A,pivot,end); // 將樞軸元素放到最右側int i;for(i=start; i<=end; i++) // 將小于等于樞軸的元素移到左側區域{if(A[i]<=A[end]){zoneIndex++;if(i>zoneIndex)Swap(A,i,zoneIndex);}}return zoneIndex;  // 返回樞軸的最終位置
}// 快速排序算法的實現
// 參數:
//   A: 數組
//   start: 子數組的起始索引
//   end: 子數組的結束索引
void QuickSort(int A[], int start, int end)
{int zoneIndex=Partition(A,start,end);  // 劃分數組if(zoneIndex>start)QuickSort(A,start,zoneIndex-1); // 對樞軸左側子數組進行快速排序if(zoneIndex<end)QuickSort(A,zoneIndex+1,end);  // 對樞軸右側子數組進行快速排序
}// 交換數組中的兩個元素
// 參數:
//   A: 數組
//   a, b: 需要交換的元素索引
void Swap(int A[],int a,int b)
{int temp;temp=A[a];A[a]=A[b];A[b]=temp;
}// 打印數組元素
// 參數:
//   A: 數組
//   length: 數組長度
void PrintfArray(int A[],int length)
{int i=0;for(i=0; i<length; i++){printf("%d ",A[i]);}printf("\n");
}