插入排序是什么?插入排序法原理以及代码实例讲解

思想:此处的插入排序为最简单的直接插入排序,将一个元素,插入有序队列的合适位置,使得插入后的序列依旧有序。

原理:将待插入元素一个个插入初始已有序部分中的过程,而插入位置的选择遵循了使插入后仍然保持有序的原则,具体做法一般是从后往前枚举已有序部分来确定插入位置。

代码描述:

#include<iostream>
using namespace std;
int main(){
char A[10]={1,2,4,5,6,43,7,9,3,5};
for(int i=1;i<10;i++){
int temp=A[i];//temp存放将要排序的数
int j=i; //j从i开始往前枚举
while(j>0&&temp<A[j-1]){//将要排序的数与前面的每一个数进行比较,若将要插入的数较小将其向前面移动;
A[j]=A[j-1];//将较大的数字向后移
j--;
}
A[j]=temp;//A[j]是找到的将要插入的位置,将temp插入
}
for(int i=0;i<10;i++){
printf("%d ",A[i]);
}
return 0;
}

分析:对序列A的n个元素A[0]~A[n-1],令i从1到n-1枚举,进行n-1趟操作。假设某一时,序列A的前i个元素A[0]~A[i]已经有序,而范围[i+1,n]还未有序,那么该从范围[0,i]中寻找某个位置j,使得将A[i+1]插入位置j后(此时A[j]~A[i]会后移一位至A[j+1]~A[i+1]),范围[0,i+1]有序。

时间复杂度:O(n²)

空间复杂度:O(1)

相关推荐

剑指Offer(Python多种思路实现):合并两个排序的链表

【Python学习1:爬取百度贴吧并按回复量生成排序】

【Python学习1:爬取百度贴吧并按回复量生成排序】

C++类对象排序operator重载操作

快速排序找数组中的第N大数