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;//交換標量到它應(yīng)該到的位置上，重新選取標量
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ù)因子很小，比復(fù)雜度穩(wěn)定等于 O(nlogn) 的歸并排序要小很多。所以，對絕大多數(shù)順序性較弱的隨機數(shù)列而言，快速排序總是優(yōu)于歸并排序。
快速排序使用分治法（Divide and conquer）策略來把一個串行（list）分為兩個子串行（sub-lists）
簡單的說，選取一個基準（這里選取第一個數(shù)據(jù)），與其他數(shù)據(jù)進行比較，使比它小的在它的前面，比它大的在它的后面。然后再以這個基準為界限分為兩部地方（比它大的部分、比它小的部分），分別選取兩個部分的基準，再進行比較，比較完后在進行分界，重復(fù)下去，直到最后每部分都只有一個數(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ù)找，重復(fù)以上步驟。
4.4、直到first>=last時，都停止尋找，并交換此時first下標的數(shù)據(jù)與key的值
4.5、分治思想，以此時的key下標的數(shù)組作為分界，分為比它大的、比它小的兩部分，在重復(fù)以上步驟，直至只有一個數(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;//交換標量到它應(yīng)該到的位置上，重新選取標量
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;
}到此這篇關(guān)于C語言之快速排序算法（遞歸Hoare版）介紹的文章就介紹到這了,更多相關(guān)C語言快速排序算法內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
本篇文章將會介紹下位機通過心跳包和上位機之間進行數(shù)據(jù)交互和遠程功能控制的實現(xiàn)方法。文中的示例代碼講解詳細，感興趣的可以了解一下2022-11-11
相信大家在小時候都用紙和筆與小伙伴們玩過一個經(jīng)典的游戲之井字棋,即三子棋,下面這篇文章主要給大家介紹了關(guān)于C語言新手初階教程之三子棋實現(xiàn)的相關(guān)資料,需要的朋友可以參考下2022-01-01
位域是C語言中的一種高級功能，允許程序員為結(jié)構(gòu)體的成員分配特定數(shù)量的位，本文主要為大家介紹了位域的使用以及優(yōu)缺點，希望對大家有所幫助2023-07-07
c++11 符號修飾與函數(shù)簽名、函數(shù)指針、匿名函數(shù)、仿函數(shù)、std::function與std::bind
這篇文章主要介紹了c++11 符號修飾與函數(shù)簽名、函數(shù)指針、匿名函數(shù)、仿函數(shù)、std::function與std::bind,本文通過實例代碼給大家介紹的非常詳細，對大家的學(xué)習(xí)或工作具有一定的參考借鑒價值，需要的朋友可以參考下2020-05-05
這篇文章主要為大家詳細介紹了如何利用Qt實現(xiàn)仿QQ設(shè)置面板功能，文中的示例代碼講解詳細，具有一定的借鑒價值，感興趣的小伙伴可以了解一下2022-12-12
這篇文章主要介紹了C++中auto_ptr智能指針的用法詳解的相關(guān)資料,需要的朋友可以參考下2016-07-07
C++/Php/Python/Shell 程序按行讀取文件或者控制臺的實現(xiàn)
下面小編就為大家?guī)硪黄狢++/Php/Python/Shell 程序按行讀取文件或者控制臺的實現(xiàn)。小編覺得挺不錯的，現(xiàn)在就分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2017-03-03
堆經(jīng)常會出現(xiàn)兩種類型的問題：1.釋放或改寫仍在使用的內(nèi)存(稱為：“內(nèi)存損壞”)。2.未釋放不再使用的內(nèi)存(稱為：“內(nèi)存泄露”)。這是最難被調(diào)試發(fā)現(xiàn)的問題之一2013-09-09
線段樹在一些acm題目中經(jīng)常見到,這種數(shù)據(jù)結(jié)構(gòu)主要應(yīng)用在計算幾何和地理信息系統(tǒng)中,這篇文章主要給大家介紹了關(guān)于線段樹以及C++實現(xiàn)的相關(guān)資料,需要的朋友可以參考下2021-07-07
詳解C++的靜態(tài)內(nèi)存分配與動態(tài)內(nèi)存分配
內(nèi)存分配 (Memory Allocation) 是指為計算機程序或服務(wù)分配物理內(nèi)存空間或虛擬內(nèi)存空間的一個過程，本文主要介紹了C++的靜態(tài)內(nèi)存分配與動態(tài)內(nèi)存分配，感興趣的同學(xué)可以參考閱讀2023-06-06