Java：选择排序

目录

直接选择排序

 堆排序

---

基本思想：

每一次从待排序的数据元素中选出最小(或最大)的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。

直接选择排序

思路1：

在元素集合array[i]--array[n-1]中选择关键码最大(小)的数据元素若它不是这组元素中的最后一个(第一个)元素，则将它与这组元素中的最后一个（第一个）元素交换在剩余的array[i]--array[n-2]（array[i+1]--array[n-1]）集合中，重复上述步骤，直到集合剩余1个元素

 

    //选择排序    /**     * 时间复杂度：O(N^2) 和数据 是否有序无关     * 空间复杂度：O(1)     * 稳定性：不稳定     * @param array     */    public static void selectSort(int[] array){        for (int i = 0; i < array.length; i++) {            int minIndex = i;            for (int j = i+1; j < array.length; j++) {                if(array[j] < array[minIndex]){                    minIndex = j;                }            }            swap(array,i,minIndex);        }    }    private static void swap(int[] array, int i, int minIndex) {        int tmp = array[i];        array[i] = array[minIndex];        array[minIndex] = tmp;    }

 思路2：

定义left和right分别去找最大值和最小值对应的下标找到后进行交换一开始最大值和最小值下标均为left，为0

 

private static void swap(int[] array, int i, int minIndex) {    int tmp = array[i];    array[i] = array[minIndex];    array[minIndex] = tmp;}public static void selectSort1(int[] array){    int left = 0;    int right = array.length-1;    while(left < right){        int minIndex = left;        int maxIndex = left;        for (int i = left+1; i <= right; i++) {            if(array[i] < array[minIndex]){                minIndex = i;            }            if(array[i] > array[maxIndex]){                maxIndex = i;            }        }        swap(array, left, minIndex);        //确保最大值的位置，最大值正好是 left 下标        //此时把最大值换到了minIndex下标        if(maxIndex == 0){            maxIndex = minIndex;        }        swap(array, right, maxIndex);        left++;        right--;    }}

 堆排序

这里我们选择大根堆进行输出，首先通过向下调整来进行创建大根堆。

public static void createHeap(int[] array){    for (int parent = (array.length-1-1)/2; parent >= 0; parent--) {        siftDown(array,parent,array.length);//向下调整，创建大根堆    }}public static void siftDown(int[] array, int parent, int length) {    int child = 2*parent+1;    while(child < length){        if(child + 1 < length && array[child] < array[child +1]){            child++;        }        if(array[child] > array[parent]){            swap(array, child, parent);            parent = child;            child = 2*parent+1;        }else{            break;        }    }

 然后再对大根堆进行输出，完整代码如下：

public static void heapSort(int[] array){    createHeap(array);    int end  = array.length-1;    while(end > 0){        swap(array, 0 ,end);        siftDown(array, 0,end);        end--;    }}public static void createHeap(int[] array){    for (int parent = (array.length-1-1)/2; parent >= 0; parent--) {        siftDown(array,parent,array.length);//向下调整，创建大根堆    }}public static void siftDown(int[] array, int parent, int length) {    int child = 2*parent+1;    while(child < length){        if(child + 1 < length && array[child] < array[child +1]){            child++;        }        if(array[child] > array[parent]){            swap(array, child, parent);            parent = child;            child = 2*parent+1;        }else{            break;        }    }}