直接插入排序(插入排序)

排序思想

• 對于一個數(shù)組 A[0,n] 的排序問題，假設認為數(shù)組在 A[0,n-1] 排序的問題已經(jīng)解決了。
• 考慮 A[n] 的值，從右向左掃描有序數(shù)組 A[0,n-1] ，直到第一個小于等于 A[n] 的元素，將 A[n] 插在這個元素的后面。

插入排序運用時需要注意的

直接插入排序?qū)τ?最壞的情況（嚴格遞減/遞增的數(shù)組），需要比較和移位的次數(shù)為 n(n-1)/2；

對于 最好的情況（嚴格遞增/遞減的數(shù)組），需要比較的次數(shù)是 n-1 ，需要移位的次數(shù)是 0 。

直接插入排序適用于 順序存儲 和 鏈式存儲結構 的線性表。注意，為鏈式存儲時，可以從前往后查找指定元素的位置。一般來說，當 數(shù)據(jù)規(guī)模較小 的情況下，可以考慮使用直接插入排序

插入排序算法分析

直接插入排序的時間復雜度是 O(n^2)，空間復雜度是 O(1)，同時也是 穩(wěn)定排序。

穩(wěn)定排序：待排序的記錄序列中可能存在兩個或兩個以上關鍵字相等的記錄。排序前的序列中Ri領先于Rj（即i<j）.若在排序后的序列中Ri仍然領先于Rj，則稱所用的方法是穩(wěn)定的。

比如int數(shù)組[1,1,1,6,4]中a[0],a[1],a[2]的值相等，在排序時不改變其序列，則稱所用的方法是穩(wěn)定的。

代碼實現(xiàn)

class Solution{ public:void insertSortion(vector<int> &nums) {if(nums.size() < 2) return;for(int i = 1; i < nums.size(); i++) {int num = nums[i];// 防止插入的數(shù)是最小的 bool flag = false;// for循環(huán)中，若插入值是最小的，沒有給最小的值安排位置 for(int j = i - 1; j > -1; j--) {if(nums[j] > num) {nums[j+1] = nums[j];} else {nums[j+1] = num;flag = true;break;}}if(!flag) {nums[0] = num; }}return;} };

加工后執(zhí)行的結果

折半插入排序(插入排序)

排序思想：折半插入排序的改進版

有一組數(shù)列待排序，排序區(qū)間為 Array[0, n-1] 。將數(shù)列分為有序數(shù)列和無序數(shù)列，第一次排序時默認 Array[0] 為有序數(shù)列，Array[1, n-1] 為無序數(shù)列。有序數(shù)列分區(qū)的第一個元素位置為 low ，最后一個元素的位置為 high。

設 Array[0, i-1] 為有序數(shù)列，待插入數(shù)據(jù)為 Array[i]。由于 Array[0, i-1] 有序，使用對有序數(shù)列的查找，最好的方法時時間復雜度為 O(logn) 的折半查找，通過折半查找找到插入位置（即 low > high 時），將該位置及之后的數(shù)據(jù)分別往后挪一位

折半插入排序運用時需要注意的條件和直接插入排序時需注意的條件一樣

折半插入排序?qū)τ?最壞的情況（嚴格遞減/遞增的數(shù)組），需要比較和移位的次數(shù)為 n(n-1)/2 ；

對于 最好的情況（嚴格遞增/遞減的數(shù)組），需要比較的次數(shù)是 n-1 ，需要移位的次數(shù)是 0。

但相比直接插入排序，折半插入排序在 查找位置的時候得到優(yōu)化（O(n)→ O(logn)）

折半排序算法分析

折半插入排序的時間復雜度是 O(n^2)，空間復雜度是O(1)，同時也是 穩(wěn)定排序。

代碼實現(xiàn)

#include <stdio.h> #include <vector> using namespace std; class Solution{ public:void binaryInsertionSort(vector<int> &nums) {if(nums.size() < 2) return;for(int i = 1; i < nums.size(); i++) {int low = 0;int high = i;int num = nums[i];while(low <= high) {int mid = (low + high) / 2;if(nums[mid] > num) {high = mid - 1;} else {low = mid + 1;}}int j;for(j = i - 1; j > high; j--) {nums[j+1] = nums[j];}nums[j+1] = num; }return; } };

加工后執(zhí)行的結果

希爾排序(插入排序)

排序思想：通過粗調(diào)的方式減少了直接插入排序的工作量

對于 Array[0,n-1] 這個數(shù)列有 n 個待排序的數(shù)字，取一個小于 n 的整數(shù) step （step被稱為步長）將待排序元素分成若干個組子序列，所有距離為 step 的倍數(shù)的記錄放在同一個組中；然后，對各組內(nèi)的元素進行直接插入排序。 這一趟排序完成之后，每一個組的元素都是有序的。然后減小 step 的值，并重復執(zhí)行上述的分組和排序。重復這樣的操作，當 step=1 時，整個數(shù)列就是有序的。

希爾排序

希爾排序的時間復雜度與增量(即，步長 step )的選取有關。例如，當增量 step 為1時，希爾排序退化成了直接插入排序，此時的時間復雜度為 O(n2)

遇到極端情況，比如 step=4 和 step=2 時，數(shù)組序列不變，進入 step=1 時，就是直接插入排序了，相比正常的直接插入排序，還多加了幾次 step=4 和 step=2 的判斷

希爾排序僅適用于線性表為順序存儲的情況。

希爾排序算法分析

希爾插入排序的時間復雜度是 O(n^2)，空間復雜度是 O(1) ，但希爾排序是 不穩(wěn)定排序。

代碼實現(xiàn)

class Solution{ public:void ShellSort(vector<int> &nums) {int size = nums.size();int count = 0;for(int step = size / 2; step > 0; step /= 2) {for(int i = 0; i < step; i++) {insertSort(nums, size, i, step);}}} private:void insertSort(vector<int> &nums, int size, int i, int step){for(int j = i + step; j < size; j+=step) {if(nums[j] < nums[j-step]) {int num = nums[j];int k = j - step;while(k >= 0 && nums[k] > num) {nums[k+step] = nums[k];k -= step;}nums[k+step] = num;}}return;} };

加工后執(zhí)行的結果

完整測試代碼

直接插入排序測試代碼

#include <stdio.h> #include <vector> using namespace std; class Solution{ public:void insertSortion(vector<int> &nums) {if(nums.size() < 2) return;printf("第0輪：");for(int i = 0; i < nums.size(); i++) {printf("%d",nums[i]);if(i!=nums.size()-1) printf(",");}printf("\n");for(int i = 1; i < nums.size(); i++) {int num = nums[i];// 防止插入的數(shù)是最小的 bool flag = false;// for循環(huán)中，若插入值是最小的，沒有給最小的值安排位置 for(int j = i - 1; j > -1; j--) {if(nums[j] > num) {nums[j+1] = nums[j];} else {nums[j+1] = num;flag = true;break;}}if(!flag) {nums[0] = num; }// 查看 printf("第%d輪：",i);for(int i = 0; i < nums.size(); i++) {printf("%d",nums[i]);if(i!=nums.size()-1) printf(",");}printf("\n");}return;} };int main() {vector<int> v;v.push_back(23);v.push_back(76);v.push_back(34);v.push_back(89);v.push_back(90);v.push_back(34);v.push_back(56);v.push_back(18);Solution solution;solution.insertSortion(v);return 0; }

折半插入排序測試代碼

#include <stdio.h> #include <vector> using namespace std; class Solution{ public:void binaryInsertionSort(vector<int> &nums) {if(nums.size() < 2) return;printf("第0輪：");for(int i = 0; i < nums.size(); i++) {printf("%d",nums[i]);if(i!=nums.size()-1) printf(",");}printf("\n");for(int i = 1; i < nums.size(); i++) {int low = 0;int high = i;int num = nums[i];while(low <= high) {int mid = (low + high) / 2;if(nums[mid] > num) {high = mid - 1;} else {low = mid + 1;}}int j;for(j = i - 1; j > high; j--) {nums[j+1] = nums[j];}nums[j+1] = num; // 查看 printf("第%d輪：",i);for(int i = 0; i < nums.size(); i++) {printf("%d",nums[i]);if(i!=nums.size()-1) printf(",");}printf("\n");}return; } };int main() {vector<int> v;v.push_back(23);v.push_back(76);v.push_back(34);v.push_back(89);v.push_back(90);v.push_back(34);v.push_back(56);v.push_back(18);Solution solution;solution.binaryInsertionSort(v);return 0; }

希爾排序測試代碼

#include <stdio.h> #include <vector> using namespace std; class Solution{ public:void ShellSort(vector<int> &nums) {int size = nums.size();int count = 0;// 查看 printf("第0輪：");count++;for(int i = 0; i < nums.size(); i++) {printf("%d",nums[i]);if(i!=nums.size()-1) printf(",");}printf("\n");for(int step = size / 2; step > 0; step /= 2) {for(int i = 0; i < step; i++) {insertSort(nums, size, i, step);}// 查看 printf("第%d輪：",count);count++;for(int i = 0; i < nums.size(); i++) {printf("%d",nums[i]);if(i!=nums.size()-1) printf(",");}printf("\n");}} private:void insertSort(vector<int> &nums, int size, int i, int step){for(int j = i + step; j < size; j+=step) {if(nums[j] < nums[j-step]) {int num = nums[j];int k = j - step;while(k >= 0 && nums[k] > num) {nums[k+step] = nums[k];k -= step;}nums[k+step] = num;}}return;} };int main() {vector<int> v;v.push_back(23);v.push_back(76);v.push_back(34);v.push_back(89);v.push_back(90);v.push_back(34);v.push_back(56);v.push_back(18);Solution solution;solution.ShellSort(v);return 0; }

所有的插入排序均不是全局有序（全局排序：即每一輪均有一個數(shù)字的位置不會改變）

總結

以上是生活随笔為你收集整理的【数据结构-排序】1. 图解插入排序三种实现(插入排序/折半排序/希尔排序)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。