【Java】五种常见排序之----------------------插入排序
- 原理:将一个数通过比较后,插入到一个有序的序列中去,使插入数后的序列仍是一个有序序列;
- 时间复杂度:O(n^2)
- 空间复杂度:最优(已排好序)为0.其它情况为O(1);平均空间复杂度为O(1)
- 核心算法代码:
for(int i=1;i<n;i++){
int temp=num[i];
int index=i-1;
while(index>=0 && temp<num[index]){//寻找插入点
num[index+1]=num[index];//将元素后移一个位置
index--;
}
num[index+1]=temp;
}![](//img-blog.csdn.net/20170304101806597?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvWGluZ19QZW5nZmVp/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/Center)
package paixu;
/**
* @author xpengfei
*/
import java.util.Scanner;
/*
* 插入排序
* 时间复杂度,最优的情况是数组已排好序,此时时间复杂度为O(n);
* 最差情况为逆序,此时时间复杂度为O(n^2);平均时间复杂度为O(n^2).
*
* 时间复杂度基本符合理论值O(n^2)
*
*
* 空间复杂度,最优情况下是数组已排好序,此时为0;
* 其它情况为O(1);平均空间复杂度为O(1)。
*/
public class sortThree {
Scanner input=new Scanner(System.in);
private int n;
private int num[];
public sortThree(){
System.out.println("请输入数组规模大小:");
n=input.nextInt();
num=new int[n];
System.out.println("随机生成的数组如下:");
for(int i=0;i<n;i++){
num[i]=(int)(Math.random()*1000);
System.out.println(num[i]);
}
}
public void SortThree(){
for(int i=1;i<n;i++){
int temp=num[i];
int index=i-1;
while(index>=0 && temp<num[index]){//寻找插入点
num[index+1]=num[index];//将元素后移一个位置
index--;
}
num[index+1]=temp;
}
}
public void display(){
System.out.println("排序后的数组如下:");
for(int i=0;i<n;i++){
System.out.println(num[i]);
}
}
public static void main(String[] args) {
sortThree sThree=new sortThree();
sThree.SortThree();
sThree.display();
}
}
原文地址:https://www.cnblogs.com/xpfei/p/7450813.html