電子發(fā)燒友App
?
以前也零零碎碎發(fā)過一些排序算法，但排版都不太好，又重新整理一次，排序算法是數(shù)據(jù)結(jié)構(gòu)的重要部分，系統(tǒng)地學習很有必要。 ?排序算法平均時間復雜度最差時間復雜度空間復雜度數(shù)據(jù)對象穩(wěn)定性| ? | ? | ? | ? | ? |
| 冒泡排序 | O(n2) | O(n2) | O(1) | 穩(wěn)定 |
| 選擇排序 | O(n2) | O(n2) | O(1) | 數(shù)組不穩(wěn)定、鏈表穩(wěn)定 |
| 插入排序 | O(n2) | O(n2) | O(1) | 穩(wěn)定 |
| 快速排序 | O(n*log2n) | O(n2) | O(log2n) | 不穩(wěn)定 |
| 堆排序 | O(n*log2n) | O(n*log2n) | O(1) | 不穩(wěn)定 |
| 歸并排序 | O(n*log2n) | O(n*log2n) | O(n) | 穩(wěn)定 |
| 希爾排序 | O(n*log2n) | O(n2) | O(1) | 不穩(wěn)定 |
| 計數(shù)排序 | O(n+m) | O(n+m) | O(n+m) | 穩(wěn)定 |
| 桶排序 | O(n) | O(n) | O(m) | 穩(wěn)定 |
| 基數(shù)排序 | O(k*n) | O(n2) | ? | 穩(wěn)定 |
1 冒泡排序
算法思想：- 比較相鄰的元素。如果第一個比第二個大，就交換他們兩個。
- 對每一對相鄰元素作同樣的工作，從開始第一對到結(jié)尾的最后一對。這步做完后，最后的元素會是最大的數(shù)。
- 針對所有的元素重復以上的步驟，除了最后一個。
- 持續(xù)每次對越來越少的元素重復上面的步驟，直到?jīng)]有任何一對數(shù)字需要比較。
代碼：
void bubbleSort(int a[], int n) { for(int i =0 ; i< n-1; ++i) { for(int j = 0; j < n-i-1; ++j) { if(a[j] > a[j+1]) { int tmp = a[j] ; //交換 a[j] = a[j+1] ; a[j+1] = tmp; } } } }
2 選擇排序
算法思想：- 在未排序序列中找到最?。ù螅┰?，存放到排序序列的起始位置
- 從剩余未排序元素中繼續(xù)尋找最?。ù螅┰?，然后放到已排序序列的末尾
- 以此類推，直到所有元素均排序完畢
選擇排序動圖演示代碼：
function selectionSort(arr) { var len = arr.length; var minIndex, temp; for (var i = 0; i < len - 1; i++) { minIndex = i; for (var j = i + 1; j < len; j++) { if (arr[j] < arr[minIndex]) { // 尋找最小的數(shù) minIndex = j; // 將最小數(shù)的索引保存 } } temp = arr[i]; arr[i] = arr[minIndex]; arr[minIndex] = temp; } return arr; }
3 插入排序
算法思想：- 從第一個元素開始，該元素可以認為已經(jīng)被排序
- 取出下一個元素，在已經(jīng)排序的元素序列中從后向前掃描
- 如果該元素（已排序）大于新元素，將該元素移到下一位置
- 重復步驟3，直到找到已排序的元素小于或者等于新元素的位置
- 將新元素插入到該位置后
- 重復步驟2~5
插入排序動圖演示代碼：
void print(int a[], int n ,int i){ cout<
4 快速排序
算法思想：- 選取第一個數(shù)為基準
- 將比基準小的數(shù)交換到前面，比基準大的數(shù)交換到后面
- 對左右區(qū)間重復第二步，直到各區(qū)間只有一個數(shù)
代碼：
void QuickSort(vector
5 堆排序
堆排序（Heapsort）是指利用堆這種數(shù)據(jù)結(jié)構(gòu)所設(shè)計的一種排序算法。堆積是一個近似完全二叉樹的結(jié)構(gòu)，并同時滿足堆積的性質(zhì)：即子結(jié)點的鍵值或索引總是小于（或者大于）它的父節(jié)點。算法思想：- 將初始待排序關(guān)鍵字序列(R1,R2….Rn)構(gòu)建成大頂堆，此堆為初始的無序區(qū)；
- 將堆頂元素R[1]與最后一個元素R[n]交換，此時得到新的無序區(qū)(R1,R2,……Rn-1)和新的有序區(qū)(Rn),且滿足R[1,2…n-1]<=R[n]；
- 由于交換后新的堆頂R[1]可能違反堆的性質(zhì)，因此需要對當前無序區(qū)(R1,R2,……Rn-1)調(diào)整為新堆，然后再次將R[1]與無序區(qū)最后一個元素交換，得到新的無序區(qū)(R1,R2….Rn-2)和新的有序區(qū)(Rn-1,Rn)。不斷重復此過程直到有序區(qū)的元素個數(shù)為n-1，則整個排序過程完成。
代碼：
#include
6 歸并排序
歸并排序是建立在歸并操作上的一種有效的排序算法。該算法是采用分治法（Divide and Conquer）的一個非常典型的應用。將已有序的子序列合并，得到完全有序的序列；即先使每個子序列有序，再使子序列段間有序。若將兩個有序表合并成一個有序表，稱為2-路歸并。算法思想：1.把長度為n的輸入序列分成兩個長度為n/2的子序列；2. 對這兩個子序列分別采用歸并排序；3. 將兩個排序好的子序列合并成一個最終的排序序列。
歸并排序動圖演示代碼：
void print(int a[], int n){ for(int j= 0; j
7 希爾排序
希爾排序，也稱遞減增量排序算法，是插入排序的一種更高效的改進版本。但希爾排序是非穩(wěn)定排序算法。先將整個待排序的記錄序列分割成為若干子序列分別進行直接插入排序.算法思想：- 選擇一個增量序列t1，t2，…，tk，其中ti>tj，tk=1；
- 按增量序列個數(shù)k，對序列進行k 趟排序；
- 每趟排序，根據(jù)對應的增量ti，將待排序列分割成若干長度為m 的子序列，分別對各子表進行直接插入排序。僅增量因子為1 時，整個序列作為一個表來處理，表長度即為整個序列的長度。
希爾排序動圖演示代碼：
void shell_sort(T array[], int length) { int h = 1; while (h < length / 3) { h = 3 * h + 1; } while (h >= 1) { for (int i = h; i < length; i++) { for (int j = i; j >= h && array[j] < array[j - h]; j -= h) { std::swap(array[j], array[j - h]); } } h = h / 3; } }
8 計數(shù)排序
計數(shù)排序統(tǒng)計小于等于該元素值的元素的個數(shù)i，于是該元素就放在目標數(shù)組的索引i位（i≥0）。- 計數(shù)排序基于一個假設(shè)，待排序數(shù)列的所有數(shù)均為整數(shù)，且出現(xiàn)在（0，k）的區(qū)間之內(nèi)。
- 如果 k（待排數(shù)組的最大值） 過大則會引起較大的空間復雜度，一般是用來排序 0 到 100 之間的數(shù)字的最好的算法，但是它不適合按字母順序排序人名。
- 計數(shù)排序不是比較排序，排序的速度快于任何比較排序算法。
- 找出待排序的數(shù)組中最大和最小的元素；
- 統(tǒng)計數(shù)組中每個值為 i 的元素出現(xiàn)的次數(shù)，存入數(shù)組 C 的第 i 項；
- 對所有的計數(shù)累加（從 C 中的第一個元素開始，每一項和前一項相加）；
- 向填充目標數(shù)組：將每個元素 i 放在新數(shù)組的第 C[i] 項，每放一個元素就將 C[i] 減去 1；
計數(shù)排序動圖演示代碼：
#include
9 桶排序
將值為i的元素放入i號桶，最后依次把桶里的元素倒出來。算法思想：- 設(shè)置一個定量的數(shù)組當作空桶子。
- 尋訪序列，并且把項目一個一個放到對應的桶子去。
- 對每個不是空的桶子進行排序。
- 從不是空的桶子里把項目再放回原來的序列中。
桶排序動圖演示代碼：
function bucketSort(arr, bucketSize) { if (arr.length === 0) { return arr; } var i; var minValue = arr[0]; var maxValue = arr[0]; for (i = 1; i < arr.length; i++) { if (arr[i] < minValue) { minValue = arr[i]; // 輸入數(shù)據(jù)的最小值 } else if (arr[i] > maxValue) { maxValue = arr[i]; // 輸入數(shù)據(jù)的最大值 } } // 桶的初始化 var DEFAULT_BUCKET_SIZE = 5; // 設(shè)置桶的默認數(shù)量為5 bucketSize = bucketSize || DEFAULT_BUCKET_SIZE; var bucketCount = Math.floor((maxValue - minValue) / bucketSize) + 1; var buckets = new Array(bucketCount); for (i = 0; i < buckets.length; i++) { buckets[i] = []; } // 利用映射函數(shù)將數(shù)據(jù)分配到各個桶中 for (i = 0; i < arr.length; i++) { buckets[Math.floor((arr[i] - minValue) / bucketSize)].push(arr[i]); } arr.length = 0; for (i = 0; i < buckets.length; i++) { insertionSort(buckets[i]); // 對每個桶進行排序，這里使用了插入排序 for (var j = 0; j < buckets[i].length; j++) { arr.push(buckets[i][j]); } } return arr; }
10 基數(shù)排序
一種多關(guān)鍵字的排序算法，可用桶排序?qū)崿F(xiàn)。算法思想：- 取得數(shù)組中的最大數(shù)，并取得位數(shù)；
- arr為原始數(shù)組，從最低位開始取每個位組成radix數(shù)組；
- 對radix進行計數(shù)排序（利用計數(shù)排序適用于小范圍數(shù)的特點）
基數(shù)排序動圖演示代碼：
int maxbit(int data[], int n) //輔助函數(shù)，求數(shù)據(jù)的最大位數(shù) { int maxData = data[0];///< 最大數(shù) /// 先求出最大數(shù)，再求其位數(shù)，這樣有原先依次每個數(shù)判斷其位數(shù)，稍微優(yōu)化點。 for (int i = 1; i < n; ++i) { if (maxData < data[i]) maxData = data[i]; } int d = 1; int p = 10; while (maxData >= p) { //p *= 10; // Maybe overflow maxData /= 10; ++d; } return d; /* int d = 1; //保存最大的位數(shù) int p = 10; for(int i = 0; i < n; ++i) { while(data[i] >= p) { p *= 10; ++d; } } return d;*/ } void radixsort(int data[], int n) //基數(shù)排序 { int d = maxbit(data, n); int *tmp = new int[n]; int *count = new int[10]; //計數(shù)器 int i, j, k; int radix = 1; for(i = 1; i <= d; i++) //進行d次排序 { for(j = 0; j < 10; j++) count[j] = 0; //每次分配前清空計數(shù)器 for(j = 0; j < n; j++) { k = (data[j] / radix) % 10; //統(tǒng)計每個桶中的記錄數(shù) count[k]++; } for(j = 1; j < 10; j++) count[j] = count[j - 1] + count[j]; //將tmp中的位置依次分配給每個桶 for(j = n - 1; j >= 0; j--) //將所有桶中記錄依次收集到tmp中 { k = (data[j] / radix) % 10; tmp[count[k] - 1] = data[j]; count[k]--; } for(j = 0; j < n; j++) //將臨時數(shù)組的內(nèi)容復制到data中 data[j] = tmp[j]; radix = radix * 10; } delete []tmp; delete []count; } 2020 GitHub, Inc.
?
?
審核編輯：湯梓紅
?
工商網(wǎng)監(jiān)
評論