欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

java简单排序算法之插入排序

程序员文章站 2024-03-16 22:21:40
...

插入排序

简介

	插入排序的算法描述是一种简单直观的排序算法。它的工作原理是通过构建有序序
	列,对于未排序数据,在已排序的序列中从后向前扫描,找到相依的插入位置。插
	入排序在实现上,通常采用in-place排序(即只需用到O(1)的额外空间的排序),
	因而再从后像前扫描的过程中,需要反复把已排序的元素逐步向后挪位,为最新的
	元素提供插入空间。

描述过程

	1.从第一个元素开始,该元素可以认为已经被排序。
	2.取出下一个元素,在已排序的元素序列中从后向前扫描。
	3.如果该元素(宝库已排序)大于新的元素,该元素移动到下一个位置。
	4.重复第3步,直到找到已排序的元素小于或者等于新元素的位置。
	5.将新元素插入到该位置后,重复2~5步。

演示图

第一步:默认是第一个数已排序

java简单排序算法之插入排序

第二步 44比3大就默认已排序到第二的位置

java简单排序算法之插入排序

第三步 取出38从后向前对比

java简单排序算法之插入排序

第四步:从后向前对比,放入第2个位置

java简单排序算法之插入排序

第5步:依次类推

java简单排序算法之插入排序

大白话理解

	一个数组中,默认第一个元素已经被排序了。取出第二个元素跟第一个元素比较大
	小。大的就原地插入,小就向前插入。取出第三个元素从后向前依次比较。比第二
	元素小就继续跟第一个元素比较。比第二元素大就原地插入。依次类推,直到所有
	元素比较完,排序就完成了。

代码演示

/**
 *  插入排序
 * @author Mr.qian
 */
public class InsertSort {
	
	public static void main(String[] args) {
		int[] arr = {8,1,9,2,7,4,5,3,6};
		sort(arr);
	}
	
	public static void sort(int[] arr) {
		//1.判空
		if(arr == null || arr.length <= 1) {
			return ;
		}
		//2.设置当前元素
		int current;                                                   
		for(int i = 0; i < arr.length -1; i++) {                            
			current =  arr[i+1]; // 当前元素下标;                         
			int preIndex = i;    // 上一元素下标;                                              
			//3.如果当前元素小于上一个元素
			while(preIndex >= 0 && current < arr[preIndex]) {            
				//需要将上一个元素下标进行下移
				arr[preIndex+1] = arr[preIndex];                        
				//4 .保证从后向前完全遍历比较											
				preIndex --;                                               
			}
			
			arr[preIndex +1] = current;                               
		}
		System.out.println(Arrays.toString(arr));
	}
}

结论

插入排序
平均时间复杂度 O(n²)
最好情况 O(n)
最坏情况 O(n²)
空间复杂度 O(1)
排序方式 In-place (内排序)
稳定性 Y
相关标签: java数据结构