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) 算法更快，因為它的內(nèi)部循環(huán)（inner loop）可以在大部分的架構(gòu)上很有效率地被實現(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ù)時，排序結(jié)束。
圖解-->
代碼講解：<運用遞歸>
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ù)結(jié)束。
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語言快速排序算法內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！
相關文章
單鏈表是一種鏈式存取的數(shù)據(jù)結(jié)構(gòu)，用一組地址任意的存儲單元存放線性表中的數(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)類型轉(zhuǎn)換的關鍵工具,允許在復雜繼承結(jié)構(gòu)中安全地將基類指針或引用轉(zhuǎn)換為派生類指針或引用,這篇文章主要介紹了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
C語言輾轉(zhuǎn)相除法求2個數(shù)的最小公約數(shù)
輾轉(zhuǎn)相除法最大的用途就是用來求兩個數(shù)的最大公約數(shù)。下面通過本文給大家介紹C語言輾轉(zhuǎn)相除法求2個數(shù)的最小公約數(shù)，非常不錯，感興趣的朋友一起看看吧2016-12-12