FilesExpand file tree

 master

/

InsertSort.java

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

47 lines (41 loc) · 910 Bytes

 master

/

InsertSort.java

Top

File metadata and controls

• Code
• Blame

47 lines (41 loc) · 910 Bytes

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

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

/**

* @author LZD 2018/02/27

*/

/*

* 插入排序

* 时间复杂度：

* 是和数据的状况有关的算法流程，一律按照最差状况计算

* 最优：有序序列：O(N)

* 最差：逆序序列：O(N^2)

* 所以时间复杂度为：O(N^2)

*/

package class01;

public class InsertSort {

public static void sort(int[] arr) {

if(arr == null || arr.length < 2)

return;

//i位置上的数就是这次排序要排的数

for(int i = 1;i < arr.length;i++) {

for(int j = i-1;j >= 0 && arr[j] > arr[j+1];j--) {

swap(arr, j, j+1);

}

}

}

public static void swap(int[] arr, int i, int j) {

int tmp = arr[i];

arr[i] = arr[j];

arr[j] = tmp;

/*

* 或使用位运算进行交换

* arr[i] = arr[i] ^ arr[j];

* arr[j] = arr[i] ^ arr[j];

* arr[i] = arr[i] ^ arr[j];

*/

}

public static void main(String[] args) {

int[] arr = new int[] {2,3,1,6,5,9};

sort(arr);

for(int i = 0;i < arr.length;i++)

System.out.println(arr[i]);

}

}