個(gè)人主頁(yè)：平行線也會(huì)相交
歡迎 點(diǎn)贊?? 收藏? 留言? 加關(guān)注??本文由 平行線也會(huì)相交 原創(chuàng)
收錄于專欄【數(shù)據(jù)結(jié)構(gòu)初階（C實(shí)現(xiàn)）】
冒泡排序
說(shuō)起來(lái)冒泡排序，是我們接觸到的最早的一個(gè)排序算法了，這次就當(dāng)進(jìn)行一個(gè)鞏固提升了。冒泡排序還被稱為交換排序。
冒泡排序：
它重復(fù)地走訪過(guò)要排序的元素列，依次比較兩個(gè)相鄰的元素，如果順序（如從大到小、首字母從Z到A）錯(cuò)誤就把他們交換過(guò)來(lái)。走訪元素的工作是重復(fù)地進(jìn)行，直到?jīng)]有相鄰元素需要交換，也就是說(shuō)該元素列已經(jīng)排序完成。
下面是冒泡排序的動(dòng)態(tài)圖：
冒泡排序特點(diǎn)：
1.時(shí)間復(fù)雜度：
O(N^2)。
2.空間復(fù)雜度：O(1).
3.穩(wěn)定性：穩(wěn)定。
冒泡排序代碼
void BubbleSort(int* a, int n)
{
for (int j = 0; j < n - 1; j++)
{
for (int i = 1; i < n - j; i++)
{
if (a[i - 1] > a[i])
Swap(&a[i - 1], &a[i]);
}
}
}
運(yùn)行結(jié)果如下：
冒泡排序優(yōu)化
我們知道冒泡排序的時(shí)間復(fù)雜度最壞情況是O(N^2)，最好情況依然是O(N^2)。所以我們對(duì)其進(jìn)行一個(gè)優(yōu)化：
void BubbleSort(int* a, int n)
{
for (int j = 0; j < n - 1; j++)
{
bool exchange = false;
for (int i = 1; i < n - j; i++)
{
if (a[i - 1] > a[i])
{
Swap(&a[i - 1], &a[i]);
}
exchange = true;
}
if (exchange == false)
break;
}
}
如果我們冒泡完一趟以后，發(fā)現(xiàn)數(shù)組有序（即一次交換都沒(méi)有發(fā)生），那么我們直接推出循環(huán)即可完成排序。
上面改進(jìn)的冒泡排序最好的情況的時(shí)間復(fù)雜度是O(N)。
快速排序
快速排序使用的是分治策略把一個(gè)序列分為兩個(gè)子序列。我們現(xiàn)在序列中選取一個(gè)元素作為基準(zhǔn)值（或者稱為關(guān)鍵值key），然后重新排序這個(gè)序列，如果是升序的話，所有比基準(zhǔn)值大的元素放到基準(zhǔn)值的右邊，所有比基準(zhǔn)值大的元素放在基準(zhǔn)值的左邊，經(jīng)過(guò)此分區(qū)結(jié)束之后，然后對(duì)左右子序列重復(fù)此過(guò)程，直到所有元素出現(xiàn)在相對(duì)應(yīng)的位置上。
其實(shí)簡(jiǎn)單來(lái)說(shuō)就是選出一個(gè)基準(zhǔn)值（一般選最左邊或者最右邊的），把這個(gè)基準(zhǔn)值放到它所對(duì)應(yīng)的位置上去。
下面是快速排序的動(dòng)態(tài)圖：
上圖就是選取最左邊的5作為基準(zhǔn)值，然后比5大的元素放到5的右邊，比5小的元素放到5的左邊。最終5就會(huì)出現(xiàn)在其所對(duì)應(yīng)的位置上。
舉個(gè)例子：
現(xiàn)在我們來(lái)對(duì)數(shù)組{6,1,2,7,9,3,4,5,10,8}來(lái)進(jìn)行排序。請(qǐng)看圖解：
經(jīng)過(guò)一次單趟排序后，上圖中的6已經(jīng)處于其對(duì)應(yīng)的位置了，所以對(duì)于快速排序的單趟排序中，本質(zhì)也是把一個(gè)元素排好。
文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-467314.html
快速排序代碼
QuickSort(int* a, int left, int right)
{
if (left >= right)
return;
int begin = left, end = right;
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;
//接下來(lái)進(jìn)行遞歸
//[begin , keyi - 1] keyi [keyi + 1 , end]
QuickSort(a, begin, keyi - 1);
QuickSort(a, keyi + 1, end);
}
運(yùn)行結(jié)果如下：
文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-467314.html
到了這里，關(guān)于十大排序算法之冒泡排序、快速排序的介紹的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
