排序之——直接插入排序
插入排序的基本思想
每次将一个待排序的记录按其关键字大小插入前面已经排好序的子序列，直到全部记录插入完成。
步骤（从小到大排序）
- 找到没有排序的元素
- 标记元素
- 将已排好序的序列中大于标记元素的往后移
- 插入元素
算法代码
- 设置变量
temp暂存标记元素
#include<iostream>usingnamespacestd; //直接插入排序算法 voidInsertSort(intnums[],intn){ inttemp,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 插入序列中 } } } //打印数组 voidprintNum(intnumbers[],intn){ for(inti=0;i<n;i++){ cout<<numbers[i]<<" "; } } intmain() { intnumbers[10]={3,44,5,44,47,15,36,26,27,2}; intn=sizeof(numbers)/sizeof(numbers[0]); //数组长度 InsertSort(numbers,n); //调用 InsertSort 函数进行插入排序 printNum(numbers,n); //打印数组 return0; }
- 设置
nums[0]暂存标记元素
#include<iostream>usingnamespacestd; //直接插入排序算法(nums[0] 设置为哨兵替代 temp 暂存)voidInsertSort(intnums[],intn){ inti,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] 插入序列中 } } } //打印数组 voidprintNum(intnumbers[],intn){ for(inti=1;i<n;i++){ cout<<numbers[i]<<" "; } } intmain() { intnumbers[11]={0,3,44,5,44,47,15,36,26,27,2}; intn=sizeof(numbers)/sizeof(numbers[0]); //数组长度 InsertSort(numbers,n); //调用 InsertSort 函数进行插入排序 printNum(numbers,n); //打印数组 return0; }
算法性能分析
