前言
今天學(xué)習(xí)了一些簡(jiǎn)單的排序算法,其實(shí)在我們平時(shí)解決問(wèn)題中經(jīng)常用到,今天正好一起看了看,記錄一下。如果對(duì)你也有幫助,我很開(kāi)心~
一、桶排序（Bucket Sort）
桶排序是一種排序算法，它將數(shù)組劃分為一些有序的桶，然后每個(gè)桶再分別排序。最后，將所有的桶合并起來(lái)，得到一個(gè)有序的數(shù)組。桶排序的核心思想是將數(shù)據(jù)分散到不同的桶中，每個(gè)桶內(nèi)部進(jìn)行排序，最后將所有桶的數(shù)據(jù)合并。
思路:
- 確定桶的數(shù)量，并創(chuàng)建這些桶
- 遍歷原始數(shù)組，將每個(gè)元素放入相應(yīng)的桶中
- 對(duì)每個(gè)桶內(nèi)部進(jìn)行排序?？梢允褂闷渌判蛩惴?，或者遞歸地使用桶排序
- 將所有桶的元素按順序合并成最終的有序數(shù)組
適用于
數(shù)據(jù)分布比較均勻的情況,因?yàn)槿绻總€(gè)桶的大小相對(duì)一致，就減少了在桶內(nèi)進(jìn)行排序的工作量,時(shí)間復(fù)雜度由桶的數(shù)量和每個(gè)桶內(nèi)采用的內(nèi)部排序算法相關(guān)
小唐有話說(shuō):我感覺(jué)桶排序也是拿空間換時(shí)間的感覺(jué),和哈希表有點(diǎn)像有沒(méi)有!!!但是他們的主要的區(qū)別在于桶排序是一種排序算法，重于對(duì)元素的排序，而哈希表是一種數(shù)據(jù)結(jié)構(gòu)，用于快速查找和插入
// 桶排序函數(shù)
void bucketSort(vector<float>& arr) {
// 找到最大值和最小值
//*max_element,*min_element是 C++ 標(biāo)準(zhǔn)庫(kù) <algorithm> 頭文件中的函數(shù)，分別用于找到范圍內(nèi)的最大值和最小值。
float max_val = *max_element(arr.begin(), arr.end());
float min_val = *min_element(arr.begin(), arr.end());
int bucket_count = 10; // 這里假設(shè)使用 10 個(gè)桶
vector<vector<float>> buckets(bucket_count);// 創(chuàng)建桶
// 將元素放入桶中
for (float num : arr) {//是 C++11 引入的一種基于范圍的 for 循環(huán)語(yǔ)法，也稱為范圍-based for循環(huán)
//表示遍歷浮點(diǎn)數(shù)數(shù)組 arr 中的每個(gè)元素，并將每個(gè)元素賦值給變量 num，然后執(zhí)行循環(huán)體內(nèi)的操作。
int index = int(bucket_count * (num - min_val) / (max_val - min_val));
buckets[index].push_back(num);
}
// 對(duì)每個(gè)桶內(nèi)部進(jìn)行排序，這里使用標(biāo)準(zhǔn)庫(kù)的排序函數(shù)
for (auto& bucket : buckets) {
sort(bucket.begin(), bucket.end());
}
// 將所有桶的元素合并
arr.clear();
for (const auto& bucket : buckets) {
arr.insert(arr.end(), bucket.begin(), bucket.end());
}
}
對(duì)于此處的例子,時(shí)間復(fù)雜度: O(n + 10 * log(10)),其中10是是因?yàn)榉至?0個(gè)桶,分桶的過(guò)程時(shí)間復(fù)雜度是 O(n),std::sort是一種改進(jìn)的快速排序算法,它的平均時(shí)間復(fù)雜度是O(n log n)
二、冒泡排序（Bubble Sort）
冒泡排序是一種簡(jiǎn)單的排序算法，其基本思想是通過(guò)不斷地交換相鄰元素，將較大的元素逐漸移到右側(cè)（或較小的元素逐漸移到左側(cè)），從而達(dá)到排序的目的。小唐有話說(shuō):不知道大家有沒(méi)有印象!反正小唐印象超級(jí)無(wú)敵深刻,大一學(xué)C語(yǔ)音的時(shí)候就對(duì)它印象深刻,到現(xiàn)在仍然記憶尤新,當(dāng)初看了好多好多遍才弄懂的算法,現(xiàn)在看簡(jiǎn)直簡(jiǎn)單的不能再簡(jiǎn)單,這就是輕舟已過(guò)萬(wàn)重山叭!
思路:
- 從第一個(gè)元素開(kāi)始，依次比較相鄰的兩個(gè)元素
- 如果發(fā)現(xiàn)順序不對(duì)（即當(dāng)前元素大于下一個(gè)元素），則交換這兩個(gè)元素的位置
- 繼續(xù)進(jìn)行相鄰元素的比較和交換，直到整個(gè)序列變得有序
- 重復(fù)上述步驟，每次都會(huì)確定一個(gè)最大（或最?。┰氐奈恢?，直到整個(gè)序列有序?yàn)橹?/li>
冒泡排序的時(shí)間復(fù)雜度為 O(n^2),因?yàn)闀r(shí)間復(fù)雜度較高，在實(shí)際應(yīng)用中較少使用，特別是對(duì)于大規(guī)模數(shù)據(jù)集。
// 冒泡排序函數(shù)
void bubbleSort(vector<int>& arr) {
int n = arr.size();
for (int i = 0; i < n - 1; ++i) {
for (int j = 0; j < n - i - 1; ++j) { //這里注意,內(nèi)層循環(huán)只用到n-i-1,因?yàn)楹竺娴囊呀?jīng)排過(guò)啦
// 如果當(dāng)前元素大于下一個(gè)元素，則交換它們
if (arr[j] > arr[j + 1]) {
swap(arr[j], arr[j + 1]);
}
}
}
}
二、快速排序（Quick Sort）
快速排序是一種高效的排序算法，屬于比較排序的一類。它基于分治法的思想，通過(guò)選擇一個(gè)基準(zhǔn)元素，將數(shù)組分成兩個(gè)子數(shù)組，使得左邊的元素都小于基準(zhǔn)元素，右邊的元素都大于基準(zhǔn)元素，然后對(duì)這兩個(gè)子數(shù)組分別遞歸地應(yīng)用相同的排序算法。
思路:
- 選擇一個(gè)基準(zhǔn)元素（通常是數(shù)組中間的元素）
- 將數(shù)組分成兩個(gè)子數(shù)組，左邊的元素小于等于基準(zhǔn)元素，右邊的元素大于等于基準(zhǔn)元素
- 對(duì)左右子數(shù)組分別遞歸地應(yīng)用快速排序
- 合并排序好的左右子數(shù)組
// 快速排序函數(shù)
void quickSort(vector<int>& arr, int low, int high) {
if (low < high) {
int pivot = arr[high];// 選擇最右邊的元素作為基準(zhǔn)元素
int i = low - 1;
cout << i << endl;
// 將小于等于基準(zhǔn)元素的元素移動(dòng)到左邊
for (int j = low; j < high; ++j) {
if (arr[j] <= pivot) {
++i;
swap(arr[i], arr[j]);
}
}
// 將基準(zhǔn)元素移動(dòng)到正確的位置
swap(arr[i + 1], arr[high]);
int pivotIndex = i + 1;
// 遞歸排序左右子數(shù)組
quickSort(arr, low, pivotIndex - 1);
quickSort(arr, pivotIndex + 1, high);
}
}
快速排序的平均時(shí)間復(fù)雜度為O(n log n)，最差時(shí)間復(fù)雜度是 O(n^2)，發(fā)生在數(shù)組已經(jīng)有序或近乎有序的情況下。
寫(xiě)了快速排序的話就順便在這最后介紹一下
std::sort
std::sort 是 C++ 標(biāo)準(zhǔn)庫(kù)提供的排序函數(shù)，其實(shí)現(xiàn)通?；谝环N改進(jìn)的快速排序算法（introsort）
相同點(diǎn):
1.平均時(shí)間復(fù)雜度都為 O(n log n)
2.兩者都基于分治法的思想，通過(guò)遞歸地劃分?jǐn)?shù)組并排序子數(shù)組來(lái)完成排序。
不同點(diǎn):
1.std::sort 的具體實(shí)現(xiàn)可能會(huì)結(jié)合多種排序算法，而不僅僅是快速排序。標(biāo)準(zhǔn)庫(kù)通常會(huì)選擇在給定情況下最適合的排序算法，這可能包括快速排序、堆排序、插入排序等。
2.std::sort 通常是穩(wěn)定排序的，即相等元素的相對(duì)順序在排序后保持不變。而經(jīng)典的快速排序算法是不穩(wěn)定的，盡管可以通過(guò)一些改進(jìn)策略使其成為穩(wěn)定排序。
3.適應(yīng)性： std::sort 可能會(huì)根據(jù)輸入數(shù)據(jù)的性質(zhì)在不同情況下選擇不同的排序算法，以提高性能。這種自適應(yīng)性是標(biāo)準(zhǔn)庫(kù)排序函數(shù)的一個(gè)特點(diǎn)。小唐有話說(shuō):總得來(lái)說(shuō)官方給的就是比我們自己寫(xiě)的厲害??!沒(méi)要求自己寫(xiě),咱們平時(shí)就還是用官方的叭!當(dāng)然原理還是得掌握的!文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-824498.html
總結(jié)
以上就是今天總結(jié)的內(nèi)容,一些簡(jiǎn)單的排序算法,主要具體的還是根據(jù)題目隨機(jī)應(yīng)變,后續(xù)也會(huì)繼續(xù)記錄學(xué)習(xí)的一些算法呀,唐怡佳繼續(xù)加油!文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-824498.html
到了這里，關(guān)于【排序算法詳細(xì)介紹】桶排序（Bucket Sort）冒泡排序（Bubble Sort）快速排序（Quick Sort）的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
