首页 > 代码库 > Java排序算法之插入排序

Java排序算法之插入排序

基本过程:

每次将待排元素和已经排序好的序列进行比较,按照大小顺序插入进去,重新构造一个新的有序序列。

插入排序算法有种递归的思想在里面,它由N-1趟排序组成。初始时,只考虑数组下标0处的元素,只有一个元素,显然是有序的。

然后第一趟 对下标 1 处的元素进行排序,保证数组[0,1]上的元素有序;

第二趟 对下标 2 处的元素进行排序,保证数组[0,2]上的元素有序;

.....

.....

第N-1趟对下标 N-1 处的元素进行排序,保证数组[0,N-1]上的元素有序,也就是整个数组有序了。

它的递归思想就体现在:当对位置 i 处的元素进行排序时,[0,i-1]上的元素一定是已经有序的了

Java代码实现:

package paixu;

import java.util.Arrays;

public class Charu {

    public static void insertSort(int[] numbers){
        int size = numbers.length;    
        for(int i = 0 ; i < size ; i++){
            int temp = numbers[i];
            //假如temp比前面的值小,则将前面的值后移
            for(int j = i ; j > 0 && temp < numbers[j-1] ; j --){
                numbers[j] = numbers[j-1];
            }
            numbers[j] = temp;
        }
    }
    
    public static void main(String[] args) {
        int a[] = {46,79,56,38,40,84};
        insertSort(a);
        System.out.println(Arrays.toString(a));
    }
}

算法性能分析:

时间复杂度:当待排数组有序时,没有移动操作,此时复杂度为O(N),当待排数组是逆序时,比较次数达到最大--对于下标 i 处的元素,需要比较 i-1 次。总的比较次数:1+2+...+N-1 ,故时间复杂度为O(N^2)

空间复杂度:O(1)。

稳定性:插入排序是在一个已经有序的小序列的基础上,一次插入一个元素。比较也是从有序序列的末尾开始,如果碰见一个和插入元素相等的,那么插入元素把想插入的元素放在相等元素的后面。所以,相等元素的前后顺序没有改变,

所以插入排序是稳定的。

Java排序算法之插入排序