选择排序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