Java教程

java排序算法之插入排序

本文主要是介绍java排序算法之插入排序,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

排序算法之插入排序

插入排序:
1.插入排序的复杂度是O(n^2),四大基础排序算法之一,八大基本排序算法之一
2.插入排序的原理:插入排序是在一个已经有序的小序列的基础上,一次插入一个元素。刚开始这个小序列只包含第一个元素,事件复杂度O(n2)。比较是从这个小序列的末尾开始的。想要插入的元素和小序列的最大者开始比起,如果比它大则直接插在其后面,否则一直往前找它该插入的位置。如果遇见了一个和插入元素相等的,则把插入元素放在这个相等元素的后面。所以相等元素间的顺序没有改变,是稳定的。

3.代码实现:

package cn.ycl.dataStructures.sort;
import java.util.Arrays;
public class insertSort {
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int array[] = { 45, 1, 34, 23, 12, 90, -1 };
		insertSort.insert(array);
		System.out.println(Arrays.toString(array));
	}
	public static void insert(int array[]) {
		for (int i = 0; i < array.length; i++) {
			// 将要插入的值赋给一个不变的变量,使得后面可以改变array[i],而保留array[i]原来的值
			int insertVal = array[i];
			int insertIndex = i - 1;
                       //insertIndex>=0是为了让insertIndex不越界,不能出现array[-1]的情况
			while (insertIndex >= 0 && insertVal < array[insertIndex]) {
				array[insertIndex + 1] = array[insertIndex];
				insertIndex--;
			}
			if (insertIndex + 1 != i) {
				array[insertIndex + 1] = insertVal;
			}
		}
	}
}

我是“道祖且长”,一个在互联网苟且偷生的Java程序员

这篇关于java排序算法之插入排序的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!