排序算法之选择排序

排序算法之选择排序

1.选择排序介绍

选择排序分为三种，直接选择排序、树形选择排序、堆排序。直接选择排序和堆排序是不稳定排序，树形选择排序是稳定排序。在这里介绍的是直接选择排序。其他的后面再分析。

直接选择排序算法思想：第一趟从n个元素的数据序列中选出关键字最小/大的元素并放在最前/后位置，下一趟从n-1个元素中选出最小/大的元素并放在最前/后位置。以此类推，经过n-1趟完成排序。

2.选择排序算法分析

直接选择排序的最好时间复杂度和最差时间复杂度都是O(n²)，因为即使数组一开始就是正序的，也需要将两重循环进行完，平均时间复杂度也是O(n²)。空间复杂度为O(1)，因为不占用多余的空间。直接选择排序是一种原地排序（In-place sort）并且稳定（stable sort）的排序算法，优点是实现简单，占用空间小，缺点是效率低，时间复杂度高，对于大规模的数据耗时长。

算法步骤：

• 第1趟，在待排序记录r[1]~r[n]中选出最小的记录，将它与r[1]交换；
• 第2趟，在待排序记录r[2]~r[n]中选出最小的记录，将它与r[2]交换；
• 以此类推，第i趟在待排序记录r[i]~r[n]中选出最小的记录，将它与r[i]交换，使有序序列不断增长直到全部排序完毕

3.选择排序算法从实现到优化

V1.0

template <typename T>
void SelectionSort2(T a[], int len)
{
    for(int i = 0; i < len; i++) {
        int MinIndex = i;
        for(int j = i+1; j < len; j++) {
            if(a[MinIndex] < a[j]) {
                MinIndex = j;
            }
        }
        swap(a[MinIndex], a[i]);
    }
}

4.选择排序多种场景下的测试

int main() {
    int N = 20000;

    //稀疏数组，随机性大
    int *arr1 = SortTestHelper::CreateRandomArray(N, 0, 1000000);
    SortTestHelper::testSort("SelectionSort", SelectSortFunc::SelectionSort2, arr1, N);

    //近乎有序
    int *arr2 = SortTestHelper::CreateRandomArray(N, 0, 100);
    SortTestHelper::testSort("SelectionSort", SelectSortFunc::SelectionSort2, arr2, N);

    //基本有序
    int *arr3 = SortTestHelper::CreateRandomArray(N, 0, 10);
    SortTestHelper::testSort("SelectionSort", SelectSortFunc::SelectionSort2, arr3, N);

    delete[] arr1;
    delete[] arr2;
    delete[] arr3;
    return 0;
}

测试结果：

SelectionSort : 0.424071s
SelectionSort : 0.416928s
SelectionSort : 0.410701s

根据结果表明，选择排序是一种稳定的排序算法，在随机性很大和近乎有序，有序的情况下算法的时间复杂度基本不变。但是这也是一个劣势，效率较差。