復(fù)習(xí)梗概

文章目錄

• • 復(fù)習(xí)梗概
  • 插入排序算法思想
  • 插入排序時間復(fù)雜度與特性（多少，與什么有關(guān)？）
  • 插入排序基礎(chǔ)版
  • 插入排序2nd優(yōu)化版（優(yōu)化了哪里？）
  • ！！！插入排序二分搜索優(yōu)化版（優(yōu)化了哪里？如何優(yōu)化？優(yōu)化后的二分搜索判定條件？）
  • • 關(guān)鍵在于理解新的二分搜索，搜索合適的插入位置如何實現(xiàn)
  • 完整代碼

插入排序算法思想

想象插入排序就是兩只手，一只手里的牌是有序的，一只是無序的，每次把無序的手里的牌的第一張，與有序的牌逐個比較，插入有序牌堆的合適位置

---

插入排序時間復(fù)雜度與特性（多少，與什么有關(guān)？）

插入排序的時間復(fù)雜度： 與數(shù)組中的逆序?qū)τ嘘P(guān)

逆序?qū)?#xff1a;比如想要遞增的數(shù)組【0，8，9，1】這里【8，1】【9，1】都是逆序?qū)?/li>

最壞時間復(fù)雜度：O（n2）（輸入數(shù)組完全逆序），最好時間復(fù)雜度O（n）（輸入數(shù)組已經(jīng)有序），平均時間復(fù)雜度O（n2），空間復(fù)雜度O（1）

即使應(yīng)用了二分搜索優(yōu)化，時間復(fù)雜度還是O（n2），因為避不開要挪元素騰位置插入

屬于原地穩(wěn)定排序算法

排序算法在逆序?qū)μ貏e少的數(shù)組中效率很高，甚至可能比O（nlogn）級別的堆排序和快速排序還快

---

插入排序基礎(chǔ)版

void insertionSort1th(vector<int> &array) //這里以數(shù)組左側(cè)作為有序的那一邊 {// chaosBeginIndex：未排序序列的起始元素下標(biāo)// insertEIndex：拿去插入有序序列的那個元素的下標(biāo)，就是未排序序列的起始元素，但隨著交換位置，下標(biāo)會改變for (int chaosBeginIndex = 1; chaosBeginIndex < array.size(); chaosBeginIndex++) //外循環(huán)控制從第二個元素開始插入到有序序列里，直到最后一個元素{for (int insertEIndex = chaosBeginIndex; insertEIndex > 0; insertEIndex--)//內(nèi)循環(huán)控制從未排序序列的首元素開始，逐漸與有序序列元素比較和交換位置，找到有序序列中的合適位置{if (array[insertEIndex] < array[insertEIndex - 1]){int temp = array[insertEIndex];array[insertEIndex] = array[insertEIndex - 1];array[insertEIndex - 1] = temp;}else{break;}}vectorPrint(array);} }void insertionSort1thRe(vector<int> &array) //這里以數(shù)組右側(cè)作為有序的那一邊 {for (int chaosBeginIndex = array.size() - 1 - 1; chaosBeginIndex >= 0; chaosBeginIndex--){for (int insertEIndex = chaosBeginIndex; insertEIndex < array.size() - 1; insertEIndex++){if (array[insertEIndex] > array[insertEIndex + 1]){int temp = array[insertEIndex];array[insertEIndex] = array[insertEIndex + 1];array[insertEIndex + 1] = temp;}else{break;}}vectorPrint(array);} } 輸入數(shù)組： 6 9 3 1 2 0 8 29 15 11 10 插入排序基礎(chǔ)版 6 9 3 1 2 0 8 29 15 11 10 3 6 9 1 2 0 8 29 15 11 10 1 3 6 9 2 0 8 29 15 11 10 1 2 3 6 9 0 8 29 15 11 10 0 1 2 3 6 9 8 29 15 11 10 0 1 2 3 6 8 9 29 15 11 10 0 1 2 3 6 8 9 29 15 11 10 0 1 2 3 6 8 9 15 29 11 10 0 1 2 3 6 8 9 11 15 29 10 0 1 2 3 6 8 9 10 11 15 29 算法用時：（微秒） [AlgoTime: 10002 us] 輸入數(shù)組： 6 9 3 1 2 0 8 29 15 11 10 插入排序基礎(chǔ)版（換一個方向） 6 9 3 1 2 0 8 29 15 10 11 6 9 3 1 2 0 8 29 10 11 15 6 9 3 1 2 0 8 10 11 15 29 6 9 3 1 2 0 8 10 11 15 29 6 9 3 1 2 0 8 10 11 15 29 6 9 3 1 0 2 8 10 11 15 29 6 9 3 0 1 2 8 10 11 15 29 6 9 0 1 2 3 8 10 11 15 29 6 0 1 2 3 8 9 10 11 15 29 0 1 2 3 6 8 9 10 11 15 29 算法用時：（微秒） [AlgoTime: 10003 us]

---

插入排序2nd優(yōu)化版（優(yōu)化了哪里？）

思路是將交換改為了挪動

就是把左邊比我大的元素都要跟我交換，換成了左邊比我大的元素都要往右移

流程圖來自騰訊課堂-戀上數(shù)據(jù)結(jié)構(gòu)與算法第二季-李明杰老師

//插入排序的第一次優(yōu)化，就是把不斷的交換位置，改成了找到位置后插入數(shù)組，數(shù)組元素后移覆蓋 //就是把左邊比我大的元素都要跟我交換，換成了左邊比我大的元素都要往右移 void insertionSort2nd(vector<int> &array) //這里以數(shù)組左側(cè)作為有序的那一邊 {for (int chaosBeginIndex = 1; chaosBeginIndex < array.size(); chaosBeginIndex++){int insertENum = array[chaosBeginIndex]; //記錄插入元素的元素內(nèi)容，因為后面原本位置會被覆蓋int rightEIndex = chaosBeginIndex; //記錄正確的插入位置，初始值就是被插入元素的原本位置（未排序序列的第一個元素位置）while (rightEIndex > 0) //不斷比較插入元素與有序隊列元素，找到合適插入位置，用rightEIndex記錄{if (insertENum< array[rightEIndex-1]){array[rightEIndex] = array[rightEIndex - 1];//妙啊，找合適位置的同時就順便把元素后移了rightEIndex = rightEIndex - 1;}else{break;}}array[rightEIndex] = insertENum; //插入到空出來的合適位置中vectorPrint(array);} } 輸入數(shù)組： 6 9 3 1 2 0 8 29 15 11 10 插入排序第一次優(yōu)化版 6 9 3 1 2 0 8 29 15 11 10 3 6 9 1 2 0 8 29 15 11 10 1 3 6 9 2 0 8 29 15 11 10 1 2 3 6 9 0 8 29 15 11 10 0 1 2 3 6 9 8 29 15 11 10 0 1 2 3 6 8 9 29 15 11 10 0 1 2 3 6 8 9 29 15 11 10 0 1 2 3 6 8 9 15 29 11 10 0 1 2 3 6 8 9 11 15 29 10 0 1 2 3 6 8 9 10 11 15 29 算法用時：（微秒） [AlgoTime: 11002 us]

---

！！！插入排序二分搜索優(yōu)化版（優(yōu)化了哪里？如何優(yōu)化？優(yōu)化后的二分搜索判定條件？）

關(guān)鍵在于理解新的二分搜索，搜索合適的插入位置如何實現(xiàn)

流程圖來自騰訊網(wǎng)課戀上數(shù)據(jù)結(jié)構(gòu)與算法第二季，李明杰老師

//整體思想是利用二分搜索的框架，修改結(jié)束條件，從找到或找不到某元素，變?yōu)閷ふ覕?shù)組中第一個大于插入元素的元素 //具體修改: 插入元素小于mid，更新搜尋范圍向左，插入元素大于等于mid，更新搜尋范圍向右，直到begin=end說明找到插入位置 int binarySearchInsertionIndex(vector<int> array, int chaosBeginIndex) {int begin = 0;int end = chaosBeginIndex;//!我們知道二分搜索法end的定義可以有兩種，但是如果優(yōu)化插入排序算法的話，我們這里的end只能定義為搜索數(shù)組的末尾元素的后一位while (begin != end){ //寫begin<end也可，begin=end時已經(jīng)找到插入位置int mid = (begin + end) / 2;if (array[chaosBeginIndex] < array[mid]){end = mid;}else if (array[chaosBeginIndex] >= array[mid]){begin = mid + 1;}}return begin;//如果前面end定義是數(shù)組末尾元素索引，會導(dǎo)致begin和end錯過時才能確定插入位置，而且我們不知道begin和end哪個是正確的插入位 }void insertionSort_BSEdition(vector<int> &array) //這里以數(shù)組左側(cè)作為有序的那一邊 {// chaosBeginIndex：未排序序列的起始元素下標(biāo)for (int chaosBeginIndex = 1; chaosBeginIndex < array.size(); chaosBeginIndex++)//外循環(huán)控制從第二個元素開始插入到有序序列里，直到最后一個元素{int rightEIndex = binarySearchInsertionIndex(array, chaosBeginIndex); //二分搜索找到正確插入位置O（logn）int insertENum = array[chaosBeginIndex]; //保留插入元素內(nèi)容，因為后面要后移覆蓋騰出插入的位置for (int i = chaosBeginIndex; i > rightEIndex; i--){array[i] = array[i - 1];}array[rightEIndex] = insertENum;vectorPrint(array);} } 輸入數(shù)組： 6 9 3 1 2 0 8 29 15 11 10 插入排序二分搜索優(yōu)化版 6 9 3 1 2 0 8 29 15 11 10 3 6 9 1 2 0 8 29 15 11 10 1 3 6 9 2 0 8 29 15 11 10 1 2 3 6 9 0 8 29 15 11 10 0 1 2 3 6 9 8 29 15 11 10 0 1 2 3 6 8 9 29 15 11 10 0 1 2 3 6 8 9 29 15 11 10 0 1 2 3 6 8 9 15 29 11 10 0 1 2 3 6 8 9 11 15 29 10 0 1 2 3 6 8 9 10 11 15 29 算法用時：（微秒） [AlgoTime: 11002 us]

---

完整代碼

#include <iostream> #include <vector> #include "MeasureAlgoTime.hpp" using namespace std;void vectorPrint(vector<int> &array) {for (int i = 0; i < array.size(); i++){cout << array[i] << ' ';}cout << endl; }//想象插入排序就是兩只手，一只手里的牌是有序的，一只是無序的，每次把無序的手里的牌的第一張，與有序的比較，插入有序牌堆的合適位置 //插入排序的時間復(fù)雜度： 與數(shù)組中的逆序?qū)τ嘘P(guān) ，逆序?qū)?#xff1a;比如想要遞增的數(shù)組【0，8，9，1】這里【8，1】【9，1】都是逆序?qū)?/span> //最壞時間復(fù)雜度：O（n2）（輸入數(shù)組完全逆序），最好時間復(fù)雜度O（n）（輸入數(shù)組已經(jīng)有序），平均時間復(fù)雜度O（n2），空間復(fù)雜度O（1）,原地穩(wěn)定排序算法 //排序算法在逆序?qū)μ貏e少的數(shù)組中效率很高，甚至可能比O（nlogn）級別的堆排序和快速排序還快void insertionSort1th(vector<int> &array) //這里以數(shù)組左側(cè)作為有序的那一邊 {// chaosBeginIndex：未排序序列的起始元素下標(biāo)// insertEIndex：拿去插入有序序列的那個元素的下標(biāo)，就是未排序序列的起始元素，但隨著交換位置，下標(biāo)會改變for (int chaosBeginIndex = 1; chaosBeginIndex < array.size(); chaosBeginIndex++)//外循環(huán)控制從第二個元素開始插入到有序序列里，直到最后一個元素{for (int insertEIndex = chaosBeginIndex; insertEIndex > 0; insertEIndex--)//內(nèi)循環(huán)控制從未排序序列的首元素開始，逐漸與有序序列元素比較和交換位置，找到有序序列中的合適位置{if (array[insertEIndex] < array[insertEIndex - 1]){int temp = array[insertEIndex];array[insertEIndex] = array[insertEIndex - 1];array[insertEIndex - 1] = temp;}else{break;}}vectorPrint(array);} }void insertionSort1thRe(vector<int> &array) //這里以數(shù)組右側(cè)作為有序的那一邊 {for (int chaosBeginIndex = array.size() - 1 - 1; chaosBeginIndex >= 0; chaosBeginIndex--){for (int insertEIndex = chaosBeginIndex; insertEIndex < array.size() - 1; insertEIndex++){if (array[insertEIndex] > array[insertEIndex + 1]){int temp = array[insertEIndex];array[insertEIndex] = array[insertEIndex + 1];array[insertEIndex + 1] = temp;}else{break;}}vectorPrint(array);} }//插入排序的第一次優(yōu)化，就是把不斷的交換位置，改成了找到位置后插入數(shù)組，數(shù)組元素后移覆蓋 //就是把左邊比我大的元素都要跟我交換，換成了左邊比我大的元素都要往右移 void insertionSort2nd(vector<int> &array) //這里以數(shù)組左側(cè)作為有序的那一邊 {for (int chaosBeginIndex = 1; chaosBeginIndex < array.size(); chaosBeginIndex++){int insertENum = array[chaosBeginIndex]; //記錄插入元素的元素內(nèi)容，因為后面原本位置會被覆蓋int rightEIndex = chaosBeginIndex; //記錄正確的插入位置，初始值就是被插入元素的原本位置（未排序序列的第一個元素位置）while (rightEIndex > 0) //不斷比較插入元素與有序隊列元素，找到合適插入位置，用rightEIndex記錄{if (insertENum < array[rightEIndex - 1]){array[rightEIndex] = array[rightEIndex - 1]; //妙啊，找合適位置的同時就順便把元素后移了rightEIndex = rightEIndex - 1;}else{break;}}array[rightEIndex] = insertENum; //插入到空出來的合適位置中vectorPrint(array);} }//整體思想是利用二分搜索的框架，修改結(jié)束條件，從找到或找不到某元素，變?yōu)閷ふ覕?shù)組中第一個大于插入元素的元素 //具體修改: 插入元素小于mid，更新搜尋范圍向左，插入元素大于等于mid，更新搜尋范圍向右，直到begin=end說明找到插入位置 int binarySearchInsertionIndex(vector<int> array, int chaosBeginIndex) {int begin = 0;int end = chaosBeginIndex;//!我們知道二分搜索法end的定義可以有兩種，但是如果優(yōu)化插入排序算法的話，我們這里的end只能定義為搜索數(shù)組的末尾元素的后一位while (begin != end){ //寫begin<end也可，begin=end時已經(jīng)找到插入位置int mid = (begin + end) / 2;if (array[chaosBeginIndex] < array[mid]){end = mid;}else if (array[chaosBeginIndex] >= array[mid]){begin = mid + 1;}}return begin;//如果前面end定義是數(shù)組末尾元素索引，會導(dǎo)致begin和end錯過時才能確定插入位置，而且我們不知道begin和end哪個是正確的插入位 }void insertionSort_BSEdition(vector<int> &array) //這里以數(shù)組左側(cè)作為有序的那一邊 {// chaosBeginIndex：未排序序列的起始元素下標(biāo)for (int chaosBeginIndex = 1; chaosBeginIndex < array.size(); chaosBeginIndex++)//外循環(huán)控制從第二個元素開始插入到有序序列里，直到最后一個元素{int rightEIndex = binarySearchInsertionIndex(array, chaosBeginIndex); //二分搜索找到正確插入位置O（logn）int insertENum = array[chaosBeginIndex]; //保留插入元素內(nèi)容，因為后面要后移覆蓋騰出插入的位置for (int i = chaosBeginIndex; i > rightEIndex; i--){array[i] = array[i - 1];}array[rightEIndex] = insertENum;vectorPrint(array);} }int main() {Tools::Time::AlgoTimeUs time1;Tools::Time::AlgoTimeUs time2;Tools::Time::AlgoTimeUs time3;Tools::Time::AlgoTimeUs time5;vector<int> array;array = {6, 9, 3, 1, 2, 0, 8, 29, 15, 11, 10};vector<int> array2 = array;vector<int> array3 = array;vector<int> array5 = array;cout << "輸入數(shù)組：" << endl;vectorPrint(array);time1.start();cout << "插入排序基礎(chǔ)版" << endl;insertionSort1th(array);cout << "算法用時：（微秒）";time1.printElapsed();cout << "輸入數(shù)組：" << endl;vectorPrint(array2);time2.start();cout << "插入排序基礎(chǔ)版（換一個方向）" << endl;insertionSort1thRe(array2);cout << "算法用時：（微秒）";time2.printElapsed();cout << "輸入數(shù)組：" << endl;vectorPrint(array3);time3.start();cout << "插入排序第一次優(yōu)化版" << endl;insertionSort2nd(array3);cout << "算法用時：（微秒）";time3.printElapsed();cout << "輸入數(shù)組：" << endl;vectorPrint(array5);time5.start();cout << "插入排序二分搜索優(yōu)化版" << endl;insertionSort_BSEdition(array5);cout << "算法用時：（微秒）";time5.printElapsed();cout << ' ' << endl;return 0; }

總結(jié)

以上是生活随笔為你收集整理的插入排序算法 及其二分搜索优化版 C++代码实现 恋上数据结构笔记的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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