溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
本篇內容主要講解“ 如何使用C語言實現快速排序”，感興趣的朋友不妨來看看。本文介紹的方法操作簡單快捷，實用性強。下面就讓小編來帶大家學習“ 如何使用C語言實現快速排序”吧!
快速排序的基本思想是：任取待排序數列中的一個數作為 key 值，通過某種方法使得 key 的左邊所有的數都比它小，右邊的數都比它大；以 key 為中心，將 key 左邊的數列與右邊的數列取出，做同樣的操作（取 key 值，分割左右區間），直至所有的數都到了正確的位置。
上述所提到的某種方法可以有很多種，例如：hoare法、挖坑法、前后指針法。它們雖然做法不相同，但做的都是同一件事——分割出 key 的左右區間（左邊的數比 key 小，右邊的數比 key 大）。
以數列 6，1，2，7，9，3，4，5，8，10 為例：
1.取最左邊為 key ，分別有 left 和 right 指向數列的最左端與最右端；
2. right 先走，找到比 key 小的數就停下來；
3. left 開始走，找到比 key 大的數就停下來；
4. 交換 left 與 right 所在位置的數；
5.重復上述操作，right 找小，left 找大，進行交換；
6. right 繼續找小；
7. left 繼續找大，若與 right 就停下來；
8.交換二者相遇位置與 key 處的值；
此時一趟排序就完成了，此時的數列有兩個特點：
1. key 所指向的值（6）已經到了正確的位置；
2. key 左邊的數字都比 key 要小，右邊的都比 key 要大；
接下來就是遞歸的過程了，分別對左右區間進行同樣的操作：
知道了詳解步驟，用代碼來實現并不困難，但是有很多很多的細節需要注意。（這里的代碼未經優化，當前的代碼有幾種極端的情況不能適應）
void Swap(int* p, int* q)
{
int tmp = *p;
*p = *q;
*q = tmp;
}
void QuickSort(int* a, int begin, int end)
{
//數列只有一個數，或無數列則返回
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);
}挖坑法相比于hoare法，思路上更為簡單易懂。
還是以同樣的數列 6，1，2，7，9，3，4，5，8，10 為例：
1. 先將第一個數存放到 key 中，形成一個坑位：分別有 left 和 right 指向數列的最左端與最右端；
2. right 先走，找到比 key 小的數，將該數丟到坑里；同時又形成了一個新的坑；
3. left 開始走，找到比 key 大的數，將該數丟到坑里；同時形成一個新的坑；
4. right繼續找小，進行重復的操作；
5. left 找大；
6. right 找小；
7. left 找大；
8.若二者相遇就停下來；將 key 值放入坑；
至此，一趟排序已經完成，我們發現此時的數列與hoare具有相同的特點：
1. key 所指向的值（6）已經到了正確的位置；
2. key 左邊的數字都比 key 要小，右邊的都比 key 要大；
挖坑法、hoare、前后指針法完成一趟排序后都具有相同的特點，所以不同版本的快速排序不一樣的只有單趟排序的實現，總體思路都是相同的。
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);
}以同樣的數列為例：
1. 取第一個值為 key ；有 prev 和 cur 分別指向數列開頭和 prev 的下一個數；
2. cur 先走，找到比 key 小的數就停下來；
3. ++prev ，交換 prev 與 cur 位置的數；（前兩次無需交換，因為自己與自己換沒有意義）
4. 重復此步驟；
5. 直到 cur 走完整個數列，交換 prev 與 key 處的值；
至此，第一趟排序就結束了，又是與前兩種方法相同的結果；
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);
}我們用三種方式實現了快速排序，其實這三種方式并無明顯的優劣之分。但是我們前面設計的快速排序其實是有兩個缺點的：
1.在最壞情況下它的的效率極慢；
2.在數據量太大時會造成棧溢出。
那么什么情況是最壞情況呢？答案是，當數據本身就是有序的時候（無論是逆序還是順序）。在最壞情況下，每次我們的 key 值都是最大或者最小，這樣就會使 key 與數列的每個數都比較一次，它的時間復雜度為 O(n^2);
為什么會發生棧溢出呢？因為我們的快速排序是利用遞歸實現的，有遞歸調用，就要建立函數棧幀，并且隨著遞歸的深度越深所要建立的函數棧幀的消耗就越大 。如這幅圖所示：
為了應對最壞情況會出現時間復雜度為 O(N^2) 的情況，有人提出了三數取中的方法。
舊方法中，我們每次選 key 都是數列的第一個元素。三數取中的做法是，分別取數列的第一個元素、最后一個元素和最中間的元素，選出三個數中不是最大也不是最小的那個數當作 key 值。
有了三數取中，之前的最壞情況立馬變成了最好情況。
由于hoare法、挖坑法、前后指針法最終的效果都相同且效率差異很小，所以就任意選取一個為例，其余兩者都類似。
//三數取中的函數
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);
}隨著遞歸的調用越深入，此時有個很大的缺點就是函數棧幀的消耗很大。但是同時又有一個好處，就是越往下，數列就越接近有序，且此時每個小區間的數據個數特別少。
那么有什么辦法可以取其長處避其短處呢？不知道你是否還記得插入排序的特點——數據越接近有序，效率就越高。并且，在數據量極少的情況下，時間復雜度為 O(N^2) 的插入排序與時間復雜度為 O(N*log N) 的快速排序基本沒有什么區別。所以，我們干脆就在排序數據量少的數列時，采用插入排序代替。
//三數取中的函數
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)
{
// 小區間用直接插入替代，減少遞歸調用次數
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);
}
}兩外兩種方法的代碼實現已打包完成，可在文末直接取用。
快速排序的非遞歸思路與遞歸相差無幾，唯一不同的是，非遞歸用棧或隊列模擬函數遞歸建立棧幀的過程。
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);
}//交換函數
void Swap(int* p, int* q)
{
int tmp = *p;
*p = *q;
*q = tmp;
}
//三數取中
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)
{
// 小區間用直接插入替代，減少遞歸調用次數
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);
}
}#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
typedef int STDataType;
typedef struct Stack
{
STDataType* a; //動態開辟數組
int capacity; //記錄棧的容量大小
int top; //記錄棧頂的位置
}Stack;
//棧的初始化
void StackInit(Stack* ps);
//釋放動態開辟的內存
void StackDestroy(Stack* ps);
//壓棧
void StackPush(Stack* ps, STDataType data);
//出棧
void StackPop(Stack* ps);
//讀取棧頂的元素
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);
}
//棧的實現_函數定義
void StackInit(Stack* ps)
{
assert(ps);
//初始化時，可附初值，也可置空
ps->a = NULL;
ps->capacity = 0;
ps->top = 0;
}
void StackDestroy(Stack* ps)
{
assert(ps);
//若并未對ps->a申請內存，則無需釋放
if (ps->capacity == 0)
return;
//釋放
free(ps->a);
ps->a = NULL;
ps->capacity = ps->top = 0;
}
void StackPush(Stack* ps,STDataType data)
{
assert(ps);
//若容量大小等于數據個數，則說明棧已滿，需擴容
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));
//返回棧頂的數據
return ps->a[ps->top - 1];
}
bool StackEmpty(Stack* ps)
{
assert(ps);
//返回top
return ps->top == 0;
}到此，相信大家對“ 如何使用C語言實現快速排序”有了更深的了解，不妨來實際操作一番吧！這里是億速云網站，更多相關內容可以進入相關頻道進行查詢，關注我們，繼續學習！
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
