排序之——直接插入排序

插入排序的基本思想

每次将一个待排序的记录按其关键字大小插入前面已经排好序的子序列，直到全部记录插入完成。

步骤（从小到大排序）

1. 找到没有排序的元素
2. 标记元素
3. 将已排好序的序列中大于标记元素的往后移
4. 插入元素

算法代码

• 设置变量 temp 暂存标记元素

#include <iostream>
using namespace std;

//直接插入排序算法 
void InsertSort(int nums[],int n){
	int temp,i,j;
	for(i=1;i<n;i++){
		if(nums[i]<nums[i-1]){					//若 nums[i]<nums[i-1] 即当前项比前一项小 
			temp=nums[i];						//temp 暂存 nums[i] 
			for(j=i;j>0&&nums[j-1]>temp;j--){ 	//检查所有已经排好序的元素 
				nums[j]=nums[j-1];				//将所有大于 temp 的元素往后移 
			}
			nums[j]=temp;						//将 temp 插入序列中 
		}
	}
}

//打印数组 
void printNum(int numbers[],int n){
	for(int i=0;i<n;i++){
		cout<<numbers[i]<<" ";
	}
}

int main()
{
	int numbers[10]={3,44,5,44,47,15,36,26,27,2};
	int n=sizeof(numbers)/sizeof(numbers[0]);	//数组长度 
	InsertSort(numbers,n);		//调用 InsertSort 函数进行插入排序 
	printNum(numbers,n);		//打印数组 
    return 0;
}

• 设置 nums[0] 暂存标记元素

#include <iostream>
using namespace std;

//直接插入排序算法(nums[0] 设置为哨兵替代 temp 暂存)
void InsertSort(int nums[],int n){
	int i,j;
	for(i=2;i<n;i++){
		if(nums[i]<nums[i-1]){				//若 nums[i]<nums[i-1] 即当前项比前一项小 
			nums[0]=nums[i];					//nums[0] 暂存 nums[i] 
			for(j=i;nums[j-1]>nums[0];j--){ //检查所有已经排好序的元素 
				nums[j]=nums[j-1];			//将所有大于 nums[0] 的元素往后移 
			}
			nums[j]=nums[0];						//将 nums[0] 插入序列中 
		}
	}
}

//打印数组 
void printNum(int numbers[],int n){
	for(int i=1;i<n;i++){
		cout<<numbers[i]<<" ";
	}
}

int main()
{
	int numbers[11]={0,3,44,5,44,47,15,36,26,27,2};
	int n=sizeof(numbers)/sizeof(numbers[0]);	//数组长度 
	InsertSort(numbers,n);		//调用 InsertSort 函数进行插入排序 
	printNum(numbers,n);		//打印数组 
    return 0;
}

算法性能分析

• 空间复杂度：$O(1)$

• 时间复杂度：$O(n^2)$

• 算法稳定性¹：稳定

---

1. 算法的稳定性：若待排序表中有两个元素 $R_i$ 和 $R_j$，其对应的关键字相同即 $ke{y}_i=ke{y}_j$，且在排序前 $R_i$ 在 $R_j$ 的前面，若使用某一排序算法排序后， $R_i$ 仍在 $R_j$ 的前面，则称这个排序算法是稳定的，否则称排序算法是不稳定的。 ↩︎