排序算法---直接選擇排序算法

選擇排序算法的過程：

從所有序列中先找到最小的，然後放到第一個位置。之後再看剩餘元素中最小的，放到第二個位置……以此類推，就可以完成整個的排序工作了。可以很清楚的發現，選擇排序是固定位置，找元素。

尋找最小的元素需要一個循環的過程，而排序又是需要一個循環的過程。算法的時間複雜度也是O(n*n)。

一共需要n次位置的交換和n^2/2次比較。空間複雜度是O(1).

選擇排序算法是不穩定的，比如原序列為：2、2、4、3、1。排序後改變了原來相同元素（即元素2）的相對位置。

c++實作代碼：

#include <iostream>

using namespace std;
void selectRank(int array[], int length)
{
    for(int i=; i<length; i++)
    {
        int index = i;
        for(int j=i+; j<length; j++)  //主要是為了找到剩餘元素的最小，需要n^2/2次比較
        {
            if(array[j]<array[index])
            {
                index=j;    //尋址操作
            }
        }
        //位置交換直接用STL的swap函數。
        swap(array[i],array[index]);
    }
}

int main()
{
    int data[] = {, , , , };
    int size = sizeof(data)/sizeof(int);
    selectRank(data, size);
    for(int i=; i<size; i++)
    {
        cout << data[i]<<" ";
    }
    return ;
}
           

運作結果：

java版本：

public class selectSortTest {
    static void selectSort(int[] a) {
        for (int i = ; i < a.length; i++) {//外層循環存放最小元素
            int index = i;
            for (int j = i + ; j < a.length; j++) {//内層循環尋找剩餘元素中的最小的元素
                if (a[j] < a[index]) {
                    index = j;
                }
            }
            swap(a,i, index);//把較小的數放到目前的位置上
        }
    }

    //java參數傳遞都是采用的值傳遞方式
    public static void swap(int[] data,  int a, int b) {
        int tmp=data[a];
        data[a]=data[b];
        data[b]=tmp;
    }

    public static void main(String[] args) {
        int[] array = { ,,,,,,, };
        selectSort(array);
        for (int i = ; i < array.length; i++) {
            System.out.print(array[i]+"\t");
        }       
    }

}