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