流年似水博客开通了,本站主要是写关于Web和大数据方面内容,正在更新中,欢迎大家光临!
  1. 文章:97 篇
  2. 总浏览:33,997 次
  3. 评论:22条
  4. 最后更新:2020-06-08
  5. 分类目录:39 个

Java之选择排序详解

Java l, xy 152℃ 0评论

Java之选择排序详解

前言

     前面写了冒泡排序、插入排序,这里在写一下一样作为简单排序的选择排序。选择排序就是在一次遍历过程中找到最小元素的位置(下标),然后把改元素放到数组的首要位置。

一、 选择排序思想

选择排序的思想也很简单:

  1. 从待排序序列中,找到关键字最小的元素;起始假定第一个元素为最小
  2. 如果最小元素不是待排序序列的第一个元素,将其和第一个元素互换;
  3. 从余下的 N - 1 个元素中,找出关键字最小的元素,重复1,2步,直到排序结束。

二 、 选择排序原理动画

三、 选择排序空间复查度、辅助空间、稳定性

  1. 选择排序的算法时间平均复杂度为O(n²)。
  2. 选择排序空间复杂度为 O(1)。
  3. 选择排序为不稳定排序。

四、 选择排序Java实现


import java.util.Arrays;
import java.util.Objects;

public class ChooseSort {

/***
* 交换数组索引1和索引2的值
* @param arr 数组
* @param index1 索引1
* @param index2 索引2
*/
public static void swap(int[] arr, int index1, int index2) {
int tmp = arr[index1];
arr[index1] = arr[index2];
arr[index2] = tmp;

}

/***
* 选择排序
* @param ints
*/
public static void chooseSort(int[] ints) {
Objects.requireNonNull(ints);

for (int i = 0; i < ints.length - 1; i++) {
// 记录最小值的下表(索引)
int minValueIndex = i;
for (int j = i + 1; j < ints.length; j++) {
// 如果最小值
if (ints[minValueIndex] > ints[j]) {
minValueIndex = j;
}
}
// 交换
swap(ints, minValueIndex, i);
}

}


public static void main(String[] args) {
int[] ints = new int[]{29, 88, 33, 20, 57, 76};
chooseSort(ints);
Arrays.stream(ints).forEach(System.out::println);
}
}

结果:

20
29
33
57
76
88

五、总结

    总的来说,选择排序的重点在每次循环过程中找到最小元素(项)的位置(下标),然后和当前循环中首位置坐交换。只要把握着这个点一般是不会错的。

但是在外层选中的终止条件一定不要写成 "int i = 0; i < ints.length - 1; i++" , 这要会出现数据下标越界。

转载请注明:流年似水 » Java之选择排序详解

喜欢 (0)or分享 (0)

Warning: copy(https://cn.gravatar.com/avatar/?s=54&d=%2Fwp-content%2Fthemes%2Fyusi1.0%2Fimg%2Fdefault.png&r=g): failed to open stream: HTTP request failed! HTTP/1.1 400 Bad Request in /usr/share/nginx/html/timewentby/wp-content/themes/yusi1.0/functions.php on line 239

Warning: copy(/wp-content/themes/yusi1.0/img/default.png): failed to open stream: No such file or directory in /usr/share/nginx/html/timewentby/wp-content/themes/yusi1.0/functions.php on line 243
发表我的评论
取消评论

表情

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址