插入排序问题

package com.www.demo10;

import java.text.SimpleDateFormat;
import java.util.Date;

public class Insert {
    public static void main(String[] args) {
        int[] arr = new int[80000];
        for (int i = 0;i < arr.length;i++){
            arr[i] = (int)(Math.random()*1000);
        }

//        show(arr);
        Date date = new Date();
        SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
        String format = simpleDateFormat.format(date);
        System.out.println("排序前" + format);
//        insertLinked(arr);//10s
//        insertSort(arr);//2s
        insertSort1(arr);//1s
        System.out.println();
        Date date1 = new Date();
        String format1 = simpleDateFormat.format(date1);
        System.out.println("排序前" + format1);
//        show(arr);
    }

    //方法一：待插入数据从前向后比较，找出要插入位置，然后将该位置数后移一位，腾出位置放待插入数据
    public static void insertSort(int[] arr){
        for (int i = 1;i < arr.length;i++){
            int temp = arr[i];//待插入数据
            for (int j = 0;j < i;j++){//与前面数据比较
                if (arr[i] < arr[j]){
                    for (int k = i;k > j;k--){//第j位置是要插入位置
                        arr[k] = arr[k-1];//后面数向后平移一位
                    }
                    arr[j] = temp;
                }
            }
        }
    }

    //方法二：将待插入数据从后向前比较，比较一次，满足条件就后移一位，继续比较，直到找到待插入位置，插入待插入数据，此方法，比较和移动是同时进行的
    public static void insertSort1(int[] arr){
        for (int i = 1;i < arr.length;i++){
            int temp = arr[i];//待插入数据
            int j = i - 1;
            for (;j >= 0 && (temp < arr[j]);j--){//与前面数据比较
                    arr[j + 1] = arr[j];
            }

            arr[j + 1] = temp;
        }
    }

    //方法三：链表
    public static void insertLinked(int[] arr){
        int size = arr.length;
        Linkedlist node = new Linkedlist(-1);//头结点
        for (int i = 0;i < size;i++){
            Linkedlist temp = node;
            while (true){
                Linkedlist temp1 = new Linkedlist(arr[i]);
                if (temp.next == null){
                        temp.next = temp1;
                        break;
                }
                if (temp1.a < temp.next.a){
                        temp1.next = temp.next;
                        temp.next = temp1;
                        break;
                }
                temp = temp.next;
            }
        }
        Linkedlist temp2 = node.next;
        for (int i = 0;i < size;i++){
            arr[i] = temp2.a;
            temp2 = temp2.next;
        }
    }
    public static void show(int[] arr){
        for (int i = 0;i < arr.length;i++){
            System.out.print(arr[i] + " ");
        }
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88