C語言簡明講解快速排序的應用
快速排序
快速排序,說白瞭就是給基準數據找其正確索引位置的過程
1.1快速排序引入
希爾排序相當於直接插入排序的升級，他們屬於插入排序類；堆排序相當於簡單選擇排序的升級，他們同屬於選擇排序類；而對於交換排序類的冒泡排序升級版本就是快速排序。
1.2快速排序的基本思想
通過一趟排序將待排記錄分割成獨立的兩部分，其中一部分記錄的關鍵字比另一部分記錄的關鍵字小，則可分別對這兩部分記錄繼續進行排序，以達到整個排序的目的。
1.3快速排序的排序流程
- 首先設定一個分界值，通過該分界值將數組分成左右兩部分。
- 將大於或等於分界值的數據集中到數組右邊，小於分界值的數據集中到數組的左邊。此時，左邊部分中各元素都小於或等於分界值，而右邊部分中各元素都大於或等於分界值。
- 然後，左邊和右邊的數據可以獨立排序。對於左側的數組數據，又可以取一個分界值，將該部分數據分成左右兩部分，同樣在左邊放置較小值，右邊放置較大值。右側的數組數據也可以做類似處理。
- 重復上述過程，可以看出，這是一個遞歸定義。通過遞歸將左側部分排好序後，再遞歸排好右側部分的順序。當左、右兩個部分各數據排序完成後，整個數組的排序也就完成瞭。
總結來說：就是分治+填數
1.4實例說明
以12、10、8、22、5、13、28、21、11我們要將它按從小到大排序排序過程：
詳細過程：
設定兩個指針 left 和 right，它們初始分別指向待排序序列的左端和右端；此外還要附設一個基準元素 tmp（一般選取第一個，本例中基準tmp的值為 20）。
首先從 right 所指的位置從右向左搜索找到第一個小於 tmp 的元素，然後將其記錄在基準元素所在的位置。
接著從 left 所指的位置從左向右搜索找到第一個大於 tmp的元素，然後將其記錄在 right 所指向的位置。
然後再從 right 所指向的位置繼續從右向左搜索找到第一個小於 tmp 的元素，然後將其記錄在 left 所指向的位置。
接著，left 繼續從左向右搜索第一個大於 tmp的元素，如果在搜索過程中出現瞭 left == right ，則說明一趟快速排序結束。此時將 tmp 記錄在 left 和 right 共同指向的位置即可。
以上便是一輪快速排序的詳細過程
註意：
- 向下劃分至少需要這個組兩個數據，才有必要劃分，0個或者1個都沒有必要
- 劃分時：從右向左找比基準小的（相等）
- 從左向右找比基準值大的
1.5代碼實現
//一次劃分函數 核心函數 //返回基準值最終所在下標
int Partition(int *arr, int left, int right)
{
//先講arr數組裡的[left， right]的第一個值 作為基準值
int tmp = arr[left];
while(left < right)
{
while(left<right && arr[right] > tmp)//左右邊界沒有相遇且當前右邊的值大於基準值tmp
right--;
if(left < right)//如果此時，左右邊界沒有相遇，那就隻能證明右邊right找到瞭一個小於等於基準值tmp的值
{
arr[left] = arr[right];
}
else
{
break;
}
while(left<right && arr[left] <= tmp)//左右邊界沒有相遇且當前左邊的值小於等於基準值tmp
left++;
if(left < right)//如果此時，左右邊界沒有相遇，那就隻能證明左邊left找到瞭一個大於基準值tmp的值
{
arr[right] = arr[left];
}
else
{
break;
}
}
arr[left] = tmp;//此時 因為 left == right
return left;//return right ok
}
void Quick(int *arr, int left, int right)
{
if(left < right)//通過left <right 保證[left, right]這個范圍內至少兩個數據
{
int par = Partition(arr, left, right);
if(left < par-1)//基準值左半部分 至少有兩個值才有必要去遞歸
{
Quick(arr, left, par-1);
}
if(par+1 < right)//基準值右半部分 至少有兩個值才有必要去遞歸
{
Quick(arr, par+1, right);
}
}
}
void QuickSort(int *arr, int len)
{
Quick(arr, 0, len-1);
}
1.6性能分析
越亂越快，越有序越慢
時間復雜度：
最優情況：O（nlogn）每次數據元素都能平均的分成兩個部分。得到一個完全二叉樹；
最壞情況： O（n^2）這個數僅有右子樹或左子樹，比較次數為 （n-1）+（n-2) + (n-3) + … +1=n*(n-1)/2 ；
平均情況：O（nlogn）。
空間復雜度：O（1）。
穩定性：因為關鍵字的比較和交換是跳躍進行的，會改變數據元素的相對位置；因此，快速排序是一種不穩定的排序方法，但是也是內排序中平均效率最高的排序算法。
（小白一位，如有錯誤歡迎指正）
到此這篇關於C語言簡明講解快速排序的應用的文章就介紹到這瞭,更多相關C語言快速排序內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet！