选择排序Java代码实现

java

插入排序复习:

插入排序特点:插入排序是基于比较的排序,时间复杂度为O(n^2),额外空间复杂度为O(1),实现可做到稳定

核心思想:选择排序的核心思想为,遍历无序数组,每次将最小的数放置在已排好序的数组的尾端,遍历至数组倒数第二位时,数组已排好序。

以下为插入排序代码:

  1 package com.cmbc.test1;

2

3 import java.util.Arrays;

4

5 /**

6 * 选择排序

7 * @author itqcy

8 *

9 */

10 public class SelectionSort {

11

12 public static void selectionSort(int[] arr){

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

14 return;

15 }

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

17 int min = i;

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

19 min = arr[min]<arr[j]?min:j;

20 }

21 swap(arr,i,min);

22 }

23 }

24

25

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

27 int tmp = arr[i];

28 arr[i] = arr[j];

29 arr[j] = tmp;

30 }

31

32 public static void printArray(int[] arr) {

33 if (arr == null) {

34 return;

35 }

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

37 System.out.print(arr[i] + " ");

38 }

39 System.out.println();

40 }

41

42 public static int[] copyArray(int[] arr) {

43 if (arr == null) {

44 return null;

45 }

46 int[] res = new int[arr.length];

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

48 res[i] = arr[i];

49 }

50 return res;

51 }

52

53 public static boolean isEqual(int[] arr1,int[] arr2){

54 if((arr1==null&&arr2!=null)||(arr1!=null&&arr2==null)){

55 return false;

56 }

57 if(arr1==null&&arr2==null){

58 return true;

59 }

60 if(arr1.length!=arr2.length){

61 return false;

62 }

63 for(int i = 0;i<arr1.length;i++){

64 if(arr1[i]!=arr2[i]){

65 return false;

66 }

67 }

68 return true;

69 }

70

71 public static int[] generateRandomArray(int maxSize,int maxValue){

72 int[] arr = new int[(int)((maxSize+1)*Math.random())];

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

74 arr[i] = (int)((maxValue+1)*Math.random())-(int)((maxValue+1)*Math.random());

75 }

76 return arr;

77 }

78 public static void main(String[] args) {

79 int testTime = 500000;

80 int maxSize = 100;

81 int maxValue = 100;

82 boolean succeed = true;

83 for (int i = 0; i < testTime; i++) {

84 int[] arr1 = generateRandomArray(maxSize, maxValue);

85 int[] arr2 = copyArray(arr1);

86 selectionSort(arr1);

87 Arrays.sort(arr2);

88 if (!isEqual(arr1, arr2)) {

89 succeed = false;

90 printArray(arr1);

91 printArray(arr2);

92 break;

93 }

94 }

95 System.out.println(succeed ? "选择排序结果正确!" : "选择排序结果错误");

96

97 int[] arr = generateRandomArray(maxSize, maxValue);

98 printArray(arr);

99 selectionSort(arr);

100 printArray(arr);

101 }

102

103 }

以上是 选择排序Java代码实现 的全部内容, 来源链接: utcz.com/z/393288.html

回到顶部