排序： 選擇排序

1. 基本原理

將待排序的元素分為已排序(初始為空)和未排序兩組，依次將未排序的元素中值最小的元素放入已排序的組中。

?

直接選擇排序簡單直觀，但性能略差；堆排序是一種較高效的選擇排序方法，但實現起來略微復雜。

?

2. 直接選擇排序

基本過程為：

• 在一組元素R[i]到R[n]中選擇具有最小關鍵碼的元素
• 若它不是這組元素中的第一個元素，則將它與這組元素中的第一個元素對調。
• 除去具有最小關鍵字的元素，在剩下的元素中重復第(1)、(2)步，直到剩余元素只有一個為止。

?

?

3. 代碼實現

package com.windy.sort;

import java.util.Arrays;

import org.junit.Test;

public class SelectSort {

    class DataWrap implements Comparable<DataWrap> {
        int data;
        String flag;

        public DataWrap(int data, String flag) {
            this.data = data;
            this.flag = flag;
        }

        @Override
        public String toString() {
            return data + flag;
        }

        @Override
        public int compareTo(DataWrap dw) {

            return this.data > dw.data ? 1 : (this.data == dw.data ? 0 : -1);

        }
    }

    @Test
    public void test1() {

        DataWrap[] dw = new DataWrap[] { 
                new DataWrap(-9, ""), 
                new DataWrap(1, ""),
                new DataWrap(-47, "*"),
                new DataWrap(1246, ""), 
                new DataWrap(758, ""), 
                new DataWrap(-123, ""), 
                new DataWrap(5, ""),
                new DataWrap(638, ""), 
                new DataWrap(-47, ""), 
                new DataWrap(5, "*")
                };

        System.out.println("排序前：\n" + Arrays.toString(dw));
        selectSort(dw);
        System.out.println("排序后：\n" + Arrays.toString(dw));
    }

    @Test
    public void test2() {
        DataWrap[] dw = new DataWrap[] { 
                new DataWrap(-9, ""), 
                new DataWrap(1, ""),
                new DataWrap(-47, "*"),
                new DataWrap(1246, ""), 
                new DataWrap(758, ""), 
                new DataWrap(-123, ""), 
                new DataWrap(5, ""),
                new DataWrap(638, ""), 
                new DataWrap(-47, ""), 
                new DataWrap(5, "*")
                };

        System.out.println("排序前：\n" + Arrays.toString(dw));
        selectSort2(dw);
        System.out.println("排序后：\n" + Arrays.toString(dw));
    }

    // 直接選擇排序
    private static void selectSort(DataWrap[] dw) {

        int length = dw.length;

        System.out.println("排序中...");

        for (int i = 0; i < length - 1; i++) {

            for (int j = i + 1; j < length; j++) {
                if (dw[i].compareTo(dw[j]) > 0) {
                    DataWrap temp;
                    temp = dw[i];
                    dw[i] = dw[j];
                    dw[j] = temp;
                }
            }

            System.out.println(Arrays.toString(dw));
        }

    }

    /*
     * 直接選擇排序改進版 用臨時變量記錄最小值的下標，而不是選擇馬上交換 在對比一輪結束之后，才選擇交換
     */
    private static void selectSort2(DataWrap[] dw) {
        int length = dw.length;

        System.out.println("排序中...");
        for (int i = 0; i < length - 1; i++) {
            int min = i;

            for (int j = i + 1; j < length; j++) {
                // 用最小值去對比，而不是dw[i]
                if (dw[min].compareTo(dw[j]) > 0) {
                    min = j;
                }
            }

            DataWrap temp;
            temp = dw[i];
            dw[i] = dw[min];
            dw[min] = temp;

            System.out.println(Arrays.toString(dw));
        }

    }

}

?

結果打印：

排序前：
[-9, 1, -47*, 1246, 758, -123, 5, 638, -47, 5*]
排序中...
[-123, 1, -9, 1246, 758, -47*, 5, 638, -47, 5*]
[-123, -47*, 1, 1246, 758, -9, 5, 638, -47, 5*]
[-123, -47*, -47, 1246, 758, 1, 5, 638, -9, 5*]
[-123, -47*, -47, -9, 1246, 758, 5, 638, 1, 5*]
[-123, -47*, -47, -9, 1, 1246, 758, 638, 5, 5*]
[-123, -47*, -47, -9, 1, 5, 1246, 758, 638, 5*]
[-123, -47*, -47, -9, 1, 5, 5*, 1246, 758, 638]
[-123, -47*, -47, -9, 1, 5, 5*, 638, 1246, 758]
[-123, -47*, -47, -9, 1, 5, 5*, 638, 758, 1246]
排序后：
[-123, -47*, -47, -9, 1, 5, 5*, 638, 758, 1246]

?

4. 算法效率分析

• 算法的時間效率：無論初始狀態如何，在第i趟排序中選擇最小關鍵碼的元素，需做n-i次比較，因此總的比較次數為：

? ? ? ??

?

• 算法的空間效率：空間效率很高，只需要一個附加程序單元用于交換，其空間效率為O(1)

?

• 算法的穩定性：不穩定