简单选择排序

数据结构 排序

选择排序（Selection sort）是一种简单直观的排序算法。它首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

排序思路

从无序区（R[i..n-1]）中选出最小的元素R[k]，并将它与无序区的第一个元素R[i]进行交换，这样有序区就多了一个元素，无序区少了一个元素。经过n-1趟排序，元素有序。

排序算法

以c为例,从小到大排序

#include<stdio.h>

void select_sort(int R[],int n){
    int i,j,k,tmp;
    for(i=0;i<n-1;i++){
        k=i;//k记录最小元素的位置
        for(j=i+1;j<n;j++){
            if(R[j]<R[k])k=j;
        }
        if(k!=i){//将无序区最小元素放到无序区的第一个
            tmp=R[i];
            R[i]=R[k];
            R[k]=tmp;
        }
        //打印第i趟排序后的结果
        printf("%d: ",i);
        int k;
        for (k = 0; k < n;k++){
            printf("%d ", R[k]);
        }
        printf("\n");
    }
}
int main(void){
    int a[] = {9,8,7,6,5,4,3,2,1,0};
    select_sort(a,10);
}

输出结果：

0: 0 8 7 6 5 4 3 2 1 9
1: 0 1 7 6 5 4 3 2 8 9
2: 0 1 2 6 5 4 3 7 8 9
3: 0 1 2 3 5 4 6 7 8 9
4: 0 1 2 3 4 5 6 7 8 9
5: 0 1 2 3 4 5 6 7 8 9
6: 0 1 2 3 4 5 6 7 8 9
7: 0 1 2 3 4 5 6 7 8 9
8: 0 1 2 3 4 5 6 7 8 9

注：这里第五（4）其实就排好序了。

动图演示：

算法分析

时间复杂度：

​ 无论元素的初始序列如何，所进行的关键字比较是相同的。

$$ 比较次数 \quad C(n) = \sum_{i=0}^{n-2}(n-i-1)=O(n^2) $$

移动次数：正序时为0，反序时为3（n-1），时间复杂度为O(n^2^)

空间复杂度:

只使用了i，j，k，tmp四个辅助变量，与问题规模n无关。空间复杂度为O(1)

稳定性：

因为会发生元素交换，相同元素的相对位置可能改变。这是一种不稳定的排序方法。如{5，3，2，5，4，1，8，7}

复杂性：

简单

归位：

全局有序。

本文由 ukuq 创作，采用 知识共享署名4.0 国际许可协议进行许可
本站文章除注明转载/出处外，均为本站原创或翻译，转载前请务必署名
最后编辑时间为: Jan 28, 2019 at 07:48 pm