?前言?：
演算法是一個程式員的內功，能很好的體現程式員的編程思維，通過學習和掌握常見的演算法，不僅能提高coding能力，還能更加容易在筆面試中脫穎而出，本專欄將記錄博主刷演算法題的程序，不定期的會更新一些優質的演算法題，如果對大家有幫助，別忘了三連支持喲！
目錄
?前言?：
?插入排序的思想?
💎如何進行插入💎
💎插入的具體方法💎
?插入排序具體代碼的實作?
?時間復雜度的計算?
?
?插入排序的思想?
💡：插入排序的核心思想就是插入二字，理解要如何插入和其內在的邏輯對深刻理解插入排序至關重要，
💎如何進行插入💎
🔑：我們假設要對n個數進行插入排序，那么我們的步驟是，先讓下標0~0上有序（只有一個數顯然成立），我們再把下標為1的數插入進這個有序序列中去讓0~1上有序，而我們要實作0~2上有序，只需要讓2位置的數插入到0~1上（這時0~1上的數相對順序不變，其還是有序的，讓2位置的數插入到應該在的位置），以此類推，最后一次時，下標為0~n-2上所有數都已經有序了，只需要將下標為n-1的元素插入到0~n-2這個有序序列中去，從這樣的邏輯分析，每次我們讓后面一個數插入時，前面所有數都已經有序，由這樣的邏輯分析下去最后一定讓所有數全部有序，
💎插入的具體方法💎
🔑上文講了插入排序的全部程序，但并沒有細致的講具體是如何進行插入的，其實插入的程序只有一個步驟：
比如我們現在想要讓0~n上排成升序，由上述可知，此時0~n-1上一定已經有序，我們插入的時候不能改變原本0~n-1上所有元素的相對順序，只需要讓n位置的元素向左看與它相鄰的元素，如果n位置的元素比左邊的小，就讓兩個元素進行交換，然后這個元素繼續與左邊的元素比較，如果小就交換，直到它比左邊元素大或者左邊沒有元素時才會停下來，
💡:插入的步驟可以簡化為4個字 （看 比 換 停），
講到這里相信大家對插入排序的大致思路顯然已經十分清晰了，如果大家胸有成竹，請大家先自己寫一篇，再過來看看我寫的代碼，這樣效果最好，
?插入排序具體代碼的實作?
#include<stdio.h>
void Swap(int arr[], int i, int j)
{
//兩種方法
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
//arr[i] = arr[i] ^ arr[j];
//arr[j] = arr[i] ^ arr[j];
//arr[i] = arr[i] ^ arr[j];
}
void insertionSort(int arr[], int sz)
{
for (int i = 1; i < sz; i++)//控制插入排序的范圍即0-1....0-n-1
{
for (int j = i - 1; j >= 0 && arr[j + 1] < arr[j]; j--)
{
//滿足兩個條件才交換
//1:小于左邊的數
//2:沒有越界
Swap(arr, j, j + 1);
}
}
}?時間復雜度的計算?
以上代碼，還可做優化在此僅作參考，若有更好的演算法，還望能夠私信告知，多謝各位，
由于本人水平十分有限，若有錯誤請即使告知！如果有幫助別忘了，萬分感謝，
點贊👍 收藏? 關注?
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/299183.html
標籤：其他
上一篇：資料結構：空間復雜度