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