冒泡排序
算法思路
每次冒泡操作都會(huì)對(duì)相鄰的兩個(gè)元素進(jìn)行比較，看是否滿(mǎn)足大小關(guān)系要求。如果不滿(mǎn)足就讓它倆互換妒茬。
一次冒泡會(huì)讓至少一個(gè)元素移動(dòng)到它應(yīng)該在的位置，重復(fù) n 次蔚晨，就完成了 n 個(gè)數(shù)據(jù)的排序工作乍钻。
經(jīng)過(guò)一次冒泡操作之后，6 這個(gè)元素已經(jīng)存儲(chǔ)在正確的位置上铭腕。要想完成所有數(shù)據(jù)的排序银择，我們只要進(jìn)行 6 次這樣的冒泡操作就行了。
void bubleSort(vector<int>& vec)
{
for (int i = 0; i < vec.size(); i++)
{
// 提前退出冒泡循環(huán)的標(biāo)志位
bool flag = false;
for (int j = 0; j < vec.size() - i - 1; ++j)
{
if (vec[j] > vec[j+1])
{
swap(vec[j], vec[j+1]);
flag = true;
}
}
if (!flag) break; // 掃描一趟沒(méi)有發(fā)生交換時(shí)累舷，說(shuō)明當(dāng)前索引右邊元素已經(jīng)有序浩考。
}
}
特點(diǎn)
冒泡排序是原地排序算法嗎？
冒泡的過(guò)程只涉及相鄰數(shù)據(jù)的交換操作被盈，只需要常量級(jí)的臨時(shí)空間析孽，所以它的空間復(fù)雜度為 O(1)，是一個(gè)原地排序算法害捕。冒泡排序是穩(wěn)定的排序算法嗎绿淋？
冒泡排序中闷畸，只有交換才可以改變兩個(gè)元素的前后順序尝盼。為了保證冒泡排序算法的穩(wěn)定性，當(dāng)有相鄰的兩個(gè)元素大小相等的時(shí)候佑菩，我們不做交換盾沫，相同大小的數(shù)據(jù)在排序前后不會(huì)改變順序，所以冒泡排序是穩(wěn)定的排序算法殿漠。-
冒泡排序算法的時(shí)間復(fù)雜度是多少赴精？
若序列是有序的，則只需要一趟掃描就可以結(jié)束绞幌，此時(shí)蕾哟，比較次數(shù)為n-1，移動(dòng)次數(shù)也為0莲蜘，此時(shí)情況最好谭确。
-
若序列是逆序的，則需要比較n(n-1)/2票渠，交換n(n-1)/2逐哈。此時(shí)情況最差。
image.png
平均時(shí)間 最差 最佳 輔助空間 穩(wěn)定性 O(n^2) O(n^2) O(n) O(1) 穩(wěn)定
選擇排序
算法思路
選擇排序會(huì)將整個(gè)數(shù)組分為已排序區(qū)間和未排序區(qū)間问顷，每次會(huì)從未排序區(qū)間中找到最小的元素昂秃，將其放到已排序區(qū)間的末尾禀梳。
void selectSort(vector<int> &vec)
{
for (int i = 0; i < vec.size(); i++)
{
int minIndex = i;
for (int j = i+1; j < vec.size(); j++)
{
if (vec[j] < vec[minIndex])
{
minIndex = j;
swap(vec[i], vec[minIndex]);
}
}
}
}
特點(diǎn)
選擇排序是原地排序算法嗎？
選擇排序空間復(fù)雜度為 O(1)肠骆，是一種原地排序算法算途。選擇排序是穩(wěn)定的排序算法嗎？
選擇排序是一種不穩(wěn)定的排序算法哗戈，選擇排序每次都要找剩余未排序元素中的最小值郊艘，并和前面的元素交換位置，這樣破壞了穩(wěn)定性唯咬。
比如 5纱注，8，5胆胰，2狞贱，9 這樣一組數(shù)據(jù)，使用選擇排序算法來(lái)排序的話(huà)蜀涨，第一次找到最小元素 2瞎嬉，與第一個(gè) 5 交換位置，那第一個(gè) 5 和中間的 5 順序就變了厚柳，所以就不穩(wěn)定了氧枣。-
選擇排序算法的時(shí)間復(fù)雜度是多少？
選擇排序有2個(gè)鮮明特點(diǎn)：- 運(yùn)行時(shí)間和輸入無(wú)關(guān)别垮，對(duì)于長(zhǎng)度為N的數(shù)組便监，選擇排序需要N(N-1)/2次比較和N次交換
- 數(shù)據(jù)移動(dòng)最少，選擇排序用了N次交換碳想，交換次數(shù)和數(shù)組大小是線(xiàn)性關(guān)系烧董。其他任何算法不具備這個(gè)特征，大部分都是線(xiàn)性對(duì)數(shù)或者平方胧奔。
平均時(shí)間 最差 最佳 輔助空間 穩(wěn)定性 O(n^2) O(n^2) O(n^2) O(1) 不穩(wěn)定
