排序算法之选择排序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;
    }
}
           

测试结果：

排序正确！