数据结构之选择排序

基本思想:在要排序的一组数中,选出最小的一个数与第一个位置的数交换;然后在剩下的数当中再找最小的与第二个位置的数交换,

如此循环到倒数第二个数和最后一个数比较为止。

选择排序(Selection sort)也是一种简单直观的排序算法。

选择排序是通过遍历每一次都找出最小(最大)的数查找出来放在第一位,然后从第二个元素开始重复上边的动作即可完成排序。选择排序的时间复杂度为哦(n^2),且为非稳定排序算法。

算法步骤

1)首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置

2)再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾。

3)重复第二步,直到所有元素均排序完毕

算法实现(java):

public class ChoseSort {
    public static void main(String[] args) {
        int[] a={5,2,0,7,1,9};
        choseSort(a);
        for(int i=0;i<a.length;i++){
            System.out.println(a[i]);
        }
    }
    public static void choseSort(int[] a){
        int i,j,lowindex;
        for(i=0;i<a.length;i++){
             lowindex=i;//将i设为最小值,然后从i+1开始遍历,有小于的交互
            j=i+1;
            while(j<a.length){
                if(a[lowindex]>a[j]){
                    lowindex=j;
                }
                j++;
            }
            int temp=a[i];
            a[i]=a[lowindex];
            a[lowindex]=temp;

        }
    }
}

算法分析:

时间复杂度:

简单选择排序的主要优点与数据移动有关。如果某个元素位于正确的最终位置上,则它不会被移动。
交换次数而言,在最好情况下,交换次数为0;在最坏的情况下,交换次数为n-1
无论最好最坏情况,其比较次数都是一样多的,基于最终的排序时间是比较和交换的次数总和,其时间复杂度为Θ(n2)。
在所有的完全依靠交换去移动元素的排序方法中,选择排序属于非常好的一种。

空间复杂度:

很明显,其空间复杂度为Θ(1)。

稳定性:

选择排序是不稳定的


文章作者: 高虎
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 高虎 !
 上一篇
数据结构之快速排序 数据结构之快速排序
基本思想:选择一个基准元素,通常选择第一个元素或者最后一个元素,通过一趟扫描,将待排序列分成两部分,一部分比基准元素小,一部分大于等于基准元素,此时基准元素在其排好序后的正确位置,然后再用同样的方法递归地排序划分的两部分。 快速排序是由东尼
下一篇 
数据结构之插入排序 数据结构之插入排序
基本思想:在要排序的一组数中,假设前面(n-1)[n>=2] 个数已经是排好顺序的,现在要把第n个数插到前面的有序数中,使得这n个数也是排好顺序的。如此反复循环,直到全部排好顺序。 插入排序是最简单的排序算法,插入排序最差的复杂度是
  目录