前言

????????排序(Sorting) 是計(jì)算機(jī)程序設(shè)計(jì)中的一種重要操作，它的功能是將一個(gè)數(shù)據(jù)元素（或記錄）的任意序列，重新排列成一個(gè)關(guān)鍵字有序的序列。所謂排序，就是使一串記錄，按照其中的某個(gè)或某些關(guān)鍵字的大小，遞增或遞減的排列起來(lái)的操作。

????????排序算法，就是如何使得記錄按照要求排列的方法。排序算法在很多領(lǐng)域得到相當(dāng)?shù)刂匾?#xff0c;尤其是在大量數(shù)據(jù)的處理方面。一個(gè)優(yōu)秀的算法可以節(jié)省大量的資源。

簡(jiǎn)介

????????所謂排序算法，即通過(guò)特定的算法因式將一組或多組數(shù)據(jù)按照既定模式進(jìn)行重新排序。這種新序列遵循著一定的規(guī)則，體現(xiàn)出一定的規(guī)律，因此，經(jīng)處理后的數(shù)據(jù)便于篩選和計(jì)算，大大提高了計(jì)算效率。對(duì)于一個(gè)排序算法的優(yōu)劣，我們需要從它的時(shí)間復(fù)雜度、空間復(fù)雜度和穩(wěn)定性三個(gè)方面來(lái)考慮。什么叫穩(wěn)定性呢？即當(dāng)兩個(gè)相同的元素同時(shí)出現(xiàn)于某個(gè)序列之中，則經(jīng)過(guò)一定的排序算法之后，兩者在排序前后的相對(duì)位置不發(fā)生變化。換言之，即便是兩個(gè)完全相同的元素，它們?cè)谂判蜻^(guò)程中也是各有區(qū)別的。

? ? ? ? 本篇文章講述的是排序算法中的選擇排序，其中包含了兩種排序算法，分別是直接選擇排序和堆排序，下面將會(huì)一一為大家詳細(xì)介紹。（用升序進(jìn)行講解）

??????

基本思想

? ? ? ? ?選擇排序算法的基本思想是為每一個(gè)位置選擇當(dāng)前最小的元素。

?1.直接選擇排序?

????????下面我們首先來(lái)看一看直接選擇排序算法的動(dòng)圖演示：

? ? ? ? 看了上圖我們可以得知，直接選擇排序算法是首先從第1個(gè)位置開(kāi)始對(duì)全部元素進(jìn)行選擇，選出全部元素中最小的給該位置，再對(duì)第2個(gè)位置進(jìn)行選擇，在剩余元素中選擇最小的給該位置即可；以此類推，重復(fù)進(jìn)行“最小元素”的選擇，直至完成第(n-1)個(gè)位置的元素選擇，則第n個(gè)位置就只剩唯一的最大元素，此時(shí)不需再進(jìn)行選擇。?

? ? ? ? 直接選擇排序算法的思路以及代碼都比較簡(jiǎn)單，有了上述講解相信大家都已經(jīng)對(duì)其了解了。

?2.堆排序

? ? ? ? 直接選擇排序是選擇排序的一種，但是其時(shí)間復(fù)雜度很高，在實(shí)際應(yīng)用中效率非常低下，那有沒(méi)有其他的效率高的選擇排序呢？答案當(dāng)然是有的，那就是堆排序(Heapsort)，堆排序主要借助了我們的數(shù)據(jù)結(jié)構(gòu)--堆來(lái)實(shí)現(xiàn)。（若是對(duì)堆不了解的可以去閱讀我的另一篇文章數(shù)據(jù)結(jié)構(gòu)--堆）。

????????當(dāng)一個(gè)堆是大根堆的時(shí)候我們知道堆頂元素永遠(yuǎn)是整個(gè)堆中最大的元素，因此每次取堆頂我們都會(huì)得到一個(gè)最大值（降序則需要用小根堆），這剛好與我們選擇排序算法的基本思想相同。下面我將同圖畫(huà)來(lái)給大家進(jìn)行演示：

????????此時(shí)堆頂元素是數(shù)組中最大的元素，將其與最后一個(gè)元素交換位置，并對(duì)堆進(jìn)行調(diào)整。

? ? ? ?此時(shí)對(duì)于 9 這個(gè)元素我們可以理解為已經(jīng)把它從該堆中刪除了，此時(shí)堆中只剩下4個(gè)元素，重復(fù)此操作即可完成排序，大家可以根據(jù)下方的代碼具體了解。

代碼實(shí)現(xiàn)

?1.直接插入排序

? ? ? ? 先看原始代碼：

void Select_sort(vector<int>& a)
{int n = a.size();//對(duì)于直接選擇排序來(lái)說(shuō)，只需要進(jìn)行n - 1次循環(huán)即可for (int i = 0; i < n - 1; i++){int minpos = i;//從i位置開(kāi)始，遍歷其后面的數(shù)組，找到最小值for (int j = i + 1; j < n; j++){if (a[j] < a[minpos]){minpos = j;}}//將最小值所處的位置與i位置的值進(jìn)行交換即可swap(a[i], a[minpos]);}
}

? ? ? ? 解析：兩次循環(huán)即可完成，第一層循環(huán)控制需要排序的位置，第二次循環(huán)尋找該位置后的最小值。

? ? ? ? 對(duì)于直接選擇排序，我們有一種優(yōu)化辦法，可以使其的時(shí)間效率增加一倍，雖說(shuō)時(shí)間復(fù)雜度是相同的，杯水車(chē)薪，但也是一種思路。?

具體思路：

? ? ? ? 第一層循環(huán)我們從數(shù)組的兩端開(kāi)始遍歷；

????????第二次循環(huán)我們同時(shí)尋找其中間的最大值和最小值。

? ? ? ? 代碼如下：

void Select_sort(vector<int>& a)
{int n = a.size();//數(shù)組大小為奇數(shù)，最后會(huì)處于left == right；當(dāng)數(shù)組大小為偶數(shù)時(shí)，最后會(huì)處于left > right//因此結(jié)束條件為left < rightfor (int left = 0, right = n - 1; left < right; left++, right--){int minpos = left;int maxpos = left;//從left位置遍歷其后面到right位置之前的數(shù)組，找到最小值和最大值for (int i = left + 1; i < right; i++){if (a[i] < a[minpos]){minpos = i;}if (a[i] > a[maxpos]){maxpos = i;}}//此時(shí)在交換元素時(shí)需要注意一個(gè)細(xì)節(jié)：//當(dāng)我們將a[right]與a[maxpos]交換時(shí)，maxpos位置上之前可能是left的位置，這樣在之后的交換會(huì)出現(xiàn)問(wèn)題，因此我們需要進(jìn)行判斷接下來(lái)的交換是否還要進(jìn)行swap(a[right], a[maxpos]);if (a[minpos] < a[left]){swap(a[left], a[minpos]);}}
}

? ? ? ? ?對(duì)于優(yōu)化后的直接選擇排序在最后的交換步驟時(shí)的細(xì)節(jié)需要大家額外注意，大家可以自己用一個(gè)倒序數(shù)組親自體驗(yàn)一下，以便有更深刻的體會(huì)。

?2.堆排序?

? ? ? ? 先看代碼：

//向下調(diào)整算法
void AdjustDown(vector<int>& a, int parent, int end)
{int child = parent * 2 + 1;while (child < end){if (child + 1 < end && a[child] < a[child + 1]){child++;}if (a[child] > a[parent]){swap(a[child], a[parent]);parent = child;child = parent * 2 + 1;}else{break;}}
}void Heap_sort(vector<int>& a)
{int n = a.size();//首先進(jìn)行建堆for (int i = (n - 1 - 1) / 2; i >= 0; i--){AdjustDown(a, i, n);}//進(jìn)行排序for (int i = n - 1; i > 0; i--){swap(a[0], a[i]);AdjustDown(a, 0, i);}
}

? ? ? ? 對(duì)于堆排序來(lái)說(shuō)，比較重要的地方是當(dāng)我們?cè)谶M(jìn)行排序時(shí)，一定要注意當(dāng)每一次交換完元素后，堆中的數(shù)據(jù)就會(huì)減少一個(gè)，因此當(dāng)我們?cè)谧约簩?xiě)向下調(diào)整算法時(shí)，一定要注意此時(shí)堆中的數(shù)據(jù)個(gè)數(shù)，不然就會(huì)出現(xiàn)錯(cuò)誤。?

? ? ? ? 注：對(duì)于建堆和向下調(diào)整算法不了解的朋友可以先去看一看數(shù)據(jù)結(jié)構(gòu)--堆，里面有較為詳細(xì)的介紹。

總結(jié)

1.時(shí)空復(fù)雜度

? ? ? ? 經(jīng)過(guò)分析我們可以得到直接選擇排序的時(shí)間復(fù)雜度和空間復(fù)雜度，兩層for循環(huán)以及常數(shù)個(gè)變量，因此

直接選擇排序：

? ? ? ? 時(shí)間復(fù)雜度：O（N ^ 2）

? ? ? ? 空間復(fù)雜度：O（1）

????????對(duì)于堆排序來(lái)說(shuō)，時(shí)間復(fù)雜度由建堆操作和排序操作決定，具體的計(jì)算過(guò)程較為復(fù)雜，感興趣的可以自己搜索一下，這里不再贅述。因此

堆排序：

? ? ? ? 時(shí)間復(fù)雜度：O（NlogN）

? ? ? ? 空間復(fù)雜度：O（1）

????????堆排序算法的總體時(shí)間復(fù)雜度是?O(n log n)，這是因?yàn)榻ǘ阎?#xff0c;還需要進(jìn)行?n-1?次的排序操作，每次排序操作的時(shí)間復(fù)雜度是?O(log n)。但是，建堆本身的時(shí)間復(fù)雜度是線性的，這使得堆排序在某些情況下比其他?O(n log n)?排序算法更高效。?

2.穩(wěn)定性

????????在排序算法中，我們不光要關(guān)注算法的時(shí)空復(fù)雜度，還在看看算法的穩(wěn)定性，什么是穩(wěn)定性呢？

穩(wěn)定性是假定在待排序的記錄序列中，存在多個(gè)具有相同的關(guān)鍵字的記錄，若經(jīng)過(guò)排序，這些記錄的相對(duì)次序保持不變，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，則稱這種排序算法是穩(wěn)定的；否則稱為不穩(wěn)定的。

? ? ? ? 簡(jiǎn)單分析我們可以知道選擇排序算法是不穩(wěn)定的。舉例說(shuō)明：序列58539．我們知道第一遍選擇第1個(gè)元素“5”會(huì)和元素“3”交換，那么原序列中的兩個(gè)相同元素“5”之間的前后相對(duì)順序就發(fā)生了改變。因此，我們說(shuō)選擇排序不是穩(wěn)定的排序算法，它在計(jì)算過(guò)程中會(huì)破壞穩(wěn)定性。（對(duì)于直接選擇排序以及堆排序都是如此）

直接選擇排序： 不穩(wěn)定

堆排序：? ? ? ? ? ? 不穩(wěn)定

尾聲

????????若有紕漏或不足之處歡迎大家在評(píng)論區(qū)留言或者私信，同時(shí)也歡迎各位一起探討學(xué)習(xí)。感謝您的觀看！