欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

基于Java实现的选择排序算法

程序员文章站 2022-07-02 17:59:49
选择排序和冒泡排序同样是基础排序算法,现在也做个学习积累。 简述 选择排序算法较为稳定,基本上都是O(n2)的时间复杂度,规模越小排序越快,不需要占用额外空间。其实选择排序原理很简单,就是在未排序序列中找到最小(大)的元素然后放到数组前面,然后再从剩下的未排序序列中找到最小(大)的元素放在上一次找到 ......

选择排序和冒泡排序同样是基础排序算法,现在也做个学习积累。

简述

选择排序算法较为稳定,基本上都是o(n2)的时间复杂度,规模越小排序越快,不需要占用额外空间。其实选择排序原理很简单,就是在未排序序列中找到最小(大)的元素然后放到数组前面,然后再从剩下的未排序序列中找到最小(大)的元素放在上一次找到最小(大)元素的后面,以此类推完成排序。

动图演示

看下动图上的演示,就能够找出排序规律,非常之简明易懂。

基于Java实现的选择排序算法

(算法动图来源于参考资料,详细请往下翻阅)

代码实现

 1 /**
 2  * 选择排序
 3  * @param array 待排序数组
 4  * @return 已排序数组
 5  */
 6 public static int[] selectionsort(int[] array) {
 7     int len = array.length;
 8     // 如果数组长度为0或者1,都是不用排序直接返回
 9     if(len == 0 || len == 1) {
10         return array;
11     }
12     for(int i = 0; i < len - 1; i++) {
13         int minidx = i;
14         for(int j = i + 1; j < len; j++) {
15             // 找到最小的数
16             if(array[minidx] > array[j]) {
17                 // 保存最小数的索引
18                 minidx = j;
19             }
20         }
21         // 如果一轮比较下来都没有变更最小值的索引则无需调换顺序
22         if(minidx != i) {
23             int tmp = array[i];
24             array[i] = array[minidx];
25             array[minidx] = tmp;
26         }
27     }
28     return array;
29 }

算法分析

最佳情况:t(n) = o(n2 最差情况:t(n) = o(n2)  平均情况:t(n) = o(n2)

由此看出,选择算法的排序情况是很稳定的,不管输入什么样的数据都是一样的时间复杂度。

参考资料

1、https://www.cnblogs.com/guoyaohua/p/8600214.html