选择排序

2020-04-11

1.概念：

选择排序的主要操作是选择，其主要思想是：每趟排序在当前待排序序列中选出关键字值最小（最大）的记录，添加到有序序列中。

简单选择排序，对待排序的记录序列进行n-1遍的处理，第1遍处理是将A[1…n]中最小者与A[1]交换位置，第2遍处理是将A[2…n]中最小者与A[2]交换位置，……，第i遍处理就是通过n-i次比较，将A[i…n]中最小者与A[il交换位置。这样，经过i遍处理之后，前i个记录的位置就已经按从小到大的顺序排列好了。

简单选择排序与气泡排序的区别在：气泡排序每次比较后，如果发现顺序不对立即进行交换，而选择排序不立即进行交换，而是找出最小关键字记录后再进行交换。

2.算法性能：
时间复杂度：O(n²)
空间复杂度：O(1)，只需要一个附加程序单元用于交换
稳定性：选择排序是不稳定的排序算法，因为无法保证值相等的元素的相对位置不变，例如 [3, 4, 3, 1, 5]这个数组，第一次交换，第一个3和1交换位置，此时原来两个3的相对位置发生了变化。

3.C++程序示例：

#include<iostream>
using namespace std;
int SelectSort(int A[], int n);
int main()
{
    int A[10] = { 11,24,16,87,45,6,93,66,74,38 };
    SelectSort(A, 10);
    return 0;
}
int count1=0, count2=0;
int SelectSort(int A[], int n)
{
    int i, j, k, min, temp;
    for(i=0; i<n-1; i++)
    {
        min = i;
        for(j=i+1; j<n; j++)
        {
            count1++;
            if(A[j] < A[min])
            {
                min = j;
            }
        }
        if(min != i)
        {
            count2++;
            temp = A[min];
            A[min] = A[i];
            A[i] = temp;
        }
        for(k=0; k<n; k++)
        {
            cout << A[k] << " " ;
        }
        cout << endl;
    }
    cout << endl << "排序结果：" ;
    for(k=0; k<n; k++)
    {
        cout << A[k] << " ";
    }
    cout << endl << "一共比较了" << count1 << "次，移到了" << count2 << "次！" << endl;
}

运行结果：