简单选择排序

点击打开在线编译器,边学边练

1.复杂度与稳定性

算法时间复杂度

最坏情况:O(n^2)

最好情况:O(1)           //即不需要排序,本身已是正序

平均情况:O(n^2)

 

空间复杂度:S(n)=O(1)

 

稳定性:不稳定排序

 

2.过程介绍(以顺序为例)

1.我们设置两个记录i和j,i自数组第一个元素开始,j自i+1个元素开始。

2.接着j遍历整个数组,选出整个数组最小的值,并让这个最小的值和i的位置交换(如果i选择的元素是最小的则不需要交换),我们称这个过程为一趟选择排序。

3.i选中下一个元素(i++),重复进行每一趟选择排序。

4.持续上述步骤,使得i到达n-1处,即完成排序 。


3.图示过程:

以数据{2,10,9,4,8,1,6,5}为例

开始数据

2

10

9

4

8

1

6

5

第一趟

1

10

9

4

8

2

6

5

第二趟

1

2

9

4

8

10

6

5

第三趟

1

2

4

9

8

10

6

5

第四趟

1

2

4

5

8

10

6

9

第五趟

1

2

4

5

6

10

8

9

第六趟

1

2

4

5

6

8

10

9

第七趟

1

2

4

5

6

8

9

10

如图所使,每次交换的数据使用红颜色标记出,已经排好序的数据使用蓝底标注,

 

每一趟从待排序的数据元素中选出最小的一个元素,顺序放在已排好序的数列的最后,直到全部待排序的数据元素排完,我们只需要进行n-1趟排序即可,因为最后剩下的一个数据一定是整体数据中最大的数据。

4.代码实现:

#include<iostream>
using namespace std;
void select_sort(int a[],int n){
    int temp;
    for(int i=0;i<n-1;i++){
        temp=i;      //利用一个中间变量temp来记录需要交换元素的位置
        for(int j=i+1;j<n;j++){
            if(a[temp]>a[j]){   //选出待排数据中的最小值
                temp=j;  
            }
        }
        swap(a[i],a[temp]); //交换函数
    }
} 
int main(){
    int a[8]={2,10,9,4,8,1,6,5};
    int n=8;
    select_sort(a,n);
    for(int i=0;i<n;i++){
        cout<<a[i]<<' ';
    }
    return 0;
}

相比冒泡排序的不断交换,简单选择排序(simple selection sort)是等到合适的关键字出现后再进行交换,并且移动(交换)一次就可以达到一次冒泡的效果。


上一课:冒泡排序 下一课:直接插入排序
第一章 数据结构入门
第二章 链表
第三章 栈
第四章 队列
第五章 从C语言到C++
第六章 串,数组,矩阵,广义表
第七章 树
第八章 图
第九章 算法—查找
第十章 算法—排序
第十一章 算法&竞赛,思维培养
第十二章 后记