简单选择排序

in 数据结构 with 1 comment

选择排序(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)其实就排好序了。

动图演示:

6tjTM2np45.gif

算法分析

时间复杂度:

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

$$ 比较次数 \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}

复杂性:

简单

归位:

全局有序。

Responses
  1. study 一起学习 go

    Reply