选择排序实现C++

目录54321

选择排序的简介

选择排序的原理

动图演示

代码实现

补充

选择排序的简介

选择排序平均时间复杂度O(N^2)，还可以进行优化，可以在一次数组遍历中同时找到最大值和最小值，这样就减少了数组的循环次数，效率提高。

选择排序的原理

选择排序（Selection sort）是一种简单直观的排序算法，和冒泡时间复杂度相似。它的工作原理是：第一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后再从剩余的未排序元素中寻找到最小（大）元素，然后放到已排序的序列的开头。以此类推，直到全部待排序的数据元素的个数为零，选择排序是一个最好和最坏都是O(n²)时间复杂度的排序方法,比较的次数与序列的初始状态无关,总的比较次数在都在(n-1) (n-2) (n-3) ... 1 =n * (n-1) / 2次,交换次数为O(n),最好为0,即序列本身有序,最坏为n-1次。

动图演示

【

代码实现

1.  
   #include <bits/stdc .h>
2.  
   using namespace std;
3.  
   int a[10000005];
4.  
   int main()
5.  
   {
6.  
   int n;
7.  
   cin>>n;
8.  
   for(int i=1; i<=n; i )
9.  
   cin>>a[i];
10.  
    for(int i=1; i<n; i ){
11.  
    int minIndex = i ;
12.  
    for(int j= i 1 ; j<= n ; j )
13.  
    if(a[j]<a[minIndex])
14.  
    minIndex = j;
15.  
    swap( a[i] , a[minIndex] );
16.  
    }
17.  
    for(int i=1; i<=n; i )
18.  
    cout<<a[i]<<" ";
19.  
    return 0;
20.  
    }

例题

说了这么多，这里有一道例题，

有n个不同的数保存在数组a[1...n]。现在进行n-1轮操作。第1轮就是把a[1]至a[n]当中最小的数交换到a[1]。第2轮就是把a[2]至a[n]当中最大的数交换到a[n]，第3轮就是把a[2]至a[n-1]当中最小的数交换到a[2],第4轮就是把a[3]至a[n-1]当中最大的数交换到a[n-1]，......按照这个规律，经过n-1轮选择交换后，a数组已经是从小都大排好顺序了。每一轮操作后，你都要输出a数组。

输入/输出例子1

输入：

 5

 3 5 4 2 1

输出：

1 5 4 2 3

1 3 4 2 5

1 2 4 3 5

1 2 3 4 5

代码

1.  
   #include<bits/stdc .h>
2.  
   using namespace std;
3.  
   int x[1000];
4.  
   int main(){
5.  
   int n;
6.  
   cin>>n;
7.  
   for(int i=1;i<=n;i )
8.  
   cin>>x[i];
9.  
   for(int i=1;i<n;i )
10.  
    {
11.  
    if(i%2==1)
12.  
    {
13.  
    int minid=i;
14.  
    for(int j=i;j<=n;j )
15.  
    if(x[minid]>x[j])
16.  
    minid=j;
17.  
    swap(x[i-i/2],x[minid]);
18.  
    }
19.  
    else
20.  
    {
21.  
    int maxid=i-i/2 1;
22.  
    for(int j=i;j<=n-i/2 1;j )
23.  
    if(x[maxid]<x[j])
24.  
    maxid=j;
25.  
    swap(x[n-i/2 1],x[maxid]);
26.  
    }
27.  
    for(int j=1;j<=n;j )
28.  
    cout<<x[j]<<" ";
29.  
    cout<<endl;
30.  
    }
31.  
     
32.  
    return 0;
33.  
    }

补充

为了使我们更好的观察选择排序的过程，下面的程序可以将每轮选择输出。

1.  
   #include <bits/stdc .h>
2.  
   using namespace std;
3.  
   int a[105];
4.  
   int main()
5.  
   {
6.  
   int n;
7.  
   cin>>n;
8.  
   for(int i=1; i<=n; i )
9.  
   cin>>a[i];
10.  
    for(int i=1; i<n; i ){
11.  
    int minIndex = i ;
12.  
    for(int j= i 1 ; j<= n ; j )
13.  
    if(a[j]<a[minIndex])
14.  
    minIndex = j;
15.  
    swap( a[i] , a[minIndex] );
16.  
    for(int i=1; i<=n; i )
17.  
    cout<<a[i]<<" ";
18.  
    cout<<endl;
19.  
    }
20.  
    return 0;
21.  
    }

输入：

4

4 1 2 3

输出：

 1 4 2 3

 1 2 4 3

 1 2 3 4

二，优化

由于可以在一次数组遍历中同时找到最大值和最小值，这样就减少了数组的循环次数，效率提高。

但由于怎么做只能把时间复杂度缩小为O((N/2)^2)，如果正的要追求更快的时间复杂度的话，可以用快速排序、堆排序、归并排序这些时间复杂度为O(N log N)的算法。优化程序会放到这个专栏的另外一片文章。

这篇好文章是转载于：学新通技术网