排序算法之简单选择排序

简单选择排序

接下来我们来简单地学习一下简单选择排序。

原理：

通过n-1次关键字之间的比较，从n-i+1个记录中找到关键字最小的记录，并和第i个记录交换。其实很好理解：在冒泡排序中，我们每次都做了交换，而这里我们不需要每次都进行交换，而是把最大的数（min记录的是最大值的下标）和第i个记录交换。

代码如下：

void simpleChooseSort(int a[],int aLength)
{
    int i,j,min;
    for (i=0; i<aLength; i++) {
        min = i;
        for (j=i+1; j<aLength; j++) {
            if (a[min]<a[j]) {
                min=j;
            }
        }
        if (i!=min) {
            swap(a, i, min);
        }
    }
}

比如说我们待排序的序列是：
{9，1，5，8，3，7，4，6，2}
也就是让数组第一个元素和后面的每个元素比较，但是比较的过程中不修改不进行交换，而是记录最大的数据的下标，然后把该最大元素与a[i]进行交换，这样便可以实现简单选择排序。
swap函数如下：

//交换位置
void swap(int a[],int i,int j)
{
    int temp = a[i];
    a[i] = a[j];
    a[j] = temp;
}

主函数如下：

int main(int argc, const char * argv[]) {

    int a[] = {12,34,9,1,5,8,3,7,4,6,2,13,42,16,23};    //length = 15
    simpleChooseSort(a, 15);


    return 0;
}

运行结果：

简单选择排序算法：42 34 23 16 13 12 9 8 7 6 5 4 3 2 1

其时间复杂的也是 O（n^2 ），虽然与冒泡排序同是O(n^2 )， 但是简单选择排序的性能还是要略优于冒泡排序的。