快捷導(dǎo)航

Java選擇排序思路詳解

更新時(shí)間：2025年12月12日 10:15:54 作者：小川ing

這篇文章給大家介紹Java選擇排序思路詳解,本文結(jié)合實(shí)例代碼給大家介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值,需要的朋友參考下吧

直接選擇排序

思路1：

在元素集合array[i]--array[n-1]中選擇關(guān)鍵碼最大(小)的數(shù)據(jù)元素
若它不是這組元素中的最后一個(gè)(第一個(gè))元素，則將它與這組元素中的最后一個(gè)（第一個(gè)）元素交換
在剩余的array[i]--array[n-2]（array[i+1]--array[n-1]）集合中，重復(fù)上述步驟，直到集合剩余1個(gè)元素

    //選擇排序
    /**
     * 時(shí)間復(fù)雜度：O(N^2) 和數(shù)據(jù) 是否有序無(wú)關(guān)
     * 空間復(fù)雜度：O(1)
     * 穩(wěn)定性：不穩(wěn)定
     * @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分別去找最大值和最小值對(duì)應(yīng)的下標(biāo)
找到后進(jìn)行交換
一開(kāi)始最大值和最小值下標(biāo)均為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 下標(biāo)
        //此時(shí)把最大值換到了minIndex下標(biāo)
        if(maxIndex == 0){
            maxIndex = minIndex;
        }
        swap(array, right, maxIndex);
        left++;
        right--;
    }
}

堆排序

這里我們選擇大根堆進(jìn)行輸出，首先通過(guò)向下調(diào)整來(lái)進(jìn)行創(chuàng)建大根堆。

public static void createHeap(int[] array){
    for (int parent = (array.length-1-1)/2; parent >= 0; parent--) {
        siftDown(array,parent,array.length);//向下調(diào)整，創(chuàng)建大根堆
    }
}
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;
        }
    }

然后再對(duì)大根堆進(jìn)行輸出，完整代碼如下：

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);//向下調(diào)整，創(chuàng)建大根堆
    }
}
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;
        }
    }
}

到此這篇關(guān)于Java選擇排序思路詳解的文章就介紹到這了,更多相關(guān)Java選擇排序內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: