选择排序—简单选择排序

2018-09-19

思路：在要排序的一组数中，选出最小（或者最大）的一个数与第1个位置的数交换；然后在剩下的数当中再找最小（或者最大）的与第2个位置的数交换，
依次类推，直到第n-1个元素（倒数第二个数）和第n个元素（最后一个数）比较为止。

public static void main(String[] args) {
        int arr[] = {3, 5, 7, 2, 4, 9, 1, 6, 10, 8};
        System.out.println("排序前:");
        System.out.println(Arrays.toString(arr));
        selectSort(arr);
        System.out.println("排序后:");
        System.out.println(Arrays.toString(arr));
    }

private static void selectSort(int[] arr) {
        for (int i=0; i<arr.length; i++){
            int min = i;
            for(int j=i+1; j<arr.length; j++){//找到最小值下标
                if(arr[min] > arr[j])
                    min=j;
            }
            swap(arr, min, i);
        }
    }

private static void swap(int[] arr, int k, int i){
        if (i == k) {
            return;
        }
        int temp = arr[i];
        arr[i] = arr[k];
        arr[k] = temp;
    }

改进--二元选择排序

思路：简单选择排序，每趟循环只能确定一个元素排序后的定位。
我们可以考虑改进为每趟循环确定两个元素（当前趟最大和最小记录）的位置，从而减少排序所需的循环次数。
改进后对n(n>=11)个数据进行排序，最多只需进行[n/2]趟循环即可。