首页 > 编程语言 > 详细

选择排序算法

时间:2019-07-17 10:11:03      阅读:82      评论:0      收藏:0      [点我收藏+]

假设你的计算机存储了很多音乐,对于每首音乐,你都记录了其播放次数。

那么你需要将这个音乐列表按播放次数从多到少进行排序。假设这个列表的长度是 n

首先遍历这个列表,找出播放次数最多的歌曲,将其放到一个新列表的第一位,操作遍历 次数为 n

然后再次编译剩下的列表,找出播放次数最多的歌曲,把它放到排序列表的第二位,操作遍历 次数 为 n-1

以此类推操作遍历次数为 n-2;...2;1

这样最终得到一个有序列表,这就是选择排序。选择排序是一种灵巧的算法,但是速度不快。

选择排序的最终操作次数为(n-1+n-2...+2+1),也就是 n2,运行效率记做 O(n2)

选择排序虽然速度不快,但是快于冒泡,下面有研究。

// java选择排序
public static void selectionSort(int[] arr){
        int min;
        int max;
        int count = arr.length;
        for (int i = 0; i < count; i++) {
            // 初始化未排序序列中最小数据数组下标
            min = i;
            // 初始化未排序序列中最大数据数组下标
            max = count - 1;
            for (int j = i; j < count; j++) {
                // 在未排序元素中继续寻找最小元素,并保存其下标
                if(arr[min] >= arr[j]){
                    min = j;
                }
                // 在未排序元素中继续寻找最大元素,并保存其下标
                if(arr[max] <= arr[j]){
                    max = j;
                }
            }
            // 将未排序列中最小元素放到已排序列头
            if(min != i){
                int temp = arr[i];
                arr[i] = arr[min];
                arr[min] = temp;
            }
            // 将未排序列中最大元素放到已排序列尾
            if(max != count - 1){
                int temp = arr[count - 1];
                arr[count - 1] = arr[max];
                arr[max] = temp;
            }
            count--;
        }
    }

 

选择排序算法

原文:https://www.cnblogs.com/zeussbook/p/11198321.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!