插入排序：直接插入排序（穩(wěn)定）
【 算法思想 】 直接插入排序是一種最基本的插入排序方法，其基本操作是將第 i 個(gè)記錄插入到前面 i-1 個(gè)已排好序的記錄中。具體過程為：將第 i 個(gè)記錄的關(guān)鍵字 K i ，順次與其前面記錄的關(guān)鍵字 K i-1 ，K i-2 ，…, K 1 進(jìn)行比較，將所有關(guān)鍵字大于 K i 的記錄依次向后移動(dòng)一個(gè)位置，直到遇見一個(gè)關(guān)鍵字小于或者等于 K i 的記錄 K j ，此時(shí) K j 后面必為空位置，將第 i 個(gè)記
錄插入空位置即可。完整的直接插入排序是從 i=2 開始，也就是說，將第 1 個(gè)記錄視為已排好序的單元素子集合，然后將第二個(gè)記錄插入到單元素子集合中。i 從 2 循環(huán)到 n，即可實(shí)現(xiàn)完整的直接插入排序。
我們經(jīng)常會(huì)到這樣一類排序問題：把新的數(shù)據(jù)插入到已經(jīng)排好的數(shù)據(jù)列中。將第一個(gè)數(shù)和第二個(gè)數(shù)排序，然后構(gòu)成一個(gè)有序序列將第三個(gè)數(shù)插入進(jìn)去，構(gòu)成一個(gè)新的有序序列。對(duì)第四個(gè)數(shù)、第五個(gè)數(shù)……直到最后一個(gè)數(shù)，重復(fù)第二步。如題所示：
直接插入排序（Straight Insertion Sorting）的基本思想：在要排序的一組數(shù)中，假設(shè)前面(n-1) [n>=2] 個(gè)數(shù)已經(jīng)是排好順序的，現(xiàn)在要把第n個(gè)數(shù)插到前面的有序數(shù)中，使得這n個(gè)數(shù)也是排好順序的。如此反復(fù)循環(huán)，直到全部排好順序。
C#實(shí)現(xiàn)：
/// <summary>
/// 自定義工具類
/// </summary>
public static class Utilit
{
/// <summary>
/// 輔助輸出排序結(jié)果：
/// </summary>
/// <param name="a"></param>
/// <param name="t"></param>
public static void Print(int[] a, int t)
{
string str = null;
for (int i = 0; i < a.Length; i++)
{
str += a[i].ToString() + " ";
}
Debug.Log("第" + t + "趟排序結(jié)果：" + str);
}
/// <summary>
/// 輔助生成排序結(jié)果
/// </summary>
/// <param name="max"></param>
/// <param name="length"></param>
/// <returns></returns>
public static int[] RandArray(int max, int length)
{
string str = null;
int[] a = new int[length];
for (int i = 0; i < a.Length; ++i)
{
a[i] = Random.Range(0, max);
str += a[i].ToString() + " ";
}
Debug.Log("隨機(jī)生成的數(shù)組：" + str);
return a;
}
}
上方為產(chǎn)生隨機(jī)數(shù)組與打印排序數(shù)組的工具類
直接插入排序：
/// <summary>
/// 插入排序類
/// </summary>
public class InsertSort
{
/// <summary>
///1、 直接插入排序法：
/// </summary>
/// <param name="a"></param>
public static void StraightInsetSort(int[] a)
{
int insertNum;//要插入的數(shù)
int len = a.Length;//數(shù)組長(zhǎng)度
for (int i = 1; i < len; i++) //從第2個(gè)數(shù)，進(jìn)行插入排序
{
insertNum = a[i];
int j = i - 1; //前一個(gè)數(shù)的索性值
while (j >= 0 && insertNum < a[j])
{
a[j + 1] = a[j]; //把大的向后移動(dòng)
j--;
}
a[j + 1] = insertNum;//找到位置，插入當(dāng)前元素
Utilit.Print(a, i);//輸出每趟的排序的結(jié)果
}
}
}
測(cè)試用例：
public class _012_InsertSort : MonoBehaviour
{
void Start()
{
int[] a = Utilit.RandArray(20, 10); //max,lenght
Debug.Log("------------直接插入排序----------------");
InsertSort.StraightInsetSort(a); //直接插入排序
}
}
輸出結(jié)果：
![]()
插入排序：直接插入排序
注：
1、直接插入排序的時(shí)間復(fù)雜度為 T(n)=O(n 2 )，空間復(fù)雜度為 S(n)=O(1)。
2、穩(wěn)定排序算法
3、直接插入排序算法簡(jiǎn)便，比較適用于待排序記錄數(shù)目較少且基本有序的情況。當(dāng)待排記錄數(shù)目較大時(shí)，直接插入排序的性能就不好，因此可以對(duì)直接插入排序做進(jìn)一步的改進(jìn)。在直接插入排序法的基礎(chǔ)上，從減少“比較關(guān)鍵字”和“移動(dòng)記錄”兩種操作的次數(shù)著手來進(jìn)行改進(jìn)。
