前言
上一期我們已經(jīng)介紹了，排序、為什么要有排序以及排序在實際生活中的應(yīng)用。并且介紹并實現(xiàn)了直接插入排序和它的優(yōu)化即希爾排序~！本期我們再來學習一組排序 ---- "選擇排序"即直接選擇排序和堆排序~！
本期內(nèi)容介紹
直接選擇排序
堆排序
選擇排序的基本思想
每次從待排序的數(shù)據(jù)元素的序列中選出最小或最大的一個元素，存放在當前序列的起始位置，直到將全部待排序的數(shù)據(jù)元素排完。
直接選擇排序
在元素集合a[i].....a[n-1]中，選擇一個最大或最小的數(shù)據(jù)，如果他不是這個序列中的最后一個或第一個，則與該序列中的最后一個或第一個進行交換，將剩余的元素重復上述操作，直到序列的元素只有一個則結(jié)束！
OK，舉個栗子畫個圖（這里是以升序距離的）：
OK，直接選擇排序的過程就是這樣的，下面我們來實現(xiàn)一下：還是和以前一樣，先寫單趟再來改造整體：
單趟
int left = begin;//當前序列的最左端
int min = begin;//最小的元素的下標
for (int i = begin; i < n; i++)
{
if (a[min] > a[i])
min = i;
}
Swap(&a[left], &a[min]);//最左端的元素與當前序列中最小的元素交換整體
直接選擇排序改造整體也很簡單，只需要，讓每個元素都重復單趟即可~！
void SelectSort(int* a, int n)
{
for (int begin = 0; begin < n; begin++)
{
int left = begin;//當前序列的最左端
int min = begin;//最小的元素的下標
for (int i = begin; i < n; i++)
{
if (a[min] > a[i])
min = i;
}
Swap(&a[left], &a[min]);//最左端的元素與當前序列中最小的元素交換
}
}OK，測試一下：
OK，沒有問題。這樣寫實每次找到當前序列中最小的一個，然后與最左端（升序）交換，我們其實可以對他進行一個小優(yōu)化的--->每次找到當前序列中的兩個元素(一個最小，一個最大)，最小的與當前序列的最左端交換，最大與當前序列的最右端交換~！
OK，還是先寫單趟，在改造多趟：
單趟
int min = begin, max = begin;
for (int i = begin + 1; i <= right; i++)
{
if (a[min] > a[i])
min = i;//選出最小
if (a[max] < a[i])
max = i;//選出最大
}
Swap(&a[begin], &a[min]);//最小與左端交換
Swap(&a[right], &a[max]);//最大與右端交換整體
void SelectSort(int* a, int n)
{
int begin = 0, right = n - 1;
while (begin < right)
{
int min = begin, max = begin;
for (int i = begin + 1; i <= right; i++)
{
if (a[min] > a[i])
min = i;
if (a[max] < a[i])
max = i;
}
Swap(&a[begin], &a[min]);
Swap(&a[right], &a[max]);
++begin;
--right;
}
}這就是一次選出兩個的整體。OK，我們來個栗子測試一下：
怎么沒有實現(xiàn)排序呢？是我們的思想有問題？？？OK，遇事不慌，調(diào)試走起：
這是調(diào)試找到的第一次最大和最小的元素的下標~！然后下來就是最小與左端交換，最大與右端交換，但此時最大恰好在最左端，一執(zhí)行最小與最左端交換后在在執(zhí)行在最大與最右交換時發(fā)現(xiàn)最大的已經(jīng)不在原來的位置了~！這就導致了上述的亂序！
解決方案：在交換完最小與最左端后，判斷一下最大的位置，如果最大的是在最左端，則此時最大值應(yīng)該被換到了最小值的位置，因此，我們只需要調(diào)整一下最大值是在最小值的位置即可，即max = min~！
void SelectSort(int* a, int n)
{
int left = 0, right = n - 1;
while (left < right)
{
int min = left, max = left;
for (int i = left + 1; i <= right; i++)
{
if (a[min] > a[i])
min = i;
if (a[max] < a[i])
max = i;
}
Swap(&a[left], &a[min]);
if (max == left)
max = min;
Swap(&a[right], &a[max]);
++left;
--right;
}
}再來測試一下：
OK，沒有問題了~！
復雜度分析
時間復雜度：O(N^2)
單趟無論選擇一個還是選擇兩個，都得遍歷一遍，復雜度為O(N),整體還得遍歷一遍O(N)
空間復雜度：O(1)
堆排序
堆排序其實在前面的二叉樹堆那里已經(jīng)介紹并實現(xiàn)過了，這來就等于回顧式的再過一遍~！如果想了解堆這種他是具體咋搞的請點擊：二叉樹的實現(xiàn)
堆排序(Heapsort)是指利用堆，這種數(shù)據(jù)結(jié)構(gòu)所設(shè)計的一種排序算法，它是選擇排序的一種。它是通過堆來進行選擇數(shù)據(jù)進行實現(xiàn)排序的。
他既然是借助堆來實現(xiàn)的那得有堆，即要建堆。這里有兩種建堆的方式：向上調(diào)整建堆+向下調(diào)整排序，向下調(diào)整建堆+向下調(diào)整排序！
他排序是采用刪除的思想，把最大或最小的換到最后，然后對前N-i（i=1，2，3...n)個進行向下調(diào)整！
注意:升序建大堆，降序建小堆
OK，舉個排序的例子：
向上調(diào)整建堆
void HeapSort(HPDataType* a, int n)
{
//向上調(diào)整建堆
//O(N*lgN)
for (int i = 1; i < n; i++)
{
AdjustUp(a, i);
}
//向下調(diào)整排序
//O(N*lgN)
int end = n - 1;
while (end)
{
Swap(&a[0], &a[end]);
AdjustDown(a, end, 0);
--end;
}
}這里的向上調(diào)整建堆和上面堆的插入是一個思路！時間復雜度是O(lgN*N),向下調(diào)整排序的時間復雜度是：O(N*lgN)---->有n個元素，每排好一個一下下標，也就是上面的刪除的思路！
向下調(diào)整建堆
void HeapSort(HPDataType* a, int n)
{
//向下調(diào)整建堆
//O(N)
for (int i = (n - 1) / 2; i >= 0; i--)
{
AdjustDown(a, n, i);
}
//向下調(diào)整排序
//O(N*lgN)
int end = n - 1;
while (end)
{
Swap(&a[0], &a[end]);
AdjustDown(a, end, 0);
--end;
}
}向下調(diào)整建堆，就是從倒數(shù)第一個元素的父節(jié)點開始向下調(diào)整為堆！這樣越往上層節(jié)點的左右子樹必定是堆！
OK，測試一下：
沒問題~！
復雜度分析
時間復雜度：O(N*logN)
向下調(diào)整和向上調(diào)整的時間復雜度都是O(logN)即最多調(diào)整高度次，但向上調(diào)整建堆是O(N*log)而向下調(diào)整建堆的O(N)如下圖~！刪除排序的時間復雜度是O(N*logN)，所以綜合下來就是O(N*logN)
空間復雜度：O(1)
向下調(diào)整建堆時間復雜度推導
向上調(diào)整建堆時間復雜度推導
文章來源：http://www.zghlxwxcb.cn/news/detail-761418.html
OK，本期分享就到這里，好兄弟，下期交換排序不見不散~！文章來源地址http://www.zghlxwxcb.cn/news/detail-761418.html
到了這里，關(guān)于DS八大排序之直接選擇排序和堆排序的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
