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之选择排序详解