当前位置： 移动技术网 > IT编程>开发语言>Java > 排序算法之选择排序

排序算法之选择排序

2020年07月22日  | 移动技术网IT编程  | 我要评论

选择排序

核心思想

从数组中找出最小的元素，与第一个元素交换，这个时候已经确定了其位置，再从剩余的元素中找出最小的元素与剩余元素中的第一个交换，直到剩余元素只剩下一个时，排序结束。
在这里插入图片描述

性能分析

对于长度为N的数组，选择排序需要大约N2/2次比较和N次交换。所以时间复杂度为O(n2)，空间复杂度为O(1)。

特点

1、运行时间与输入无关
已经有序的数组或者主键全部相同的数组和一个元素随机排列的数组所用的排序时间一样长。
2、数据移动是最少的
每次交换都会更改两个数组元素的值，因此选择排序用了N次交换，交换次数与数组长度是线性关系。

代码实现

public static void selectionSort(Comparable[] a) {

        for (int i = 0; i < a.length; i++) {
            int min = i;
            for (int j = i + 1; j < a.length; j++) {
            	//找到最小元素，与未排序数组中第一个元素交换
                if (a[min].compareTo(a[j]) > 0) {
                    Comparable temp = a[min];
                    a[min] = a[j];
                    a[j] = temp;
                }
            }
        }
    }

测试：

public class SortingAlgorithm {
    public static void main(String[] args) {
        SortingAlgorithm sort = new SortingAlgorithm();

        Comparable[] arr = {4, 2, 1, 6, 9, 7};
        selectionSort(arr);
        System.out.println(Arrays.toString(arr));
    }
}

运行结果：
在这里插入图片描述

本文地址：https://blog.csdn.net/weixin_44431550/article/details/107485777

您可能感兴趣的文章:

如对本文有疑问， 点击进行留言回复！！

相关文章:

验证码：
最近更新的文章
大家感兴趣的文章
移动技术网