Java 排序算法 — 简单选择排序

出处:https://github.com/iTimeTraveler/SortAlgorithms


“选择排序的示例动画。红色表示当前最小值,黄色表示已排序序列,蓝色表示当前位置。”)选择排序的示例动画。红色表示当前最小值,黄色表示已排序序列,蓝色表示当前位置。

从算法逻辑上看,选择排序是一种简单直观的排序算法,在简单选择排序过程中,所需移动记录的次数比较少。

1、基本思想

选择排序的基本思想:比较 + 交换。

在未排序序列中找到最小(大)元素,存放到未排序序列的起始位置。在所有的完全依靠交换去移动元素的排序方法中,选择排序属于非常好的一种。

2、算法描述

①. 从待排序序列中,找到关键字最小的元素;
②. 如果最小元素不是待排序序列的第一个元素,将其和第一个元素互换;
③. 从余下的 N – 1 个元素中,找出关键字最小的元素,重复①、②步,直到排序结束。

3、代码实现

选择排序比较简单,以下是我自己的实现,跟官方版差不多,所以完全可以参考。

/**
 * 选择排序
 *
 * 1\. 从待排序序列中,找到关键字最小的元素;
 * 2\. 如果最小元素不是待排序序列的第一个元素,将其和第一个元素互换;
 * 3\. 从余下的 N - 1 个元素中,找出关键字最小的元素,重复①、②步,直到排序结束。
 *    仅增量因子为1 时,整个序列作为一个表来处理,表长度即为整个序列的长度。
 * @param arr  待排序数组
 */
public static void selectionSort(int[] arr){
 for(int i = 0; i < arr.length-1; i++){
 int min = i;
 for(int j = i+1; j < arr.length; j++){    //选出之后待排序中值最小的位置
 if(arr[j] < arr[min]){
 min = j;
 }
 }
 if(min != i){
 int temp = arr[min];      //交换操作
 arr[min] = arr[i];
 arr[i] = temp;
 System.out.println("Sorting:  " + Arrays.toString(arr));
 }
 }
}

以下是选择排序复杂度:

平均时间复杂度 最好情况 最坏情况 空间复杂度
O(n²) O(n²) O(n²) O(1)

选择排序的简单和直观名副其实,这也造就了它”出了名的慢性子”,无论是哪种情况,哪怕原数组已排序完成,它也将花费将近n²/2次遍历来确认一遍。即便是这样,它的排序结果也还是不稳定的。 唯一值得高兴的是,它并不耗费额外的内存空间。

赞(0) 打赏

如未加特殊说明,此网站文章均为原创,转载必须注明出处。Java 技术驿站 » Java 排序算法 — 简单选择排序
分享到: 更多 (0)

评论 抢沙发

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

关注【Java 技术驿站】公众号,每天早上 8:10 为你推送一篇技术文章

扫描二维码关注我!


关注【Java 技术驿站】公众号 回复 “VIP”,获取 VIP 地址永久关闭弹出窗口

免费获取资源

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信扫一扫打赏