目錄
前言：
直接插入排序
直接插入排序代碼實現(xiàn)
直接插入排序特性總結(jié)
希爾排序
希爾排序代碼實現(xiàn)
希爾排序特性總結(jié)
直接選擇排序
直接選擇排序代碼實現(xiàn)
直接選擇排序特性總結(jié)
堆排序
堆的向下調(diào)整算法
建堆
堆排序代碼實現(xiàn)
堆排序特性總結(jié)
前言：
排序即使得一串記錄，按照其中某個或某些關(guān)鍵字的大小，遞增或遞減的排列起來的操作；
排序分為內(nèi)部排序和外部排序，穩(wěn)定排序和非穩(wěn)定排序；
內(nèi)部排序：數(shù)據(jù)元素全部放在內(nèi)存中的排序；
外部排序：數(shù)據(jù)元素太多不能同時存儲于內(nèi)存中，根據(jù)排序過程的要求不能在內(nèi)外存之間移動數(shù)據(jù)的排序；
穩(wěn)定性：假定在待排序的序列中，如果元素a位于元素b前面,且a=b,經(jīng)過某種排序方法進(jìn)行排序之后，元素a依然位于元素b前面，那么這種排序方法就是穩(wěn)定的，否則就是不穩(wěn)定的；
衡量一個排序方法的好壞可以根據(jù)時間復(fù)雜度與空間復(fù)雜度，穩(wěn)定性等綜合考慮；
常見的排序算法：
本篇主要詳細(xì)介紹前四種排序，均以升序為例 ；
直接插入排序
?
直接插入排序的基本思想：
對于一個長度為n的數(shù)組a,當(dāng)插入第 i (i>=1)個元素時，前面的a[0],a[1],......,a[i-1]已經(jīng)有序，此時只需將a[i]元素與a[i-1],a[i-2],.....的元素進(jìn)行比較，找到插入位置先將原來位置上的元素依次向后移動，然后在插入位置插入元素a[i];
?
具體步驟如下：
- 將待排序的序列分為有序區(qū)和無序區(qū)，初始時有序區(qū)只有一個元素，即序列的第一個元素，無序區(qū)包括除第一個元素外的所有元素；
- 從無序區(qū)中取出第一個元素，將其插入到有序區(qū)中的適當(dāng)位置，使之成為新的有序區(qū)；
- 重復(fù)步驟2，直到無序區(qū)中的所有元素都插入到有序區(qū)中；
- 單個數(shù)據(jù)必然有序，所以將元素3劃分為有序區(qū)，其他元素均位于無序區(qū)，假設(shè)有序區(qū)最后一個元素下標(biāo)為end，為防止移動過程中插入元素被覆蓋,用tmp保存插入元素的數(shù)值；
- 尋找插入位置，將tmp與數(shù)組有序區(qū)尾元素a[end]進(jìn)行比較，若a[end]>tmp,先將有序區(qū)尾元素向后移動一位，然后通過控制end即end每次自減1,向左查找下一位，按此循環(huán)，直至a[end]<tmp出現(xiàn)或者end = -1;
- 此時單趟排序已完成，end繼續(xù)回到有序區(qū)的尾元素的位置，進(jìn)行下一趟排序，若a[end]<tmp,直接插入到end的下一位置即a[end+1]=tmp;
?
?
.......
直接插入排序代碼實現(xiàn)
void InsertSort(int* a, int n)
{
//先寫單趟，再寫整體;
for (int i = 0; i <n-1 ; i++)
{
int end = i;
int tmp = a[end + 1];
while (end >= 0)
{
if (tmp < a[end])
{
//向后挪動一位
a[end + 1] = a[end];
end--;
}
else
{
//考慮極端情況，當(dāng)插入的數(shù)值小于有序區(qū)數(shù)組每個元素，不斷向前挪動過程中，直至end=-1;
//出現(xiàn)插入的數(shù)值大于a[end];
break;
}
}
a[end + 1] = tmp;
}
}
直接插入排序特性總結(jié)
1.時間復(fù)雜度
最好情況就是全部有序，此時只需遍歷一次，最好的時間復(fù)雜度為O(n)
最壞情況全部逆序，內(nèi)層每次遍歷已排序部分，最壞時間復(fù)雜度為O(n^2)綜上，因此直接插入排序的平均時間復(fù)雜度為O(n^2)
2. 空間復(fù)雜度
額外開辟的空間為常數(shù)個，所以空間復(fù)雜度為O(1)；
3.算法穩(wěn)定性文章來源：http://www.zghlxwxcb.cn/news/detail-775248.html
穩(wěn)定性指相同元素的前后順序是否改變，當(dāng)插入元素小于a[end]時，插入到比它大的數(shù)前面，所以直接插入排序是穩(wěn)定的；
希爾排序
希爾排序的基本思想：
希爾排序是一種改進(jìn)的插入排序算法，其基本思想是將待排序的序列按照一定的間隔(gap)分成若干個子序列，通過插入排序?qū)Υ箝g隔的子序列進(jìn)行排序，使得整個序列基本有序，然后逐步縮小間隔，重復(fù)上述操作，直到間隔gap為1，最后對整個序列進(jìn)行直接插入排序；每次排序讓數(shù)組接近有序的過程叫做預(yù)排序，最后一次排序為直接插入排序；
1.? 取間隔gap=3對下述序列進(jìn)行分組，該序列被分成3組，每組之間都是以3的等差數(shù)列；
2. 對每一組進(jìn)行插入排序，得到如下數(shù)組
3.縮小間隔，取間隔gap=2對數(shù)組進(jìn)行分組，數(shù)組被分成2份，每組之間都是2的等差數(shù)列;
4. 對每一組進(jìn)行插入排序，得到如下數(shù)組
5.縮小間隔，取間隔gap=1對數(shù)組進(jìn)行分組，數(shù)組相當(dāng)于沒有分組，進(jìn)行插入排序，當(dāng)gap=1時為直接插入排序；
- 如何選擇希爾增量gap?
最初Shell提出的增量是 gap = [n / 2]，每一次排序完讓增量減少一半gap =[ gap / 2]，直到gap = 1時排序變成了直接插入排序；后來Knuth提出的gap = [gap / 3] + 1，每次排序讓增量成為原來的三分之一，加一是防止gap <= 3時gap = [gap / 3] = 0的發(fā)生，導(dǎo)致希爾增量最后不為1，無法完成插入排序；
上述無論哪一種主張都沒有得到證明，本文代碼實現(xiàn)部分采取gap=[n/2],gap=[gap/2]；
希爾排序代碼實現(xiàn)
- 長度為n的數(shù)組間距為gap分為一組，共計gap組，定義遍歷變量i，首先遍歷第一組數(shù)據(jù)，i從0開始遍歷，i每次移動gap步，由于數(shù)組尾元素下標(biāo)為n-1，則i+gap=n-1,為防止數(shù)組越界訪問，i最后訪問位置為 n-1-gap ;
......
第一組排序代碼如下：
for (int i = 0; i < n - gap; i += gap)
{
int end = i;
int tmp = a[end + gap];
while (end >= 0)
{
if (tmp < a[end])
{
a[end + gap] = a[end];
end -= gap;
}
else
{
break;
}
}
a[end + gap] = tmp;
}
- 第一組排序完成，外面套一層循環(huán)，遍歷其余組，便可完成第一趟排序，定義循環(huán)變量j，j從0開始，每次自增1，一共有g(shù)ap組，j小于gap即可排序其他組；
for (int j = 0; j < gap; j++)
{
for (int i = j; i < n - gap; i += gap)
{
int end = i;
int tmp = a[end + gap];
while (end >= 0)
{
if (tmp < a[end])
{
a[end + gap] = a[end];
end -= gap;
}
else
{
break;
}
}
a[end + gap] = tmp;
}
- 然后縮小增量
gap = gap /2 直到gap = 1，繼續(xù)插入排序，直到排序完成；
void ShellSort(int* arr, int n)
{
int gap = n;
//預(yù)排序:分組排序,間距為gap分為一組,共計gap組;
//最后進(jìn)行直接插入排序，即gap==1;
while (gap > 1)
{
gap = gap / 2;
//其次排序其余gap組,一次預(yù)排序完成,會進(jìn)行多次預(yù)排序;
for (int j = 0; j < gap; j++)
{
//首先排序以第一個元素為起點,間距為gap的第一組;相當(dāng)于整個數(shù)組排序;
for (int i = j; i < n - gap; i += gap)
{
//保證[0,end]有序,每個元素間隔為gap,控制[0,end+gap]有序;
int end = i;
int tmp = arr[end + gap];
while (end >= 0)
{
if (tmp < arr[end])
{
arr[end + gap] = arr[end];
end = end - gap;
}
//else會出現(xiàn)倆種情況;
//第一種為第一個元素以后且間距為gap的某個位置插入;
//第二種會不斷滿足tmp<arr[end],直至end=-gap;
else
{
break;
}
//end=-gap的位置，直接將arr[end+gap]=tmp;
arr[end + gap] = tmp;
}
}
}
}
}希爾排序特性總結(jié)
1.時間復(fù)雜度
希爾排序的時間復(fù)雜度取決于增量序列的選擇，由于gap取值有多種方法，導(dǎo)致希爾排序的時間復(fù)雜度并不固定，一般來說，希爾排序的平均時間復(fù)雜度界于 O(n)到 O(n^2)之間， 最好的時間復(fù)雜度為 O(n^1.3)；
2. 空間復(fù)雜度
希爾排序的空間復(fù)雜度為O(1)，因為在希爾排序時是對原數(shù)組進(jìn)行直接排序，并沒有創(chuàng)建其他新的數(shù)組；
3.算法穩(wěn)定性
希爾排序是一種非穩(wěn)定的排序算法；希爾排序的精髓在于按照某個增量來劃分子序列，實現(xiàn)跳躍式移動來提高排序效率，而也正是這種跳躍性帶來了不穩(wěn)定性。如果不同子序列中有相等的數(shù)，但它們不在同一子序列中，可能會因為子序列內(nèi)部排序而改變原有的順序。
直接選擇排序
直接選擇排序的基本思想：
每一次從待排序的數(shù)據(jù)元素中選出最小（或最大）的一個元素，通過交換存放在序列的起始位置（或最后一個位置），直到全部待排序的數(shù)據(jù)元素排完；
具體來說，就是在待排序序列中，首先找到最小的元素和最大的元素，然后將最小的元素與序列的第一個元素交換位置，最大的元素與序列的最后一個元素交換位置，接著在剩下的元素中找到最小的元素與最大的元素，將最小元素與序列的第二個元素交換位置，最大元素與序列的倒數(shù)第二個元素交換位置，以此類推，直到序列中只剩一個元素為止；
具體步驟如下：
- ? 遍歷整個序列，找到最小的元素與最大的元素；
- ? 將最小的元素與序列的第一個元素交換位置，最大的元素與序列尾元素交換位置；
- ? 序列遍歷范圍從第二個元素開始到倒數(shù)第二個元素，遍歷序列，找到剩余元素中的最?? 小元素與最大元素；
- ? 將最小的元素與序列的第二個元素交換位置，最大的元素與序列倒數(shù)第二個元素交換位置；
- ? 重復(fù)上述步驟，直到整個列表都被排序；
?1. 定義變量begin，end，確定遍歷范圍[begin,end] ；定義maxi,mini記錄遍歷范圍內(nèi)的最大值下標(biāo)? 和最小值下標(biāo)，最初maxi ，mini 指向遍歷范圍內(nèi)的首元素，當(dāng)在遍歷范圍內(nèi)查找到最大值，最小值時更新maxi,mini ；
2. 遍歷結(jié)束后查找到最大值，最小值，此時將最小的元素與遍歷范圍內(nèi)的第一個元素交換位置，最大的元素與遍歷范圍內(nèi)的尾元素交換位置；
3.交換完成后，begin自增1，end自減1，確定新的遍歷范圍，同時maxi ，mini 指向遍歷范圍內(nèi)的首元素，當(dāng)在遍歷范圍內(nèi)查找到最大值，最小值時更新maxi,mini ；
4. 交換時先將遍歷范圍內(nèi)的最小值與遍歷范圍的首元素交換，其次將遍歷范圍內(nèi)的最大值與遍歷范圍內(nèi)的尾元素交換；
當(dāng)出現(xiàn)上述情況即出現(xiàn) 最大的位置恰好位于begin位置，說明mini是和最大的交換位置，這個時候max的位置就發(fā)生了變換， maxi變到了mini的位置，需要 更新max的位置，否則易導(dǎo)致錯誤,正確做法如下圖所示
?
......
直接選擇排序代碼實現(xiàn)
//交換
void swap(int* p, int* q)
{
int tmp = *p;
*p = *q;
*q = tmp;
}
//選擇排序
void SelectSort(int* arr, int n)
{
int begin = 0;
int end = n - 1;
while (begin < end)
{
//單趟排序,將[begin,end]范圍內(nèi)最大與最小的數(shù)據(jù)調(diào)整于左右;
int maxi = begin;//最大元素的下標(biāo),假設(shè)最大元素在最左邊;
int mini = begin;//最小元素的下標(biāo),假設(shè)最小元素在最左邊;
for (int i = begin+1; i <=end; i++)
{
if (arr[i]>arr[maxi])
{
maxi = i;
}
if (arr[i]<arr[mini])
{
mini = i;
}
}
swap(&arr[begin], &arr[mini]);
//如果最大元素的位置位于begin位置，說明mini和最大的交換位置;
//maxi的位置變化到mini的位置，要更新maxi;
if (maxi == begin)
{
maxi = mini;
}
swap(&arr[end], &arr[maxi]);
end--;
begin++;
}
}直接選擇排序特性總結(jié)
1.時間復(fù)雜度
數(shù)據(jù)的比較次數(shù)為（n-1）+（n-2）+（n-3）+......1 = n*(n-1)/2，數(shù)據(jù)的交換次數(shù)為n-1，所以 時間復(fù)雜度為O(n^2)；
2. 空間復(fù)雜度
選擇排序的空間復(fù)雜度為O(1)，因為在選擇排序時是對原數(shù)組進(jìn)行直接排序，并沒有創(chuàng)建其他新的數(shù)組；
3.算法穩(wěn)定性
選擇排序是一種非穩(wěn)定的排序算法，具體參見上圖紅五與白五排序前后的位置；
堆排序
大根堆：任意父節(jié)點的數(shù)值大于等于孩子節(jié)點的數(shù)值（a[i] >= a[2i+1] && a[i] >= a[2i+2])；
對堆中的結(jié)點按層進(jìn)行編號，映射到數(shù)組便可得其存儲結(jié)構(gòu)
小根堆：任意父節(jié)點的數(shù)值小于等于孩子節(jié)點的數(shù)值（a[i] <= a[2i+1] && a[i] <= a[2i+2])；
對堆中的結(jié)點按層進(jìn)行編號，映射到數(shù)組便可得其存儲結(jié)構(gòu)
結(jié)論： 大堆堆頂數(shù)據(jù)的數(shù)值最大； 小堆堆頂數(shù)據(jù)數(shù)值最小
堆排序是利用大堆或者小堆堆頂數(shù)據(jù)最大或最小的特性來進(jìn)行排序的，所以，我們排序的對象必須是大堆或者小堆，但給定的數(shù)據(jù)不一定是大堆或者小堆，所以必須先建堆；
堆的向下調(diào)整算法
建堆的核心為堆的向下調(diào)整算法，堆的向下調(diào)整算法的基本思想：
從根結(jié)點開始，利用假設(shè)法尋找同一高度處值最小的孩子，根據(jù)其左右子樹為小堆還是大堆，按照小堆或大堆的原則將其交換，若為小堆，父節(jié)點處的數(shù)值大于孩子結(jié)點出的數(shù)值，則交換彼此位置；若為大堆，父節(jié)點處的數(shù)值小于孩子結(jié)點出的數(shù)值，則交換彼此位置；直至葉節(jié)點為止或出現(xiàn)滿足其邏輯上不滿足大小堆的數(shù)值為止；
//堆的向下調(diào)整算法(建大堆)
void AdjustDown(int* nums, int n, int parent)
{
//假設(shè)法求同一深度左右孩子最小的一個,假設(shè)左孩子為最小
int child = parent * 2 + 1;
while (child<n)
{
if (child + 1 < n && nums[child] < nums[child + 1])
{
child++;
}
//無論左右孩子,child為最大,調(diào)整為大堆;
if (nums[child] > nums[parent])
{
swap(&nums[child], &nums[parent]);
parent = child;
child = 2 * parent + 1;
}
else
{
break;
}
}
}建堆
由于向下調(diào)整算法的使用前提是左右子樹必須是大堆或者小堆，從倒數(shù)第一個非葉子結(jié)點開始調(diào)整，一定能夠保證待排序序列的左右子樹都是大堆或者小堆，此時即可看作大堆又可以看作小堆，根據(jù)需要進(jìn)行調(diào)整即可；
倒數(shù)第一個非葉子結(jié)點恰好是最后一個結(jié)點的父親，最后一個結(jié)點的下標(biāo)為n-1，套用公式：parent=(child-1)/2，則該結(jié)點下標(biāo)為:（n-1-1) / 2；
//建堆 升序建大堆，降序建小堆
for (int i = (n - 1 - 1) / 2; i >= 0; i--)
{
AdjustDown(arr, n, i);
}
?詳細(xì)圖解可參考：數(shù)據(jù)結(jié)構(gòu)之堆-CSDN博客
堆排序的基本思想：
- 將待排序序列構(gòu)造成一個大根堆；
- 整個序列的最大值就是堆頂?shù)母?jié)點；
- 將堆頂元素與數(shù)組尾元素進(jìn)行交換，此時數(shù)組尾元素就為最大值；
- 將數(shù)組尾元素不看做堆里面的數(shù)據(jù)，前n-1個數(shù)繼續(xù)向下調(diào)整為堆，選出次大的數(shù)，和倒數(shù)第二個位置的數(shù)交換；反復(fù)執(zhí)行，得到升序序列；
堆排序代碼實現(xiàn)
void HeapSort(int* arr, int n)
{
//建堆
for (int i = (n - 1 - 1) / 2; i >= 0; i--)
{
AdjustDown(arr, n, i);
}
//排序
int end = n - 1;
while (end > 0)
{
swap(&arr[0], &arr[end]);
AdjustDown(arr, end, 0);
end--;
}
}
堆排序特性總結(jié)
1.時間復(fù)雜度
堆向下調(diào)整算法的時間復(fù)雜度為O(logn)，堆排序由建堆與排序倆部分組成，建堆的時間復(fù)雜度O(n) ;? 假設(shè)節(jié)點數(shù)為n，需要進(jìn)行n-1次交換，每次調(diào)整的時間復(fù)雜度O(logn)，總的時間復(fù)雜度為(n-1)*O(logn)，所以 堆排序的時間復(fù)雜度為 O(n)+O(n*logn)=O(n*logn)；
2. 空間復(fù)雜度
堆排序的空間復(fù)雜度為O(1)，因為在堆排序時是對原數(shù)組進(jìn)行直接排序，并沒有創(chuàng)建其他新的數(shù)組；
3.算法穩(wěn)定性
堆排序是一種非穩(wěn)定的排序算法，堆排序時需要交換堆頂和堆尾的數(shù)據(jù)，交換時兩個相等的數(shù)據(jù)在序列中的相對位置就可能發(fā)生改變，所以堆排序不是一個穩(wěn)定排序；文章來源地址http://www.zghlxwxcb.cn/news/detail-775248.html
到了這里，關(guān)于【數(shù)據(jù)結(jié)構(gòu)】八大排序（一）的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
