C語言之快速排序算法(遞歸Hoare版)介紹
廢話不多說，先看代碼
#define _CRT_SECURE_NO_WARNINGS 1
//快速排序算法，遞歸求解
#include <stdio.h>
void swap(int* a, int* b)
{
int c = 0;
c = *a;
*a = *b;
*b = c;
}
void Compare(int arr[], int one, int end)
{
int first = one;//最左邊數(shù)組下標
int last = end;//最右邊數(shù)組下標
int key = first;//用于比較的標量（選取最左邊第一個元素）
if (first >= last)
{
return;
}
while (first < last)
{
while (first < last && arr[last] >= arr[key])//右邊找比標量小的數(shù)
{
last--;
}
while (first < last && arr[first] <= arr[key])//左邊找比標量大的數(shù)
{
first++;
}
if(first < last)//分析交換找出來的值
swap(&arr[first], &arr[last]);
}
if (first == last)
{
int mite = key;//交換標量到它應該到的位置上，重新選取標量
swap(&arr[mite], &arr[last]);
}
Compare(arr,one,first-1);//左邊遞歸排序
Compare(arr,first+1,end);//右邊遞歸排序
}
int main()
{
int arr[] = { 5,4,6,5,2,1};
int i = 0;
int len = sizeof(arr) / 4;
Compare(arr,i,len-1);//傳第一個和最后一個元素的下標
for (i = 0; i < len; i++)
{
printf("%d ", arr[i]);
}
return 0;
}首先什么是快速排序算法：快速排序是由東尼·霍爾所發(fā)展的一種排序算法。在平均狀況下，排序n 個項目要Ο(nlogn) 次比較。在最壞狀況下則需要Ο(n2) 次比較，但這種狀況并不常見。事實上，快速排序通常明顯比其他 Ο(nlogn) 算法更快，因為它的內部循環(huán)（inner loop）可以在大部分的架構上很有效率地被實現(xiàn)出來。
快速排序的最壞運行情況是 O(n²)，比如說順序數(shù)列的快排。但它的平攤期望時間是 O(nlogn)，且 O(nlogn) 記號中隱含的常數(shù)因子很小，比復雜度穩(wěn)定等于 O(nlogn) 的歸并排序要小很多。所以，對絕大多數(shù)順序性較弱的隨機數(shù)列而言，快速排序總是優(yōu)于歸并排序。
快速排序使用分治法（Divide and conquer）策略來把一個串行（list）分為兩個子串行（sub-lists）
簡單的說，選取一個基準（這里選取第一個數(shù)據(jù)），與其他數(shù)據(jù)進行比較，使比它小的在它的前面，比它大的在它的后面。然后再以這個基準為界限分為兩部地方（比它大的部分、比它小的部分），分別選取兩個部分的基準，再進行比較，比較完后在進行分界，重復下去，直到最后每部分都只有一個數(shù)據(jù)時，排序結束。
圖解-->
代碼講解：<運用遞歸>
1、首先需要創(chuàng)建數(shù)組、數(shù)組第一個數(shù)據(jù)下標，最后一個數(shù)據(jù)下標三個參數(shù)，數(shù)組用于儲存數(shù)據(jù)，然后創(chuàng)建一個Compare()用于快速排序函數(shù)，最后打印出來就是我們需要的有序數(shù)列。
int main()
{
int arr[] = { 5,4,6,5,2,1};
int i = 0;
int len = sizeof(arr) / 4;
Compare(arr,i,len-1);//傳第一個和最后一個元素的下標
for (i = 0; i < len; i++)
{
printf("%d ", arr[i]);
}
return 0;2、Compare()函數(shù)創(chuàng)建
這里使用無符號返回類型，因為不需要返回值
為保證數(shù)組第一個元素和最后一個元素下標不變，創(chuàng)建first和last兩個局部變量記錄數(shù)組第一個元素和最后一個元素的下標
創(chuàng)建key下標的數(shù)據(jù)作為基準
void Compare(int arr[], int one, int end)
{
int first = one;//最左邊數(shù)組下標
int last = end;//最右邊數(shù)組下標
int key = first;//用于比較的標量（選取最左邊第一個元素）3、首先判斷數(shù)列是否只有一個元素，如果只有一個元素，則函數(shù)結束。
4、開始實現(xiàn)函數(shù)主要比較部分
4.1、如果選取左邊第一個數(shù)據(jù)為基準，先從右邊開始比較，
4.2、從右邊第一個數(shù)據(jù)開始與key進行比較，如果比它大則繼續(xù)向右比較(last--)，直到找到比key小的數(shù)據(jù)，便停下來。
4.3、此刻開始從左邊開始與key比較，如果比key小則繼續(xù)比較(first++)，如果比key大則與右邊找到的比key大的數(shù)進行交換。然后右邊繼續(xù)找，重復以上步驟。
4.4、直到first>=last時，都停止尋找，并交換此時first下標的數(shù)據(jù)與key的值
4.5、分治思想，以此時的key下標的數(shù)組作為分界，分為比它大的、比它小的兩部分，在重復以上步驟，直至只有一個數(shù)據(jù)為止，停下排序。采用遞歸求解。
void Compare(int arr[], int one, int end)
{
int first = one;//最左邊數(shù)組下標
int last = end;//最右邊數(shù)組下標
int key = first;//用于比較的標量（選取最左邊第一個元素）
if (first >= last)
{
return;
}
while (first < last)
{
while (first < last && arr[last] >= arr[key])//右邊找比標量小的數(shù)
{
last--;
}
while (first < last && arr[first] <= arr[key])//左邊找比標量大的數(shù)
{
first++;
}
if(first < last)//分析交換找出來的值
swap(&arr[first], &arr[last]);
}
if (first == last)
{
int mite = key;//交換標量到它應該到的位置上，重新選取標量
swap(&arr[mite], &arr[last]);
}
Compare(arr,one,first-1);//左邊遞歸排序
Compare(arr,first+1,end);//右邊遞歸排序
}swap()交換函數(shù)，因為需要影響到交換函數(shù)外的值，使用指針形參。
void swap(int* a, int* b)
{
int c = 0;
c = *a;
*a = *b;
*b = c;
}到此這篇關于C語言之快速排序算法（遞歸Hoare版）介紹的文章就介紹到這了,更多相關C語言快速排序算法內容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！
相關文章
單鏈表是一種鏈式存取的數(shù)據(jù)結構，用一組地址任意的存儲單元存放線性表中的數(shù)據(jù)元素。本文將為大家介紹C語言中單鏈表的基本操作，需要的可以參考一下2022-10-10
這篇文章主要為大家詳細介紹了C++控制臺實現(xiàn)俄羅斯方塊游戲，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2018-06-06
這篇文章介紹了C++中Boost的智能指針shared_ptr，文中通過示例代碼介紹的非常詳細。對大家的學習或工作具有一定的參考借鑒價值，需要的朋友可以參考下2022-07-07
這篇文章主要為大家介紹了C語言編程PAT乙級學習筆記實現(xiàn)示例，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進步，早日升職加薪2022-05-05
在C++編程中,dynamic_cast 是處理多態(tài)類型轉換的關鍵工具,允許在復雜繼承結構中安全地將基類指針或引用轉換為派生類指針或引用,這篇文章主要介紹了C++的dynamic,需要的朋友可以參考下2024-08-08
這篇文章主要給大家介紹了關于c語言中scanf的基本用法，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2021-01-01
這篇文章主要為大家詳細介紹了如何利用C語言實現(xiàn)繪制可愛的橘子鐘表，文中的示例代碼講解詳細，具有一定的學習價值，感興趣的可以了解一下2022-12-12
這篇文章主要介紹了C/C++多態(tài)的實現(xiàn)機制理解的相關資料,非常不錯，具有參考借鑒價值，需要的朋友可以參考下，希望能給你帶來幫助2021-08-08
C語言中求字符串長度的函數(shù)的幾種實現(xiàn)方法
這篇文章主要介紹了C語言中求字符串長度的函數(shù)的幾種實現(xiàn)方法,需要的朋友可以參考下2018-08-08
輾轉相除法最大的用途就是用來求兩個數(shù)的最大公約數(shù)。下面通過本文給大家介紹C語言輾轉相除法求2個數(shù)的最小公約數(shù)，非常不錯，感興趣的朋友一起看看吧2016-12-12