算法回顾篇：选择排序

Luckly 收录于算法

2018-06-12 约 1084 字预计阅读 3 分钟次阅读

更多分享：www.catbro.cn

一、前言：

所谓排序：就是一组对象，按照某种逻辑重新排序的过程。
排序算法主要有以下几种：插入排序，冒泡排序，堆排序，归并排序，选择排序，计数排序，基数排序，桶排序，快速排序等。
插入排序，堆排序，选择排序，归并排序和快速排序，冒泡排序都是比较排序，它们通过对数组中的元素进行比较来实现排序，
其他排序算法则是利用非比较的其他方法来获得有关输入数组的排序信息。
本章节我们将学习选择排序。

二、选择排序概念

选择排序（Selection sort）是一种简单直观的排序算法。它的工作原理是每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。

三、kotlin代码实现

在编写排序算法之前，我们先准备几个公共函数
代码如下： object SortUtils { val TAG: String = “SortUtils: “; //判断v1元素是否小于v2元素 fun less(v1: Comparable, v2: Comparable): Boolean { var result = v1.compareTo(v2); return result<0; } //交换v1与v2的位置 fun exchange(list: Array<Comparable>, v1: Int, v2: Int) { var temp: Comparable = list[v1]; list[v1] = list[v2]; list[v2] = temp; } //打印列表元素 fun show(list: Array<Comparable>) { list.forEach { print("$it “) } println(); }
```
} 
```

创建一个SelectSort类

 class SelectSortDemo {

     fun sort(list: Array<Comparable<Any>>) {
         println("排序前：");
         var compareCount = 0;
         var moveCount = 0;
         SortUtils.show(list);
         var N: Int = list.size;
         //外层从第0个开始取
         for (i in 0..(N - 1)) {
           //取外层循环的第一个默认为最小值
             var min = i;
             //内层从第一个开始取
             for (j in (i + 1)..(N - 1)) {
                 compareCount++;
                 //依次取出剩余元素进行比较，将最小的元素的index赋值给min
                 if (SortUtils.less(list[j], list[min])) {
                     min = j;
                 }
             }
             //计算位置交换的次数
             moveCount++;
             //交换元素位置，可以考虑判断i是否等于min来减少移动的次数
             SortUtils.exchange(list, i, min);

         }
         println("排序后：");
         SortUtils.show(list);

         println("数组大小：${list.size} || 比较次数：$compareCount || 移动次数：$moveCount")
     }

 }

调用代码如下：

fun main(args: Array<String>) {
    var list: Array<String> = arrayOf("S", "O", "R","T", "E", "X","A","M","P","L","E","S");

    var selectSort = SelectSortDemo();
    var startTime = System.currentTimeMillis();

    selectSort.sort(list as Array<Comparable<Any>>)
    var endTime = System.currentTimeMillis();
    var costTime = endTime - startTime;
    println("花费时间： $costTime")

}

四、总结：

选择排序是非常简洁的一种排序算法，其比较次数和交换次数都是固定的。
再次简述以下：
- 有1～N个元素，从第一个元素开始，依次与2～N个元素做比较，将最大的或者最小的存放在第一个位置
- 元素的交换次数为N
- 比较次数：(N-1)+(N-2)+…….+2+1=(N-1+1)*N/2=N^2/2
特点：
- 1、运行时间与输入无关一个已排序好的数组与一个乱序的数组，比较次数和交换次数都是一样的
- 2、数据移动最少每次排序都换交换两个位置的元素，因此选择排序交换次数为N次，交换次数和组数的大小是线性增长的，比较次数是平方增长的
更多分享：www.catbro.cn

目录

算法回顾篇：选择排序

一、前言：

二、选择排序概念

三、kotlin代码实现

四、总结：