排序算法之選擇排序1——直接選擇排序

直接選擇排序算法是一種簡單的排序算法，它的時間複雜度為O（N^2），空間複雜度為O（1），它的時間複雜度與初始狀态無關，是以總是做一些“重複性”的動作，并且它是不穩定的。

直接選擇排序算法的實作：

template <typename T>
void SelectSort(T *array, const int size)
{
    assert(NULL != array && size > );
    if(size == )
        return;
    for(int i = ; i < (int)size-; i++)
    {
        int sub = i;
        for(int j = i+; j < (int)size; j++)
            if(Less<T>()(array[j], array[sub]))
                sub = j;
        if(sub != i)
            swap(array[i], array[sub]);
    }
}
           

測試代碼：

void test4()
{
    int arr[] = {  };
    int sz = sizeof(arr) / sizeof(arr[]);
    srand((unsigned int)time());
    for(int i = ; i < sz; i++)    //Assign values with random numbers
    {
        arr[i] = rand() % sz;
    }
    for(int i = ; i < sz; i++)    //print array
        cout << arr[i] << " ";
    cout << endl << endl << endl << "sort:" << endl;
    SelectSort(arr, sz);
    for(int i = ; i < sz; i++)    //print array
        cout << arr[i] << " ";
    cout << endl;
    for(int i = ; i < sz; i++)  //check that the sort is correct
    {
        if(Less<int>()(arr[i], arr[i-]))
            cout << "insert sort error! " << i << endl;
    }
}
           

測試結果：

排序正确！