数据结构与算法（Java篇）笔记--选择排序

---

前言

在我们的程序中，排序是非常常见的一种需求，提供一些数据元素，把这些数据元素按照一定的规则进行排序。比如查询一些订单，按照订单的日期进行排序；再比如查询一些商品，按照商品的价格进行排序等等。所以，接下来我们要学习一些常见的排序算法。

---

一、选择排序

选择排序是一种更加简单直观的排序方法。
需求：
排序前：{4,6,8,7,9,2,10,1}
排序后：{1,2,4,5,7,8,9,10}

二、排序原理

Step1.每一次遍历的过程中，都假定第一个索引处的元素是最小值，和其他索引处的值依次进行比较，如果当前索引处 的值大于其他某个索引处的值，则假定其他某个索引出的值为最小值，最后可以找到最小值所在的索引
Step2.交换第一个索引处和最小值所在的索引处的值

API设计

1.代码实现

//排序代码
public class Selection {
    /*
    对数组a中的元素进行排序
    */
    public static void sort(Comparable[] a){
        for (int i=0;i<=a.length-2;i++){
            //假定本次遍历，最小值所在的索引是i
            int minIndex=i;
            for (int j=i+1;j<a.length;j++){
                if (greater(a[minIndex],a[j])){
                    //跟换最小值所在的索引
                    minIndex=j;
                }
            }
            //交换i索引处和minIndex索引处的值
            exch(a,i,minIndex);
        }
    }
    /*
    比较v元素是否大于w元素
    */
    private static boolean greater(Comparable v,Comparable w){
    	return v.compareTo(w)>0;
    }
    /*
    数组元素i和j交换位置
    */
    private static void exch(Comparable[] a,int i,int j){
        Comparable t = a[i];
        a[i]=a[j];
        a[j]=t;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

测试类

//测试代码
//测试代码
public class Test {
    public static void main(String[] args) {
        Integer[] a = {4,6,8,7,9,2,10,1};
        Selection.sort(a);
        System.out.println("Selection sort " + Arrays.toString(a));
    }
}
1
2
3
4
5
6
7
8
9

2.运行结果

编写完成之后，点击运行就能知道选择排序的结果，如下图所示：

---

总结

选择排序使用了双层for循环，其中外层循环完成了数据交换，内层循环完成了数据比较，所以我们分别统计数据交换次数和数据比较次数，根据大O推导法则，保留最高阶项，去除常数因子，时间复杂度为O(N^2);