資訊專欄INFORMATION COLUMN
摘要：當到達時等同于直接插入排序，此時序列已基本有序，所有記錄在統一組內排好成有序序列。當面對大量數據時，希爾排序將比直接插入排序更具優勢圖示講解第一趟取增量，所有間隔為的元素分在一組，在各個組中分別進行直接插入排序。
排序：所謂排序，就是使一串記錄，按照其中的某個或某些關鍵字的大小，遞增或遞減的排列起來的操作。
穩定性：假定在待排序的記錄序列中，存在多個具有相同的關鍵字的記錄，若經過排序，這些記錄的相對次序保持不變，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，則稱這種排序算法是穩定的；否則稱為不穩定的。
內部排序：數據元素全部放在內存中的排序。
外部排序：數據元素太多不能同時放在內存中，根據排序過程的要求不能在內外存之間移動數據的排序。
排序實現的接口：
//打印序列void PrintArray(int* a, int n);//直接插入排序void InsertSort(int* a, int n);//希爾排序void ShellSort(int* a, int n);//選擇排序void SelectSort(int* a, int n);//堆排序void HeapSort(int* a, int n);//冒泡排序void BubbleSort(int* a, int n);//快排void QuickSort(int* a, int left,int right);void QuickSortNonR(int* a, int left, int right);//歸并排序void MergeSort(int* a, int n);void MergeSortNonR(int* a, int n);//計數排序void CountSort(int* a, int n);是一種最簡單的排序，將元素逐個插入到已排好序的有序表中，從而得到一個新的，容量增1的有序表。
將r[i]與r[i-1],r[i-2],…,r[0],從后向前順序比較，在往前比較的過程中同時
后移比自身大的元素。
void InsertSort(int* a, int n){ int i; for (i = 0; i < n - 1; i++) { int end = i; int tmp = a[end + 1]; while (end>=0) { if (a[end] > tmp) { a[end + 1] = a[end];//比待插入元素更大的元素需要后移 end--;//從后往前尋找插入點 } else { break;//找到end后退出循環 } } a[end + 1] = tmp;//在end之后插入 }}
時間復雜度
代碼中的循環次數取決于待插元素與前i-1個元素的大小關系
最好情況，序列原本已為順序，只需遍歷一遍數組，無需移動——O(N)
最壞情況，序列為逆序，每次待插元素需要逐步走向隊頭，那么總的比較次數（移動次數）為一個等差數列的和，最后一個元素需要比較n-1次才能走到隊頭——O(n^2).空間復雜度
只需要一個記錄待插元素的輔助空間tmp，所以空間復雜度為O(1).
穩定性：插入排序是穩定的排序算法，滿足條件r[j] > r[j + 1]才發生交換，這個條件可以保證值相等的元素的相對位置不變
希爾排序是插入排序的一種，又稱縮小增量法。
希爾排序法的基本思想是：先選定一個整數gap，把待排序文件中所有記錄分成n/gap個組，所有距離為gap的記錄分在同一組內，并對每一組內的記錄進行排序。
然后，gap折半，重復上述分組和排序的工作。當到達gap==1時（等同于直接插入排序），此時序列已基本有序，所有記錄在統一組內排好成有序序列。
當面對大量數據時，希爾排序將比直接插入排序更具優勢
- 第一趟取增量gap=5，所有間隔為5的元素分在一組，在各個組中分別進行直接插入排序。
我們可以根據這個特性，先寫出一部分代碼：
for (int i = 0; i < n - gap; i++) { //單個數字 int end = i; int tmp = a[end + gap]; while (end >= 0) { if (a[end] > tmp) { a[end + gap] = a[end]; end -= gap; } else { break; } } a[end + gap] = tmp; }
- 第二趟增量取之前增量的一半，即gap=2，所有間隔為2的元素分在一組，在各個組中直接插入排序。
- 第三趟gap=1，對整個序列進行一趟直接插入排序，由于已基本有序，這次的直接插入排序將會省去不少時間。
void ShellSort(int* a, int n){ int gap = n; while (gap > 1) { gap = gap / 2; //單個gap組 for (int i = 0; i < n - gap; i++) { //單個數字 int end = i; int tmp = a[end + gap]; while (end >= 0) { if (a[end] > tmp) { a[end + gap] = a[end]; end -= gap; } else { break; } } a[end + gap] = tmp; } }}
- 時間復雜度
當gap>1時，元素不是一步步移動，而是跳躍式移動，當進行最后的直接插入排序時，序列以基本有序，只要做少量的比較和移動即可完成排序。希爾排序的時間復雜度取決于gap的選擇，這涉及一些數學上尚未解決的難題。在前人大量的實驗基礎上推出，當序列長度n在特定范圍內，時間復雜度為O(n^1.3),當n->∞時，可減少到O(n*log(n)).- 空間復雜度
只需要一個輔助空間——O(1)
不穩定，相同的值預排時被分到不同的組里
在數組r[0…(n-1)]中，第一趟從r[0]開始，通過n-1次比較在n個元素中找到最小的元素并與r[0]互換。
第二趟從r[1]開始，通過n-2次比較，在n-1個元素中找到最小的元素并于r[1]互換。
依次類推，經過n-1趟，排序完成。
void Swap(int* a, int* b){ int tmp = *a; *a = *b; *b = tmp;}void SelectSort(int* a, int n){ int begin = 0, end = n - 1; while (begin < end) { int mini = begin, maxi = end; for (int i = begin; i <= end; i++) { if (a[i] < a[mini]) { mini = i; } if (a[i] > a[maxi]) { maxi = i; } } //互換函數 Swap(&a[begin], &a[mini]); //begin==maxi時，最大的被換到了mini的位置了，需要對maxi調整 if (begin == maxi) { maxi = mini; } Swap(&a[end], &a[maxi]); begin++; end--; }}
- 時間復雜度
無論初始的序列排列如何，元素之間依然需要通過遍歷去比較大小，確定單個最值的時間復雜度為等差數列之和(n^2/2),同時確定最大和最小值的時間復雜度(n ^2/4)。不管原序列是無序，有序或接近有序，選擇排序的時間復雜度皆為O(n ^2),
空間復雜度
一個輔助空間或兩個輔助空間——O(1)
堆的定義：簡而言之，將數組按層序排成的完全二叉樹，稱之為堆
如果二叉樹的雙親結點大于孩子結點——大根堆
如果二叉樹的雙親結點小于孩子結點——小根堆
之后我們需要進一步調整，將堆調整成為大根堆(小根堆)。大小根堆可保證堆頂為當前數組的
最值
那么我們如何對堆進行調整呢？
- 首先我們需要了解一下堆的性質
如果當前索引值下標為i，
雙親結點的下標parent=(i-1)/2
左孩子結點的小標child1 =2*i+1
右孩子結點的下標child2 =2*i+2
了解這一基本性質后，我們就可以對堆進行調整了。
以建大根堆作為演示
向下調整
從最后一個非葉子結點parent開始，讓其與孩子結點進行比較，如果孩子結點比k大，那么k便往下與孩子結點互換，直到孩子的下標越界，說明該結點調整結束。
然后繼續對上一個非葉子結點的子樹進行向下調整，直到達到整個堆的根結點，堆調整結束。最后一個非葉子結點的下標parent的計算
數組長度為n，那么最后一個葉子結點下標為n-1，其雙親結點就是最后一個非葉子結點，于是parent=(n-1-1)/2
- 單顆子樹根結點向下調整的代碼實現//向下調整void AdjustDown(int *a,int n,int parent)//a-數組，n-數組大小，parent-向下調整的起始位置{ int child = parent * 2 + 1;//完全二叉樹必先有左孩子 while (child < n)//當孩子越界時，說明雙親已達葉子結點，結束當前調整 { if (child + 1 < n && a[child+1]>a[child])//找到兩個孩子中的較大者 { child++; } if (a[child] > a[parent])//如果孩子比雙親大則互換 { Swap(&a[child], &a[parent]); parent = child;//雙親向下繼續調整 child = parent * 2 + 1;//孩子隨著雙親一起改變 } else { break;//雙親已比孩子大亦無必要調整，因為下面的子樹先前已成大根堆 } }}如果我們需要排為
升序，則應建立大根堆。
同樣我們需要排為降序，則應建立小根堆。
由堆的性質，我們只能唯一確定堆頂的是最值，
(1). 將得到的堆頂最值與堆尾元素互換，堆容量-1
(2).堆頂向下調整，選出剩余元素的最大值放置堆頂，
(3). 繼續執行(1)(2)，直到堆容量為1，堆排序完成。
void HeapSort(int* a, int n){ //建堆 升序建大堆 int i = 0; //向下調整建堆 for (i = (n-1-1)/2; i >=0; i--)//i從最后一個非葉子結點走向根結點 { AdjustDown(a, n, i); } //把堆頂與堆尾互換不再理會，堆頂再向下調整 for (i = 0; i < n; i++) { Swap(&a[0], &a[n - i - 1]); AdjustDown(a, n - i - 1, 0); }}綠圈為
已滿足大根堆性質的樹
紫圈為進行向下調整
黃圈為堆頂和堆尾交換過程
紅圈為已排完序的元素
堆排序的時間主要耗費在建初堆和調整堆時進行的反復篩選上。
建初堆的移動步數：
第h-1層，2^(h-2)個結點向下移動1層
…
第3層，2^(2)個結點，向下移動h-3層
第2層，2^(1)個結點，向下移動h-2層
第1層，2^(0)個結點，向下移動h-1層
T(n)=2^(0)* (h-1)+2 ^(1)* (h-2)+…+2^(h-2)1
利用錯位相減法，得到T(n)=n-log2(n+1)≈n
建堆的時間復雜度為O(n)
調整堆需要將堆頂的元素不斷的移向堆尾，則復雜度為元素個數二叉樹高度——O(n*logn)
空間復雜度，只借助了一個輔助空間——O(1)
它重復地走訪過要排序的數列，一次比較兩個元素，如果他們的順序錯誤就把他們交換過來。走訪數列的工作是重復地進行直到沒有再需要交換，也就是說該數列已經排序完成。這個算法的名字由來是因為越小的元素會經由交換慢慢"浮"到數列的頂端。
- 比較相鄰的兩個數，如果第一個數比第二個數大，則兩數交換。對之后的相鄰元素進行同樣的工作，從開始到最后一對，這樣進行一次排序后，數據的最后一位會是最大值，第一次循環進行的次數為 r.length-1。之后對所有的元素重復以上的步驟，且以后每次循環的次數為r.length-1-i（i為循環第幾次 ，i 從零開始）；重復上述步驟，直到排序完成
void BubbleSort(int* a, int n){ //優化 //已經有序 提前結束 for (int j = 0; j < n; j++) { int exchange = 0; for (int i = 1; i < n - j; i++) { if (a[i] < a[i - 1]) { Swap(&a[i], &a[i - 1]); exchange = 1; } } if (exchange == 0)//沒有發生過互換的情況，說明已經有序 { break; } } }時間復雜度
最好的時間復雜度O(n)–有序只需要遍歷一遍
最差的時間復雜度O(n^2)——逆序，等差數列之和
空間復雜度，只借助了一個輔助空間——O(1)
快速排序是由冒泡排序改進而得的。
在冒泡排序的過程中，每次遍歷只對相鄰元素進行比較，每次交換只能消除一個逆序。
如果能通過兩個(不相鄰的)元素的交換消除多個逆序，則會大大加快排序的速度，快速排序的一次交換可以消除多個逆序。
單趟排序*（遞歸 or 迭代）：//邏輯void Partition(){ ...}void QuickSort(int *a,int n){ 迭代 or 遞歸 { Partition()//單趟排序函數 }}重要）a.在序列的n個元素中，選擇一個元素（一般選擇第一個元素）作為
樞軸，將其設為關鍵字keyi，在經歷一次單趟排序后，所有小于keyi的元素交換到前面，把所有大于keyi的元素都交換到后面，單趟排序完成。
b.然后，將待排序的元素以keyi為界，分為左右兩個子表，再分別對左右子表
重復上述步驟。
c.直至每個子表
不含元素或只有一個元素時（控制結束條件），排序完成。
我們有三種方法可以完成單趟排序這一步驟，分別為
Hoare算法，pivot法(挖坑法)和前后指針法。
a.選定下標作為基準值
keyi，一般將keyi定在左端或者右端
b.我們再選定兩個指針left，right分別位于序列的左側和右側。
c.如果keyi定在左側則right先向左邊遍歷，如果keyi定在了右側則left先向右邊遍歷。
d.這里我們假設keyi定在左側，right先開始向左遍歷，直至遇到比a[keyi]小的值則停下。然后left開始向右遍歷，遇到比a[keyi]大的值則停下。然后互換左右下標對應值，Swap(&a[left],&a[right])。
e.然后繼續right先走，left后走，直至left==right時，Swap(&a[keyi],&a[left]),這樣便完成了單趟排序。
這里的
p也就是前文中提到的keyi，不過這里設置在了右端（a[keyi]為6），可以發現left先開始了遍歷，找到了比keyi大的值，a[left]
為8，right隨后找到了比keyi小的值，a[right]為4，兩者調換完后繼續遍歷，直到left撞上right，將left和right共同指向的值9，與a[keyi]互換，完成單趟遍歷。
int Partition1(int* a, int left, int right){ int keyi = left;//將keyi定在左側，則右端先走，反之則左端先走 while (left < right) { //右端先走,對于升序，找到比a[key]小的值則停下 while (right > left && a[right] >= a[keyi])//保證是大于等于號 { right--; } //left找比a[key]大的值停下 while (left < right && a[left] <=a[keyi])//保證是小于等于號 { left++; } Swap(&a[left], &a[right]);//交換左右，比keyi小的放左邊，大的放右邊 } Swap(&a[keyi], &a[left]); return left;}
- 具體思路：
a.以左端作為基準值，將下標記為關鍵字pivot（樞軸），令keyi=a[pivot]。
b.分別用關鍵字left和right記錄左右端下標。
c.right往左遍歷，遇到比keyi小的數字時，將a[right]填入a[pivot]中，
再讓pivot=right(將坑位留在right處)。
d.此時讓left往右遍歷，遇到比keyi大的數字，將a[left]填入a[left]中，
再讓pivot=left（將坑位留在left處）。
e.之后依舊是right先動，left后動，直至left與right重合（此時left==right，right= =pivot）,使a[pivot]=keyi,單趟排序結束。
動圖演示
代碼實現
//單趟排序的第二種方法——挖坑法int Partition2(int* a ,int left, int right){ int keyi=a[left]; int pivot = left; while (left < right) { //key在左端，則從右端開始找 //右邊找小，放到左邊的坑中，自己再成坑 while (left < right && a[right] >= keyi) { right--; } a[pivot] = a[right]; pivot = right; //左邊找大，放到右邊的坑中，自己再成坑 while (left < right && a[left] <= keyi) { left++; } a[pivot] = a[left]; pivot = left; } a[pivot] = keyi; return pivot;}
- 基本原理
a.初始化：選擇一端下標設為基準值keyi，需要兩個指針，一個在前一個在后，分別用cur表示前指針，prev表示后指針(這里的指針的意思是待排序數列的下標)，我們規定cur在prev的后一個位置。prev指向這個數列開始的第一個，cur指向prev的后一個位置。
b.如果cur的值大于基準值a[key]，這時只讓cur++,如果a[cur]小于基準值，這時我們讓prev++后，判斷是否與cur的位置相等，若相等，cur繼續向后遍歷，若不相等，則交換cur和prev的值。c.直到
cur超過序列末尾時，我們再交換prev和基準值，這樣基準值的位置也就確定了。
keyi選在左端，那么cur從left+1開始 走到right，prev從cur-1開始。
cur走到終點時，[left+1,prev]都是比a[keyi]小的數字，[prev+1,right]都比a[keyi]大。
所以a[prev]和a[keyi]互換，使a[keyi]正確落位。
//以左端為keyiint Partition3(int* a, int left, int right){ int keyi = left; int cur = left + 1, prev = left; while (cur <= right) { if (a[cur] < a[keyi] && (++prev)!=cur) { Swap(&a[cur], &a[prev]); } cur++; } Swap(&a[prev], &a[keyi]); return prev;}如果以右端為keyi則有小小的改動
keyi選在右端，那么cur從left開始 走到right-1，prev從cur-1開始。
cur走到終點，[left,prev]都是比a[keyi]小的數字，[prev+1,right-1]都比a[keyi]大。
所以a[keyi]和a[prev+1]互換，以使a[keyi]正確落位。
int Partition4(int* a, int left, int right){ int keyi = right
文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。
轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/125387.html
摘要：本篇博客我要來和大家一起聊一聊數據結構初階中的最后一篇博客八大經典排序算法的總結，其中會介紹他們的原來，還有復雜度的分析以及各種優化。快速排序遞歸版本快速排序是于年提出的一種二叉樹結構的交換排序方法。 ...
閱讀 3735·2023-01-11 11:02
閱讀 4244·2023-01-11 11:02
閱讀 3050·2023-01-11 11:02
閱讀 5180·2023-01-11 11:02
閱讀 4737·2023-01-11 11:02
閱讀 5534·2023-01-11 11:02
閱讀 5313·2023-01-11 11:02
閱讀 3990·2023-01-11 11:02
