开发喵星球

关卡2:选择排序(Selection Sort)

pPeHp90.png pPeHkB4.png

本文内容是对选择排序的梳理和总结,本文内容包括:

排序算法十大经典方法

  1. 冒泡排序:比较相邻元素并交换,每一轮将最大的元素移动到最后。
  2. 选择排序:每一轮选出未排序部分中最小的元素,并将其放在已排序部分的末尾。
  3. 插入排序:将未排序部分的第一个元素插入到已排序部分的合适位置
  4. 希尔排序:改进的插入排序,将数据分组排序,最终合并排序
  5. 归并排序:将序列拆分成子序列,分别排序后合并,递归完成
  6. 快速排序:选定一个基准值,将小于基准值的元素放在左边,大于基准值的元素放在右边,递归排序
  7. 堆排序:将序列构建成一个堆,然后一次将堆顶元素取出并调整堆
  8. 计数排序:统计每个元素出现的次数,再按照元素大小输出
  9. 桶排序:将数据分到一个或多个桶中,对每个桶进行排序,最后输出
  10. 基数排序:按照元素的位数从低到高进行排序,每次排序只考虑一位

选择排序(Selection sort)

选择排序是一种简单直观的排序算法,无论什么数据进去都是 O(n²) 的时间复杂度。所以用到它的时候,数据规模越小越好。唯一的好处可能就是不占用额外的内存空间了吧。它的工作原理:首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置,然后,再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾。以此类推,直到所有元素均排序完毕。

算法步骤

  1. 首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置
  2. 再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾。
  3. 重复第 2 步,直到所有元素均排序完毕。

图解算法

如果下图不动,点击这里查看在线的图解

代码实现

/**
 * 选择排序
 */
public static int[] selectionSort(int[] arr) {
    for (int i = 0; i < arr.length - 1; i++) {
        int minIndex = i;
        for (int j = i + 1; j < arr.length; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }
        if (minIndex != i) {
            int tmp = arr[i];
            arr[i] = arr[minIndex];
            arr[minIndex] = tmp;
        }
    }
    return arr;
}

算法分析

   
分类:数据结构和算法 作者:开发喵 发表于:2023-08-11 12:51:52 阅读量:114
<<   >>


powered by kaifamiao