前言

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

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

簡介

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

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

??????

基本思想

? ? ? ? ?選擇排序算法的基本思想是為每一個位置選擇當前最小的元素。

?1.直接選擇排序?

????????下面我們首先來看一看直接選擇排序算法的動圖演示：

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

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

?2.堆排序

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

????????當一個堆是大根堆的時候我們知道堆頂元素永遠是整個堆中最大的元素，因此每次取堆頂我們都會得到一個最大值（降序則需要用小根堆），這剛好與我們選擇排序算法的基本思想相同。下面我將同圖畫來給大家進行演示：

????????此時堆頂元素是數(shù)組中最大的元素，將其與最后一個元素交換位置，并對堆進行調整。

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

代碼實現(xiàn)

?1.直接插入排序

? ? ? ? 先看原始代碼：

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

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

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

具體思路：

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

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

? ? ? ? 代碼如下：

void Select_sort(vector<int>& a)
{int n = a.size();//數(shù)組大小為奇數(shù)，最后會處于left == right；當數(shù)組大小為偶數(shù)時，最后會處于left > right//因此結束條件為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;}}//此時在交換元素時需要注意一個細節(jié)：//當我們將a[right]與a[maxpos]交換時，maxpos位置上之前可能是left的位置，這樣在之后的交換會出現(xiàn)問題，因此我們需要進行判斷接下來的交換是否還要進行swap(a[right], a[maxpos]);if (a[minpos] < a[left]){swap(a[left], a[minpos]);}}
}

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

?2.堆排序?

? ? ? ? 先看代碼：

//向下調整算法
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();//首先進行建堆for (int i = (n - 1 - 1) / 2; i >= 0; i--){AdjustDown(a, i, n);}//進行排序for (int i = n - 1; i > 0; i--){swap(a[0], a[i]);AdjustDown(a, 0, i);}
}

? ? ? ? 對于堆排序來說，比較重要的地方是當我們在進行排序時，一定要注意當每一次交換完元素后，堆中的數(shù)據(jù)就會減少一個，因此當我們在自己寫向下調整算法時，一定要注意此時堆中的數(shù)據(jù)個數(shù)，不然就會出現(xiàn)錯誤。?

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

總結

1.時空復雜度

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

直接選擇排序：

? ? ? ? 時間復雜度：O（N ^ 2）

? ? ? ? 空間復雜度：O（1）

????????對于堆排序來說，時間復雜度由建堆操作和排序操作決定，具體的計算過程較為復雜，感興趣的可以自己搜索一下，這里不再贅述。因此

堆排序：

? ? ? ? 時間復雜度：O（NlogN）

? ? ? ? 空間復雜度：O（1）

????????堆排序算法的總體時間復雜度是?O(n log n)，這是因為建堆之后，還需要進行?n-1?次的排序操作，每次排序操作的時間復雜度是?O(log n)。但是，建堆本身的時間復雜度是線性的，這使得堆排序在某些情況下比其他?O(n log n)?排序算法更高效。?

2.穩(wěn)定性

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

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

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

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

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

尾聲

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