C語言實現(xiàn)快速排序
快速排序是霍爾大佬在1962年提出的排序方法，因其出色的排序效率使得它成為使用最廣泛的排序算法?？焖倥判蛑愿医凶隹焖倥判颍匀皇怯幸欢ǖ牡览?，今天我們就來看看快速排序是如何凌駕于其它算法之上的。
快速排序的基本思想是：任取待排序數(shù)列中的一個數(shù)作為 key 值，通過某種方法使得 key 的左邊所有的數(shù)都比它小，右邊的數(shù)都比它大；以 key 為中心，將 key 左邊的數(shù)列與右邊的數(shù)列取出，做同樣的操作（取 key 值，分割左右區(qū)間），直至所有的數(shù)都到了正確的位置。
上述所提到的某種方法可以有很多種，例如：hoare法、挖坑法、前后指針法。它們雖然做法不相同，但做的都是同一件事——分割出 key 的左右區(qū)間（左邊的數(shù)比 key 小，右邊的數(shù)比 key 大）。
我們首先來看看霍爾大佬所用的方法——hoare法。
1. hoare法
方法與步驟
以數(shù)列 6，1，2，7，9，3，4，5，8，10 為例：
1.取最左邊為 key ，分別有 left 和 right 指向數(shù)列的最左端與最右端；
2. right 先走，找到比 key 小的數(shù)就停下來；
3. left 開始走，找到比 key 大的數(shù)就停下來；
4. 交換 left 與 right 所在位置的數(shù)；
5.重復上述操作，right 找小，left 找大，進行交換；
6. right 繼續(xù)找?。?/p>
7. left 繼續(xù)找大，若與 right 就停下來；
8.交換二者相遇位置與 key 處的值；
此時一趟排序就完成了，此時的數(shù)列有兩個特點：
1. key 所指向的值（6）已經(jīng)到了正確的位置；
2. key 左邊的數(shù)字都比 key 要小，右邊的都比 key 要大；
接下來就是遞歸的過程了，分別對左右區(qū)間進行同樣的操作：
代碼實現(xiàn)
知道了詳解步驟，用代碼來實現(xiàn)并不困難，但是有很多很多的細節(jié)需要注意。（這里的代碼未經(jīng)優(yōu)化，當前的代碼有幾種極端的情況不能適應）
void Swap(int* p, int* q)
{
int tmp = *p;
*p = *q;
*q = tmp;
}
void QuickSort(int* a, int begin, int end)
{
//數(shù)列只有一個數(shù)，或無數(shù)列則返回
if (begin >= end)
{
return;
}
int left = begin;
int right = end;
int keyi = left;
while (left < right)
{
//右邊先走
while (left < right && a[right] >= a[keyi])
{
right--;
}
while (left < right && a[left] <= a[keyi])
{
left++;
}
Swap(&a[left], &a[right]);
}
Swap(&a[keyi], &a[left]);
QuickSort(a, begin, left - 1);
QuickSort(a, left + 1, end);
}2. 挖坑法
挖坑法相比于hoare法，思路上更為簡單易懂。
方法與步驟
還是以同樣的數(shù)列 6，1，2，7，9，3，4，5，8，10 為例：
1. 先將第一個數(shù)存放到 key 中，形成一個坑位：分別有 left 和 right 指向數(shù)列的最左端與最右端；
2. right 先走，找到比 key 小的數(shù)，將該數(shù)丟到坑里；同時又形成了一個新的坑；
3. left 開始走，找到比 key 大的數(shù)，將該數(shù)丟到坑里；同時形成一個新的坑；
4. right繼續(xù)找小，進行重復的操作；
5. left 找大；
6. right 找小；
7. left 找大；
8.若二者相遇就停下來；將 key 值放入坑；
至此，一趟排序已經(jīng)完成，我們發(fā)現(xiàn)此時的數(shù)列與hoare具有相同的特點：
1. key 所指向的值（6）已經(jīng)到了正確的位置；
2. key 左邊的數(shù)字都比 key 要小，右邊的都比 key 要大；
挖坑法、hoare、前后指針法完成一趟排序后都具有相同的特點，所以不同版本的快速排序不一樣的只有單趟排序的實現(xiàn)，總體思路都是相同的。
代碼實現(xiàn)
void QuickSort(int* a, int begin, int end)
{
if (begin >= end)
{
return;
}
int left = begin;
int right = end;
int key = a[left];
int hole = left;//坑位
while (left < right)
{
while (left < right && a[right] >= key)
{
right--;
}
a[hole] = a[right];
hole = right;
while (left < right && a[left] <= key)
{
left++;
}
a[hole] = a[left];
hole = left;
}
a[hole] = key;
QuickSort(a, begin, hole - 1);
QuickSort(a, hole + 1, end);
}3. 前后指針法
方法與步驟
以同樣的數(shù)列為例：
1. 取第一個值為 key ；有 prev 和 cur 分別指向數(shù)列開頭和 prev 的下一個數(shù)；
2. cur 先走，找到比 key 小的數(shù)就停下來；
3. ++prev ，交換 prev 與 cur 位置的數(shù)；（前兩次無需交換，因為自己與自己換沒有意義）
4. 重復此步驟；
5. 直到 cur 走完整個數(shù)列，交換 prev 與 key 處的值；
至此，第一趟排序就結(jié)束了，又是與前兩種方法相同的結(jié)果；
代碼實現(xiàn)
void QuickSort(int* a, int begin, int end)
{
if (begin >= end)
{
return;
}
int prev = begin;
int cur = prev + 1;
int keyi = begin;
while (cur <= end)
{
if (a[cur] < a[keyi] && ++prev != cur)
{
Swap(&a[prev], &a[cur]);
}
cur++;
}
Swap(&a[keyi], &a[prev]);
keyi = prev;
QuickSort(a, begin, keyi - 1);
QuickSort(a, keyi + 1, end);
}4. 快速排序的缺點與優(yōu)化
1.快速排序的缺點
我們用三種方式實現(xiàn)了快速排序，其實這三種方式并無明顯的優(yōu)劣之分。但是我們前面設(shè)計的快速排序其實是有兩個缺點的：
1.在最壞情況下它的的效率極慢；
2.在數(shù)據(jù)量太大時會造成棧溢出。
那么什么情況是最壞情況呢？答案是，當數(shù)據(jù)本身就是有序的時候（無論是逆序還是順序）。在最壞情況下，每次我們的 key 值都是最大或者最小，這樣就會使 key 與數(shù)列的每個數(shù)都比較一次，它的時間復雜度為 O(n^2);
為什么會發(fā)生棧溢出呢？因為我們的快速排序是利用遞歸實現(xiàn)的，有遞歸調(diào)用，就要建立函數(shù)棧幀，并且隨著遞歸的深度越深所要建立的函數(shù)棧幀的消耗就越大 。如這幅圖所示：
2.快速排序的優(yōu)化
① 三數(shù)取中法選 key
為了應對最壞情況會出現(xiàn)時間復雜度為 O(N^2) 的情況，有人提出了三數(shù)取中的方法。
舊方法中，我們每次選 key 都是數(shù)列的第一個元素。三數(shù)取中的做法是，分別取數(shù)列的第一個元素、最后一個元素和最中間的元素，選出三個數(shù)中不是最大也不是最小的那個數(shù)當作 key 值。
有了三數(shù)取中，之前的最壞情況立馬變成了最好情況。
代碼實現(xiàn)
由于hoare法、挖坑法、前后指針法最終的效果都相同且效率差異很小，所以就任意選取一個為例，其余兩者都類似。
//三數(shù)取中的函數(shù)
int GetMidIndex(int* a, int begin, int end)
{
int mid = (begin + end) / 2;
if (a[begin] < a[mid])
{
if (a[mid] < a[end])
{
return mid;
}
else if (a[begin] > a[end])
{
return begin;
}
else
{
return end;
}
}
else // a[begin] > a[mid]
{
if (a[mid] > a[end])
{
return mid;
}
else if (a[begin] < a[end])
{
return begin;
}
else
{
return end;
}
}
}
//hoare法
void QuickSort(int* a, int begin, int end)
{
if (begin >= end)
{
return;
}
int mid = GetMidIndex(a, begin, end);
Swap(&a[mid], &a[begin]);
int left = begin;
int right = end;
int keyi = left;
while (left < right)
{
while (left < right && a[right] >= a[keyi])
{
right--;
}
while (left < right && a[left] <= a[keyi])
{
left++;
}
Swap(&a[left], &a[right]);
}
Swap(&a[keyi], &a[left]);
QuickSort(a, begin, left - 1);
QuickSort(a, left + 1, end);
}② 小區(qū)間優(yōu)化
隨著遞歸的調(diào)用越深入，此時有個很大的缺點就是函數(shù)棧幀的消耗很大。但是同時又有一個好處，就是越往下，數(shù)列就越接近有序，且此時每個小區(qū)間的數(shù)據(jù)個數(shù)特別少。
那么有什么辦法可以取其長處避其短處呢？不知道你是否還記得插入排序的特點——數(shù)據(jù)越接近有序，效率就越高。并且，在數(shù)據(jù)量極少的情況下，時間復雜度為 O(N^2) 的插入排序與時間復雜度為 O(N*log N) 的快速排序基本沒有什么區(qū)別。所以，我們干脆就在排序數(shù)據(jù)量少的數(shù)列時，采用插入排序代替。
代碼實現(xiàn)
//三數(shù)取中的函數(shù)
int GetMidIndex(int* a, int begin, int end)
{
int mid = (begin + end) / 2;
if (a[begin] < a[mid])
{
if (a[mid] < a[end])
{
return mid;
}
else if (a[begin] > a[end])
{
return begin;
}
else
{
return end;
}
}
else // a[begin] > a[mid]
{
if (a[mid] > a[end])
{
return mid;
}
else if (a[begin] < a[end])
{
return begin;
}
else
{
return end;
}
}
}
//插入排序
void InsertSort(int* a, int n)
{
for (int i = 0; i < n - 1; i++)
{
int end = i;
int tmp = a[end + 1];
while (end >= 0)
{
if (a[end] > tmp) //大于tmp，往后挪一個
{
a[end + 1] = a[end];
end--;
}
else
{
break;
}
}
a[end + 1] = tmp; //把tmp插入空隙
}
}
//hoare法
void QuickSort(int* a, int begin, int end)
{
if (begin >= end)
{
return;
}
if ((end - begin + 1) < 15)
{
// 小區(qū)間用直接插入替代，減少遞歸調(diào)用次數(shù)
InsertSort(a+begin, end - begin + 1);
}
else
{
int mid = GetMidIndex(a, begin, end);
Swap(&a[mid], &a[begin]);
int left = begin;
int right = end;
int keyi = left;
while (left < right)
{
while (left < right && a[right] >= a[keyi])
{
right--;
}
while (left < right && a[left] <= a[keyi])
{
left++;
}
Swap(&a[left], &a[right]);
}
Swap(&a[keyi], &a[left]);
QuickSort(a, begin, left - 1);
QuickSort(a, left + 1, end);
}
}兩外兩種方法的代碼實現(xiàn)已打包完成，可在文末直接取用。
5. 快速排序的非遞歸實現(xiàn)
快速排序的非遞歸思路與遞歸相差無幾，唯一不同的是，非遞歸用?；蜿犃心M函數(shù)遞歸建立棧幀的過程。
void QuickSortNonR(int* a, int begin, int end)
{
Stack st;
StackInit(&st);
StackPush(&st, begin);
StackPush(&st, end);
while (!StackEmpty(&st))
{
int right = StackTop(&st);
StackPop(&st);
int left = StackTop(&st);
StackPop(&st);
int keyi = PartSort1(a, left, right);//三種方法任選其一
//int keyi = PartSort2(a, left, right);
//int keyi = PartSort3(a, left, right);
if (keyi + 1 < right)
{
StackPush(&st, keyi + 1);
StackPush(&st, right);
}
if (left < keyi - 1)
{
StackPush(&st, left);
StackPush(&st, keyi - 1);
}
}
StackDestroy(&st);
}附錄﹡完整源碼
快速排序遞歸實現(xiàn)
//交換函數(shù)
void Swap(int* p, int* q)
{
int tmp = *p;
*p = *q;
*q = tmp;
}
//三數(shù)取中
int GetMidIndex(int* a, int begin, int end)
{
int mid = (begin + end) / 2;
if (a[begin] < a[mid])
{
if (a[mid] < a[end])
{
return mid;
}
else if (a[begin] > a[end])
{
return begin;
}
else
{
return end;
}
}
else // a[begin] > a[mid]
{
if (a[mid] > a[end])
{
return mid;
}
else if (a[begin] < a[end])
{
return begin;
}
else
{
return end;
}
}
}
//插入排序
void InsertSort(int* a, int n)
{
for (int i = 0; i < n - 1; i++)
{
int end = i;
int tmp = a[end + 1];
while (end >= 0)
{
if (a[end] > tmp) //大于tmp，往后挪一個
{
a[end + 1] = a[end];
end--;
}
else
{
break;
}
}
a[end + 1] = tmp; //把tmp插入空隙
}
}
// Hoare法
int PartSort1(int* a, int begin, int end)
{
int mid = GetMidIndex(a, begin, end);
Swap(&a[begin], &a[mid]);
int left = begin, right = end;
int keyi = left;
while (left < right)
{
while (left < right && a[right] >= a[keyi])
{
--right;
}
while (left < right && a[left] <= a[keyi])
{
++left;
}
Swap(&a[left], &a[right]);
}
Swap(&a[left], &a[keyi]);
keyi = left;
return keyi;
}
// 挖坑法
int PartSort2(int* a, int begin, int end)
{
int mid = GetMidIndex(a, begin, end);
Swap(&a[begin], &a[mid]);
int left = begin, right = end;
int key = a[left];
int hole = left;
while (left < right)
{
while (left < right && a[right] >= key)
{
--right;
}
a[hole] = a[right];
hole = right;
while (left < right && a[left] <= key)
{
++left;
}
a[hole] = a[left];
hole = left;
}
a[hole] = key;
return hole;
}
//前后指針法
int PartSort3(int* a, int begin, int end)
{
int mid = GetMidIndex(a, begin, end);
Swap(&a[begin], &a[mid]);
int keyi = begin;
int prev = begin, cur = begin + 1;
while (cur <= end)
{
if (a[cur] < a[keyi] && ++prev != cur)
Swap(&a[prev], &a[cur]);
++cur;
}
Swap(&a[prev], &a[keyi]);
keyi = prev;
return keyi;
}
//快速排序（遞歸）
void QuickSort(int* a, int begin, int end)
{
if (begin >= end)
{
return;
}
if ((end - begin + 1) < 15)
{
// 小區(qū)間用直接插入替代，減少遞歸調(diào)用次數(shù)
InsertSort(a + begin, end - begin + 1);
}
else
{
int keyi = PartSort1(a, begin, end);
//int keyi = PartSort2(a, begin, end);
//int keyi = PartSort3(a, begin, end);
QuickSort(a, begin, keyi - 1);
QuickSort(a, keyi + 1, end);
}
}快速排序非遞歸實現(xiàn)
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
typedef int STDataType;
typedef struct Stack
{
STDataType* a; //動態(tài)開辟數(shù)組
int capacity; //記錄棧的容量大小
int top; //記錄棧頂?shù)奈恢?
}Stack;
//棧的初始化
void StackInit(Stack* ps);
//釋放動態(tài)開辟的內(nèi)存
void StackDestroy(Stack* ps);
//壓棧
void StackPush(Stack* ps, STDataType data);
//出棧
void StackPop(Stack* ps);
//讀取棧頂?shù)脑?
STDataType StackTop(Stack* ps);
//判斷棧是否為空
bool StackEmpty(Stack* ps);
// Hoare法
int PartSort1(int* a, int begin, int end)
{
int mid = GetMidIndex(a, begin, end);
Swap(&a[begin], &a[mid]);
int left = begin, right = end;
int keyi = left;
while (left < right)
{
while (left < right && a[right] >= a[keyi])
{
--right;
}
while (left < right && a[left] <= a[keyi])
{
++left;
}
Swap(&a[left], &a[right]);
}
Swap(&a[left], &a[keyi]);
keyi = left;
return keyi;
}
// 挖坑法
int PartSort2(int* a, int begin, int end)
{
int mid = GetMidIndex(a, begin, end);
Swap(&a[begin], &a[mid]);
int left = begin, right = end;
int key = a[left];
int hole = left;
while (left < right)
{
while (left < right && a[right] >= key)
{
--right;
}
a[hole] = a[right];
hole = right;
while (left < right && a[left] <= key)
{
++left;
}
a[hole] = a[left];
hole = left;
}
a[hole] = key;
return hole;
}
int PartSort3(int* a, int begin, int end)
{
int mid = GetMidIndex(a, begin, end);
Swap(&a[begin], &a[mid]);
int keyi = begin;
int prev = begin, cur = begin + 1;
while (cur <= end)
{
if (a[cur] < a[keyi] && ++prev != cur)
Swap(&a[prev], &a[cur]);
++cur;
}
Swap(&a[prev], &a[keyi]);
keyi = prev;
return keyi;
}
void QuickSortNonR(int* a, int begin, int end)
{
Stack st;
StackInit(&st);
StackPush(&st, begin);
StackPush(&st, end);
while (!StackEmpty(&st))
{
int right = StackTop(&st);
StackPop(&st);
int left = StackTop(&st);
StackPop(&st);
int keyi = PartSort1(a, left, right);//三種方法任選其一
//int keyi = PartSort2(a, left, right);
//int keyi = PartSort3(a, left, right);
if (keyi + 1 < right)
{
StackPush(&st, keyi + 1);
StackPush(&st, right);
}
if (left < keyi - 1)
{
StackPush(&st, left);
StackPush(&st, keyi - 1);
}
}
StackDestroy(&st);
}
//棧的實現(xiàn)_函數(shù)定義
void StackInit(Stack* ps)
{
assert(ps);
//初始化時，可附初值，也可置空
ps->a = NULL;
ps->capacity = 0;
ps->top = 0;
}
void StackDestroy(Stack* ps)
{
assert(ps);
//若并未對ps->a申請內(nèi)存，則無需釋放
if (ps->capacity == 0)
return;
//釋放
free(ps->a);
ps->a = NULL;
ps->capacity = ps->top = 0;
}
void StackPush(Stack* ps,STDataType data)
{
assert(ps);
//若容量大小等于數(shù)據(jù)個數(shù)，則說明棧已滿，需擴容
if (ps->capacity == ps->top)
{
//若為第一次擴容，則大小為4，否則每次擴大2倍
int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
STDataType* tmp = (STDataType*)realloc(ps->a, sizeof(STDataType) * newCapacity);
if (tmp == NULL)
{
perror("realloc fail");
exit(-1);
}
ps->a = tmp;
ps->capacity = newCapacity;
}
//壓棧
ps->a[ps->top] = data;
ps->top++;
}
void StackPop(Stack* ps)
{
assert(ps);
assert(!StackEmpty(ps));
//出棧
ps->top--;
}
STDataType StackTop(Stack* ps)
{
assert(ps);
assert(!StackEmpty(ps));
//返回棧頂?shù)臄?shù)據(jù)
return ps->a[ps->top - 1];
}
bool StackEmpty(Stack* ps)
{
assert(ps);
//返回top
return ps->top == 0;
}到此這篇關(guān)于C語言實現(xiàn)快速排序的文章就介紹到這了,更多相關(guān)C語言實現(xiàn)快速排序內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
C語言使用Bresenham算法生成直線（easyx圖形庫）
這篇文章主要為大家詳細介紹了C語言使用Bresenham算法生成直線，基于easyx圖形庫，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2020-03-03
c++創(chuàng)建二維動態(tài)數(shù)組與內(nèi)存釋放問題
這篇文章主要介紹了c++創(chuàng)建二維動態(tài)數(shù)組與內(nèi)存釋放問題,本文通過實例代碼給大家介紹的非常詳細，具有一定的參考借鑒價值，需要的朋友可以參考下2018-06-06
C語言實現(xiàn)Linux下的socket文件傳輸實例
這篇文章主要介紹了C語言實現(xiàn)Linux下的socket文件傳輸?shù)姆椒?較為詳細的分析了C語言文件Socket文件傳輸客戶端與服務(wù)器端相關(guān)實現(xiàn)技巧,需要的朋友可以參考下2015-06-06
這篇文章主要介紹了C++?DLL注入工具的相關(guān)資料,并向大家分享了完整的源碼，具有一定的參考價值，希望對正在工作或?qū)W習的你有所幫助2022-02-02
C++入門教程之內(nèi)聯(lián)函數(shù)與extern?"C"詳解
C++中的內(nèi)聯(lián)函數(shù)與靜態(tài)函數(shù)靜態(tài)函數(shù)靜態(tài)函數(shù)的定義靜態(tài)函數(shù)又稱為內(nèi)部函數(shù),下面這篇文章主要給大家介紹了關(guān)于C++入門教程之內(nèi)聯(lián)函數(shù)與extern?"C"的相關(guān)資料,需要的朋友可以參考下2023-01-01
在本文里小編給大家分享的是關(guān)于c語言的注釋定界符知識點詳解，需要的朋友們可以跟著學習下。2020-02-02
C++實現(xiàn)刪除txt文件中指定內(nèi)容的示例代碼
這篇文章主要介紹了C++實現(xiàn)刪除txt文件中指定內(nèi)容的示例代碼，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2020-12-12
這篇文章主要為大家詳細介紹了opencv實現(xiàn)視場轉(zhuǎn)換，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2021-04-04
C++的智能指針是克服C++大坑的非常有用的的手段，之所以說它智能，是因為它為程序員克服了重要的編程問題——懸掛指針,下面通過本文給大家分享C++-(=)賦值操作符、智能指針編寫，感興趣的朋友一起看看吧2018-03-03
C++?Qt開發(fā)之使用QUdpSocket實現(xiàn)組播通信
Qt?是一個跨平臺C++圖形界面開發(fā)庫,利用Qt可以快速開發(fā)跨平臺窗體應用程序,本文將重點介紹如何運用QUdpSocket組件實現(xiàn)基于UDP的組播通信,感興趣的可以了解下2024-03-03