首页 > 代码库 > 插入排序
插入排序
输入：待排序的n个数；
输出：输入序列的一个有序排列（从小到大）
插入排序是一种原地排序算法。假设A[j]是待排元素，每次A[j]之前的子数组A[0..j-1]都是已排好序的。这样A[j]只需从后往前和子数组元素比较把比A[j]大的元素向后移动一位，将A[j]插入到合适位置后。j从0取到A.length()之后，数组A也就成为了一个有序数组。插入排序算法的复杂度为O(n2).
import java.util.*;
public class InsertSort {
static int [] insertSort(int [] A){
int i=0;
for(int j=1;j<A.length;j++){
int key=A[j];//key保存待排元素A[j]的值
i=j-1;
while(i>=0&&A[i]>key){//因为子数组是已排好序的，所以从后往前比较大小找到A[j]应该插入的位置，并将比A[j]大的元素往后移动
A[i+1]=A[i];
i=i-1;
}
A[i+1]=key;//将A【j】插入到合适的位置。
}
print(A);
return A;
}
static void print(int [] A){
for(int i=0;i<A.length;i++){
System.out.print(A[i]+" ");
}
System.out.println();
}
public static void main(String[] args) {
int [] A=new int[6];
Random rand=new Random();
for(int i=0;i<A.length;i++)
{
A[i]=rand.nextInt(100);
}
print(A);
insertSort(A);
}
}
插入排序
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。