資料結構-選擇排序法-有解無憂

　　選擇排序法可使用兩種方式排序，一為在所有的資料中，當由大到小排序，則將最大值放入第一個位置；若由小至大排序時，則將最大值放入位置末端，

　　例如當 N 個資料需要由小到大排序時，首先以第一個位置的資料，依次向 2、3、4......N 個位置的資料做比較，如果資料小于或者等于其中一個位置，則兩個位置的資料不變；若大于其中一個位置，則兩個位置的資料互換，互換后的第一個位置新資料，繼續找下一個位置資料作比較，直到位置最末端，此時第一個位置的資料即為此排序數列的最小值，接下來選擇第二個位置資料，依次向 3、4、5......N 個位置的資料作比較，將剩余排序的最小值放入第二個位置，依循此方法直到 (N-1) 個位置最小值找到后，就完成選擇排序法由小至大的排序，

演算程序

選擇法分析

無論是最壞情況，最佳情況還是平均情況都需要找到最小值（最大值），因此其比較次數為 (n-1)+(n-2)+(n-3)+...+3+2+1=n(n-1)/2 次；時間復雜度為 O(n^2)，
由于選擇排序是以最小或最大值直接與最前方未排序的鍵值交換，資料排列順序很有可能被改變，故不是穩定排序法，
只需一個額外的空間，所以空間復雜度為最佳，
此排序法適用于資料量小或有部分資料已經過排序的情況，

example1

/**
 * 選擇排序法
 *
 */
public class SelectionSort {

    public static void main(String[] args) {
        int data[] = new int[] {9, 7, 5, 3, 4, 6};
        System.out.print("原始資料：");
        showData(data);
        select(data);
        System.out.print("排序后的資料：");
        showData(data);
    }
    
    private static void select(int data[]) {
        int i, j, tmp;
        for (i = 0; i < data.length - 1; i++) {
            for (j = i + 1; j < data.length; j++) {
                if (data[i] > data[j]) {
                    tmp = data[i];
                    data[i] = data[j];
                    data[j] = tmp;
                }
            }
            showData(data);
        }
    }
    
    private static void showData(int data[]) {
        for (int i = 0; i < data.length; i++) {
            System.out.printf("[%d]", data[i]);
        }
        System.out.printf("%n");
    }

}

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/62075.html

標籤：其他

上一篇：【LeetCode】21.合并兩個有序鏈表

下一篇：資料結構-插入排序法