数据结构与算法之选择排序

上一篇说了冒泡排序,这次说选择排序.选择排序与冒泡排序十分相似.冒泡排序是每一轮中的每一次都讲最小值交换.而选择排序是将每一轮中最小的值记录下标记录下来,一轮过后只交换一次,从空间上来说比冒泡排序好.

但是从时间复杂度来说是一样的.此算法的时间复杂度为O(n^2)

public static void xuanze(int[] arr) {         for (int i = 0; i < arr.length; i++) {             int min =i;             for (int x = i + 1; x < arr.length; x++) {                 if (arr[x] < arr[min]) {                     min = x;                 }             }            int temp = arr[i];             arr[i] = arr[min];             arr[min] = temp;         }     }

以下提供了一个测试方法.

public static void main(String[] args) {         Random random = new Random();         while (true) {             int length = random.nextInt(100);             int[] arr = new int[length];             int[] arr2 = new int[length];             for (int x = 0; x < length; x++) {                 int i = random.nextInt(100);                 arr[x] = i;                 arr2[x] = i;             }             xuanze(arr);             Arrays.sort(arr2);             boolean equals = Arrays.equals(arr2, arr);             System.out.println(equals);             if (!equals) {                 break;             }         }     }