一、排序概念

排序是數據結構中的一個重要概念，它是指將一組數據元素按照特定的順序進行排列的過程，默認是從小到大排序。

常見的八大排序算法：

插入排序、希爾排序、冒泡排序、快速排序、選擇排序、堆排序、歸并排序、基數排序

二、快速排序（重點常考）

1.算法思想：

通過一趟排序將待排記錄分割成獨立的兩部分，其中一部分記錄的關鍵字均比另一部分記錄的關鍵字小，然后分別對這兩部分記錄繼續進行排序，以達到整個序列有序的目的。

2.算法步驟：

1.選擇一個基準值（通常選擇序列的第一個元素或最后一個元素）。
2.從序列的兩端開始，設置兩個指針，一個指向序列的起始位置（left），一個指向序列的結束位置（right）。
3.從 right 指針開始，向左移動 right 指針，找到第一個小于基準值的元素，（從后往前找，找比基準小的數字，往前挪），然后從 left 指針開始，向右移動 left 指針，找到第一個大于基準值的元素（從前往后找，找比基準大的數字，往后挪）。
4.交換 left 和 right 指針所指向的元素。
5.重復步驟 3 和 4，直到 left 和 right 指針相遇。此時，將基準值與 left 指針所指向的元素交換位置，這樣基準值就處于正確的排序位置上，并且其左邊的元素都小于它，右邊的元素都大于它。（完成快速排序的一次劃分）
6.對基準值左邊和右邊的子序列分別重復步驟 1 到 5，直到子序列的長度為 1 或 0，此時整個序列就已經有序。

3.代碼實現：

//代碼實現
#include<stdio.h>
int Partition(int* arr, int left, int right)//一次劃分
{int tmp = arr[left];//基準while (left < right){//從后往前找比基準小的數字，往前移動while (left<right&&arr[right] > tmp){right--;}if (left < right)//判斷循環出口條件{arr[left] = arr[right];}//從前往后找比基準大的數字，往后移動while (left < right && arr[left] <= tmp){left++;}if (left < right){arr[right] = arr[left];}}arr[left] = tmp;return left;
}
void Quick(int* arr, int left, int right)//遞歸調用一次劃分
{int par = Partition(arr, left, right);if(left<par-1)//左邊序列長大于1{Quick(arr, left, par - 1);}if (par + 1 < right)//右邊序列長大于1{Quick(arr, par+1, right);}
}
void QuickSort(int* arr, int len)//快速排序
{Quick(arr, 0, len - 1);
}
void Show(int *arr, int size) 
{for (int i = 0; i < size; i++)printf("%d ", arr[i]);printf("\n");
}

4.復雜度分析

5.快速排序特點

優點：平均時間復雜度；不需要額外的存儲空間，高效使用內存。

缺點：不穩定，空間復雜度大 ；越有序越慢，完全有序時間復雜度為O(n^2)。

以上是排序算法第一部分關于快速排序的知識，如果有幫助可以點贊收藏一下，會持續更新輸出有用的內容，感興趣可以關注我！