C語言實現交換排序算法(冒泡,快速排序)的示例代碼
前言
查找和排序是數據結構與算法中不可或缺的一環，是前輩們在算法道路上留下的重要且方便的一些技巧，學習這些經典的查找和排序也能讓我們更好和更快的解決問題。在這個專欄中我們會學習六大查找和十大排序的算法與思想，而本篇將詳細講解其中的交換排序——冒泡排序和快速排序；
註意：本文中所有排序按照升序排序，降序隻需要把邏輯反過來即可！
一、冒泡排序
1.基本思想
對於很多同學來說冒泡排序是再熟悉不過瞭，冒泡的思想在於：不斷的比較兩個元素並交換，大的在右邊，小的在左邊；
有一個數組{5, 1, 4, 2, 8, 4}
第一輪
- arr[0] = 5和 arr[1] = 1比較 5 > 1，交換；
- arr[2] = 4和 arr[1] = 5比較 5 > 4，交換；
- arr[2] = 5和 arr[3] = 2比較 5 > 2，交換；
- arr[3] = 5和 arr[4] = 8比較 5 < 8，不交換；
- arr[4] = 8和 arr[5] = 4比較 8 > 4，交換；
第二輪
從arr[1]開始重復上述的步驟；
… …直到循環 N – 1 次，排序結束；
#include <stdio.h>
#include<stdlib.h>
//冒泡排序
void bubbleSort(int a[], int n)
{
//一共要掃描n-1趟
for(int i = 0; i < n - 1; i++)
{
//用來比較 交換
for(int j = 0; j < n - i - 1; j++)
{
if(a[j] > a[j + 1])
{
int temp = a[j + 1];
a[j + 1] = a[j];
a[j] = temp;
}
}
}
}
int main()
{
int arr[] = {5, 1, 4, 2, 8, 4};
int length = sizeof(arr) / sizeof(arr[0]);
bubbleSort(arr, length);
for(int i = 0; i < length; i++)
{
printf("%d", arr[i]);
}
system("pause");
return 0;
}
那麼問題來瞭，問題一：這裡我們發現對於這個數組而言在第二輪排序就已經排好瞭整體甚至穩定的有序，剩下的循環就相當於浪費瞭，那麼有沒有一種方法能夠判斷數組已經有序？
還有這樣一個數組{4, 2, 1, 5, 6, 8}
問題二：我們發現{5, 6, 8}的部分是已經有序瞭的，對於已經有序的部分還要繼續比較，那麼能不能確定出有序的部分和無序的部分的邊界呢？
2.優化
針對問題一，我們可以添加一個標志，用來標識數組是否有序：當某一輪排序沒有發生交換，就可以認為數組已經有序瞭；
針對問題二，我們可以記錄冒泡排序的過程中最後一次發生交換的地方index，如在下圖中index==1，每一次後面的排序隻要從第一個到index就可以瞭；
值得註意的是，不管怎樣去優化，最壞情況的時間復雜度都是O(n^2)，即數組逆序的情況；
3.擴展
雖然用棧實現冒泡排序可能在實際中沒有應用場景（也沒必要用），但是可能會有面試的時候要求用棧或者其他的結構去實現冒泡排序來考查對算法和思想熟練度，所以這裡也提供用棧實現冒泡排序的思路；
void bubbleSort(int a[], int n)
{
//定義兩個棧S1和S2
stack<int>stk1, stk2;
//將數組中的所有元素入棧S1
for (int i = 0; i < n; i++)
{
stk1.push(a[i]);
}
//循環N次 每一次找出最大的元素（就像真冒泡一樣 最大的元素浮在最上面）
for (int i = 0; i < n; i++)
{
//如果S1不為空
while (!stk1.empty())
{
//如果S2為空就把棧S1頂的元素入棧S2
if (stk2.empty())
{
stk2.push(stk1.top());
stk1.pop();
}
else
{
int temp = 0;//用於接收需要交換的元素
if (stk1.top() < stk2.top())
{
//如果S1的棧頂小於S2的棧頂 把S1的棧頂壓在S2的棧頂下面
temp = stk2.top();
stk2.pop();
stk2.push(stk1.top());
stk1.pop();
stk2.push(temp);
}
else
{
stk2.push(stk1.top());
stk1.pop();
}
}
}
//把最大的元素從後往前更新回原數組中
a[n - i - 1] = stk2.top();
stk2.pop();
//把剩下的元素倒棧 重復
for (int j = stk2.size(); j > 0; j--)
{
stk1.push(stk2.top());
stk2.pop();
}
}
}
二、快速排序
1.基本思想
選取一個基準（可以認為是要放到排序以後正確的位置的元素，可以是第一個元素、最後一個 中間的、隨機的都可以）；
把數組中的元素做一個劃分，每一趟劃分將作為基準的值x放到排序後數組正確的位置，並將所有比x小的放到左邊，比x大的放到右邊；
有一個數組{1, 8, 3, 9, 4, 5, 4, 7}
假定選擇元素arr[7] = 7為基準，就是要把7放在正確的位置，那麼隻有兩種情況：
要麼7本身就是正確的位置，要麼就在前面；
第一步：初始化指針 i = -1，j = 0，把 j 指向的元素和7比較 ，當1 < 7，將 i++， 交換 i 和 j 指向的元素，j++；
第二步：把 j 指向的元素和7比較 ，當8 > 7，將 j++；
第三步：把 j 指向的元素和7比較 ，當3 < 7，將 i++， 交換 i 和 j 指向的元素，j++；
第四步：把 j 指向的元素和7比較 ，當4 < 7，將 i++， 交換 i 和 j 指向的元素，j++；
第五步：把 j 指向的元素和7比較 ，當5 < 7，將 i++， 交換 i 和 j 指向的元素，j++；
第五步：把 j 指向的元素和7比較 ，當4 < 7，將 i++， 交換 i 和 j 指向的元素，j++；
第六步：當j到7遍歷結束，讓i++的位置和7交換，第一趟排序結束；
如此一來，基準7就找到瞭它在數組中的正確位置，並且把數組劃分成瞭兩邊【0，5）和（5,7】這時再選一個基準再進行上述步驟，如下圖所示：
是不是覺得很眼熟？沒錯這就是一棵二叉樹：
2.優化
既然是二叉樹，那麼排出一棵斜樹自然就是最壞的情況；要緩解這個問題，可以以中間的值為基準來減少這種情況的發生；
即復雜度與數組長度和基準的選擇有關，尾基準是O(n^2)因為n趟每一趟劃分需要O(n)，而平衡樹是O(nlogn)，通過數學方法能夠得到更優的基準選擇，但無論選什麼為基準都應該能滿足：基準左邊小、右邊大；
我們之前說過，快速排序其實是一個不穩定排序（不穩定的排序就意味著交換的次數多，如果需要按多條件排序就會亂），而我們又說過任何一個不穩定的排序算法都有辦法使其變得穩定，用到的是以空間換時間的思想；
也就是我們可以用一個變量對原來的順序做標記；
3.代碼
既然是通過不斷劃分數組來減少比較的次數，這一聽就知道用到瞭分治的思想，也就是可以用遞歸來實現代碼：
#include <stdio.h>
#include<stdlib.h>
//快排
void quickSort(int a[], int low, int high)
{
if(low < high)
{
int i = low;//這裡以i下標的值為基準
int j = high;
int k = a[low];//k是用來記錄基準的值
while(i < j)
{
//從右往左找第一個比k要小的值
while(i < j && a[j] >= k)
{
j--;
}
if(i < j)
{
a[i++] = a[j];
}
//從左往右找第一個比k要大的值
while(i < j && a[i] < k)
{
i++;
}
if(i < j)
{
a[j--] = a[i];
}
}
a[i] = k;
//遞歸
quickSort(a, low, i - 1);
quickSort(a, i + 1, high);
}
}
int main()
{
int arr[] = {1, 8, 3, 9, 4, 5, 4, 7};
int length = sizeof(arr) / sizeof(arr[0]);
quickSort(arr, 0, length - 1);
for(int i = 0; i < length; i++)
{
printf("%d ", arr[i]);
}
system("pause");
return 0;
}
運行結果
到此這篇關於C語言實現交換排序算法(冒泡,快速排序)的示例代碼的文章就介紹到這瞭,更多相關C語言交換排序算法內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet！