美文网首页
重温算法之选择排序

重温算法之选择排序

作者: Leon_hy | 来源:发表于2017-03-21 17:32 被阅读1次

选择排序原理 每一趟从待排序的记录中选出最小的元素,顺序放在已排好序的序列最后,直到全部记录排序完毕。也就是:每一趟在n-i+1(i=1,2,…n-1)个记录中选取关键字最小的记录作为有序序列中第i个记录。基于此思想的算法主要有简单选择排序、树型选择排序和堆排序。(这里只介绍常用的简单选择排序)

  • 简单选择排序的基本思想:给定数组:int[] arr={里面n个数据};第1趟排序,在待排序数据arr[1]arr[n]中选出最小的数据,将它与arrr[1]交换;第2趟,在待排序数据arr[2]arr[n]中选出最小的数据,将它与r[2]交换;以此类推,第i趟在待排序数据arr[i]~arr[n]中选出最小的数据,将它与r[i]交换,直到全部排序完成。

  • 举例:数组 int[] arr={5,2,8,4,9,1};


第一趟排序: 原始数据:5 2 8 4 9 1

最小数据1,把1放在首位,也就是1和5互换位置,

排序结果:1 2 8 4 9 5


第二趟排序:

第1以外的数据{2 8 4 9 5}进行比较,2最小,

排序结果:1 2 8 4 9 5


第三趟排序:

除1、2以外的数据{8 4 9 5}进行比较,4最小,8和4交换

排序结果:1 2 4 8 9 5


第四趟排序:

除第1、2、4以外的其他数据{8 9 5}进行比较,5最小,8和5交换

排序结果:1 2 4 5 9 8


第五趟排序:

除第1、2、4、5以外的其他数据{9 8}进行比较,8最小,8和9交换

排序结果:1 2 4 5 8 9


注:每一趟排序获得最小数的方法:for循环进行比较,定义一个第三个变量temp,首先前两个数比较,把较小的数放在temp中,然后用temp再去跟剩下的数据比较,如果出现比temp小的数据,就用它代替temp中原有的数据。具体参照后面的代码示例,相信你在学排序之前已经学过for循环语句了,这样的话,这里理解起来就特别容易了。

代码实例

    public class SelectionSort {
    public static void main(String[] args) {
        int[] arr={1,3,2,45,65,33,12};
        System.out.println("交换之前:");
        for(int num:arr){
            System.out.print(num+" ");
        }        
        //选择排序的优化
        for(int i = 0; i < arr.length - 1; i++) {// 做第i趟排序
            int k = i;
            for(int j = k + 1; j < arr.length; j++){// 选最小的记录
                if(arr[j] < arr[k]){ 
                    k = j; //记下目前找到的最小值所在的位置
                }
            }
            //在内层循环结束,也就是找到本轮循环的最小的数以后,再进行交换
            if(i != k){  //交换a[i]和a[k]
                int temp = arr[i];
                arr[i] = arr[k];
                arr[k] = temp;
            }    
        }
        System.out.println();
        System.out.println("交换后:");
        for(int num:arr){
            System.out.print(num+" ");
        }
    }

运行结果

Paste_Image.png

选择排序的时间复杂度:简单选择排序的比较次数与序列的初始排序无关。 假设待排序的序列有 N 个元素,则比较次数永远都是N (N - 1) / 2。而移动次数与序列的初始排序有关。当序列正序时,移动次数最少,为 0。当序列反序时,移动次数最多,为3N (N - 1) / 2。所以,综上,简单排序的时间复杂度为 O(N2)。

相关文章

  • 重温算法之选择排序

    选择排序原理 每一趟从待排序的记录中选出最小的元素,顺序放在已排好序的序列最后,直到全部记录排序完毕。也就是:每一...

  • 算法-选择排序

    算 法:选择排序算法时间复杂度: 选择排序算法概述 选择排序伪代码 选择排序实现 选择排序算法概述 排序算法有许...

  • 3.1-选择排序-简单选择排序

    参考链接 选择排序:简单选择排序(Simple Selection Sort) 白话经典算法系列之四 直接选择排序...

  • 算法理解之排序-选择排序

    算法理解之排序-选择排序 选择排序是一种简单直观的排序算法, 以当前点为锚点, 向后依次进行比较所有未排序元素, ...

  • 算法4:插入排序和选择排序算法的比较

    排序算法列表电梯: 选择排序算法:详见 《算法4》2.1 - 选择排序算法(Selection Sort), Py...

  • 经典排序算法总结

    经典排序算法集锦 冒泡法 排序算法入门之冒泡排序 排序算法入门之冒泡排序优化

  • JS实现排序算法

    原文:常见排序算法之JavaScript实现 - 知乎 目录 冒泡排序 选择排序 插入排序 合并排序 快速排序 1...

  • 算法之 排序算法之 选择排序

    简介 插入式排序属于内部排序法,是对于欲排序的元素以插入的方式找寻该元素的适当位置,以达到排序的目的。 实现步骤 ...

  • 重温算法之快速排序

    原文地址:http://www.jb51.net/article/79020.htm 概述 快速排序是由东尼·霍尔...

  • 『算法』之 初级排序算法总结

    本篇文章同时收录在我的个人博客:『算法』之 初级排序算法总结 选择排序 一种最简单的排序算法:首先,找到数组中最小...

网友评论

      本文标题:重温算法之选择排序

      本文链接:https://www.haomeiwen.com/subject/mhmgnttx.html