小滕的博客

小滕的技术点滴

java实现插入排序

1 month ago · 1 MIN READ

package com.xiaoteng;

import java.util.Arrays;

public class InsertSort {

    public int[] sort(int[] a) {
        int[] b = new int[a.length];
        for (int i = 0; i < a.length; i++) {
            if (i == 0) {
                b[0] = a[i];
                continue;
            }
            int tmp = a[i];
            int j = i - 1;
            while (b[j] > tmp && j >= 0) {
                b[j+1] = b[j];
                j--;
            }
            b[j + 1] = tmp;
            System.out.println("b的值:" + Arrays.toString(b));
        }
        return b;
    }

    public static void main(String[] args) {
        int[] arr = {1, 1, 2, 3, 18, 1, 999, 3, 19, 99, 29, 190, 120, 12};
        InsertSort insertSort = new InsertSort();
        System.out.println("排序结果:" + Arrays.toString(insertSort.sort(arr)));
    }
}

运行结果:

b的值:[1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
b的值:[1, 1, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
b的值:[1, 1, 2, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
b的值:[1, 1, 2, 3, 18, 0, 0, 0, 0, 0, 0, 0, 0, 0]
b的值:[1, 1, 1, 2, 3, 18, 0, 0, 0, 0, 0, 0, 0, 0]
b的值:[1, 1, 1, 2, 3, 18, 999, 0, 0, 0, 0, 0, 0, 0]
b的值:[1, 1, 1, 2, 3, 3, 18, 999, 0, 0, 0, 0, 0, 0]
b的值:[1, 1, 1, 2, 3, 3, 18, 19, 999, 0, 0, 0, 0, 0]
b的值:[1, 1, 1, 2, 3, 3, 18, 19, 99, 999, 0, 0, 0, 0]
b的值:[1, 1, 1, 2, 3, 3, 18, 19, 29, 99, 999, 0, 0, 0]
b的值:[1, 1, 1, 2, 3, 3, 18, 19, 29, 99, 190, 999, 0, 0]
b的值:[1, 1, 1, 2, 3, 3, 18, 19, 29, 99, 120, 190, 999, 0]
b的值:[1, 1, 1, 2, 3, 3, 12, 18, 19, 29, 99, 120, 190, 999]
排序结果:[1, 1, 1, 2, 3, 3, 12, 18, 19, 29, 99, 120, 190, 999]

其实上面的算法存在一个问题:插入排序本身不需要引入额外的内存空间,但是上面的算法引入了b,所以最优的是下面这个:


package com.xiaoteng;

import java.util.Arrays;

public class InsertSort {

    public int[] sort(int[] a) {
        for (int i = 1; i < a.length; i++) {
            int tmp = a[i];
            int j = i - 1;
            while (a[j] > tmp && j >= 0) {
                a[j + 1] = a[j];
                j--;
            }
            a[j + 1] = tmp;
            System.out.println("b的值:" + Arrays.toString(a));
        }
        return a;
    }

    public static void main(String[] args) {
        int[] arr = {1, 1, 2, 3, 18, 1, 999, 3, 19, 99, 29, 190, 120, 12};
        InsertSort insertSort = new InsertSort();
        System.out.println("排序结果:" + Arrays.toString(insertSort.sort(arr)));
    }
}

直接在原有的a数组上面操作。

···

xiao teng



备案号:皖ICP备14012032号-5