直接插入排序基本思想、示例、详细代码

1、算法思想

直接插入排序是一种最简单的排序方法，基本操作是将一个记录插入到已排好序的有序表中，从而得到一个新的、记录数增1的有序表。整个排序过程为进行n-1趟插入，第一趟比较前两个数，然后把第二个数按大小插入到有序表中； 第二趟把第三个数据与前两个数从后向前扫描，把第三个数按大小插入到有序表中；依次进行下去，进行了(n-1)趟扫描以后就完成了整个排序过程。

2、应用举例

假设待排序序列为49，38，65，97，13，27，49。初始时默认49为有序序列，第一趟排序从第2个关键字开始。38和49进行比较，38插入到49之前，第一趟排序后的序列为38，49，65，97，13，27，49。第二趟排序待插入关键字为65，对有序序列从后往前顺序查找，65比49大，因此65插入到49之后，第二趟排序后的序列为38，49，65，97，13，27，49。第三趟排序待插入关键字为97，对有序序列从后往前顺序查找，97比65大，因此97插入到65之后，第三趟排序后的序列为38，49，65，97，13，27，49。第四趟排序待插入关键字为13，对有序序列从后往前顺序查找，13比97、65、49、38小，因此97插入到38之后，第四趟排序后的序列为13，38，49，65，97，27，49。第五趟排序待插入关键字为27，对有序序列从后往前顺序查找，27比97、65、49、38小，比13大，因此27插入到13之后，第五趟排序后的序列为13，27，38，49，65，97，49。第六趟排序待插入关键字为49，对有序序列从后往前顺序查找，49比97、65小，与49相等，因此49插入到相同元素49之后，第六趟排序后的序列为13，27，38，49，49，65，97。

3、代码说明

① 算法代码

//num[0]是哨兵，暂存当前待插入的值
void insert_sort(int num[],int n){//对num[n+1]进行排序
	for(int i=2;i<=n;i++){//第1个数默认已排好，从第二个数字开始 
		if(num[i]<num[i-1]){//检验当前待插入值是否需要移动 
			num[0]=num[i];//在0号单元设立哨兵
			for(int j=i-1;j--){//从当前位置从后往前扫描 
				if(num[j]>num[0])
					num[j+1]=num[j];//向后移动一个单位 
				else{//此时num[j]<=num[0],所以要把num[0]放在num[j+1]上
					num[j+1]=num[0];
					break;
				}//else
			} //for
		}//if
	} //for
} //void insert_sort

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

②完整代码

#include<bits/stdc++.h>
using namespace std;
//num[0]是哨兵，暂存当前待插入的值
void insert_sort(int num[],int n){//对num[n+1]进行排序
	for(int i=2;i<=n;i++){//第1个数默认已排好，从第二个数字开始 
		if(num[i]<num[i-1]){//检验当前待插入值是否需要移动 
			num[0]=num[i];//在0号单元设立哨兵
			for(int j=i-1;j<=n;j--){//从当前位置从后往前扫描 
				if(num[j]>num[0])
					num[j+1]=num[j];//向后移动一个单位 
				else{//此时num[j]<=num[0],所以要把num[0]放在num[j+1]上
					num[j+1]=num[0];
					break;
				}//else
			} //for
		}//if
		cout<<"第 "<<i-1<<" 趟排序结果为："; 
		for(int j=1;j<=n;j++){
			cout<<num[j]<<" ";
		}
		cout<<endl;
	} //for
} //void insert_sort

int main(){
	int n;
	cin>>n;
	int a[n+1];
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	insert_sort(a,n);
	return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

③结果验证

4、时空复杂度

从上述算法可知，其时间复杂度为O(n^2)，空间复杂度为O(1)。

5、稳定性

直接选择排序是稳定性排序。

6、序列初始状态对算法时间复杂度的影响

直接选择排序的时间复杂度与序列的初始状态有关，最坏情况下直接选择排序的时间复杂度为O(n^2)，最好情况下序列完全有序此时仅需要一趟即可完全排序，最好情况下的时间复杂度为O(n)。