1. 復(fù)雜度與穩(wěn)定性

最壞情況：O(N^2)

最好情況：O(N^2)

平均情況：O(N^2)

穩(wěn)定性：穩(wěn)定排序

2. 過(guò)程介紹

直接插入排序是把新的數(shù)據(jù)插入以及排序好的數(shù)列中，排序的基本方法是：每一步將一個(gè)待排序的元素，按其排序碼的大小，插入到前面已經(jīng)排好序的一組元素的適當(dāng)位置上去，直到元素全部插入為止。

可以選擇不同的方法在已經(jīng)排好序數(shù)據(jù)表中尋找插入位置。根據(jù)查找方法不同，有多種插入排序方法，下面要介紹的是直接插入排序。

1.         每次從無(wú)序表中取出第一個(gè)元素，把它插入到有序表的合適位置，使有序表仍然有序。

2.         第一趟比較前兩個(gè)數(shù)，然后把第二個(gè)數(shù)按大小插入到有序表中；

3.         第二趟把第三個(gè)數(shù)據(jù)與前兩個(gè)數(shù)從后向前掃描，把第三個(gè)數(shù)按大小插入到有序表中；

4.         依次進(jìn)行下去，進(jìn)行了(n-1)趟掃描以后就完成了整個(gè)排序過(guò)程。

直接插入排序是由兩層嵌套循環(huán)組成的。外層循環(huán)標(biāo)識(shí)并決定待比較的數(shù)值。內(nèi)層循環(huán)為待比較數(shù)值確定其最終位置。直接插入排序?qū)⒋容^的數(shù)值與它的前一個(gè)數(shù)值進(jìn)行比較，所以外層循環(huán)是從第二個(gè)數(shù)值開(kāi)始的。當(dāng)前一數(shù)值比待比較數(shù)值大的情況下繼續(xù)循環(huán)比較，直到找到比待比較數(shù)值小的并將待比較數(shù)值置入其后一位置，結(jié)束該次循環(huán)。

3.圖示過(guò)程

以數(shù)組數(shù)據(jù){ 70,50,30,20,10,70,40,60}為例：

將紅色的數(shù)據(jù)依次插入組成一個(gè)逐漸有序的數(shù)組

4.  相關(guān)的代碼

#include<iostream>
using namespace std;
void insert_sort(int a[],int n) {
    int i,j;
    for(i=1; i<n; i++) { //循環(huán)從第2個(gè)元素開(kāi)始
        if(a[i]<a[i-1]) {
            int temp=a[i];
            for(j=i-1; j>=0 && a[j]>temp; j--) {
                a[j+1]=a[j];
            }
            a[j+1]=temp;//此處就是a[j+1]=temp;
        }
    }
}
 
int main() {
    int a[8]= {70,50,30,20,10,70,40,60};
    int n=7;
    insert_sort(a,n);
    for(int i=0; i<=n; i++) {
        cout<<a[i]<<' ';
    }
    return 0;
}