【算法】排序（一）选择排序

Google Image

在排序算法中，最简单的莫过于选择排序了。

---

本文将介绍以下内容

排序思路
算法实现（JAVA）
测试阶段
算法分析

排序思路：

在选择排序算法中分别有一个外循环和一个内循环，假设需要排序的序列共有n个元素，所以外循环的次数为n次，在n次交换（外循环）中，每次设置序列中的第一个元素为最小值（min)，然后进行内循环，每次内循环都将序列中与min比较，若有元素小于min，则进行交换（若没有，min自己与自己交换）。所以内循环的次数暂时不确定。

简而言之，就是在未排序的序列中，每次选取序列首位元素，依次与序列中其他元素比较，进而交换元素，达到排序的效果。

算法实现

1.外循环

      public static void selectionSort(int[] a){
          int n = a.length;
          for (int i = 0; i < n; i++) {                      //外循环共n次
              int min = i;
              int temp = a[i];                               //
              a[i] = a[min];                                 // 交换元素
              a[min] = temp;                                 //
          } 
      } 

共有n次交换

2.内循环（比较大小并交换元素索引）

        for (int j = i + 1; j < n; j++) {
                 if(a[j] < a[min]){
                    min = j;                 //如果由元素小于min,则交换元素索引
                }
        }

j = i + 1, i +2 , i + 3 ... n.
共有n - i - 1次比较，比较的次数将会在下文提及。

3.交换元素

        int temp = a[i];
        a[i] = a[min];
        a[min] = temp;

所以，选择排序的代码块

就是如此了：

public static void selectionSort(int[] a){
        int n = a.length;
        for (int i = 0; i < n; i++) {
            int min = i;
            for (int j = i + 1; j < n; j++) {
                if(a[j] < a[min]){
                    min = j;
                }
            }
            int temp = a[i];
            a[i] = a[min];
            a[min] = temp;
        } 
    }

测试阶段

我们来写一个测试数据：

public static void main(String[] args){
        int[] a = new int[10];
        for (int i = 0; i < a.length; i++) {
            a[i] = (int)(Math.random()*100);      //随机输入测试数据
            System.out.print(a[i] + " ");
        }
        System.out.println();
        selectionSort(a);
        for (int i = 0; i < a.length; i++) {
            System.out.print(a[i] + " ");
        }
    }

随机选取几组排序结果：

test 1 test 2 test 3

算法分析：

1. 特点

1. 运行时间与输入数据无关，运行时间与数组大小成线性相关，无论
   初始数据的有序性如何，都不会改变元素交换的次数。

2. 数据的移动最少，这是其他排序所不能比的，每次外循环使数据移
   动一次，所以选择排序的数据移动次数为 n 次。

2. 时间复杂度

• 内循环：n 次交换

• 外循环：比较的次数随着i的增长而减少，每次内循环有n -1 - i 次比
  较，总共比较次数：
  (n - 1) + (n - 2) + ... + 2 + 1 = n(n - 1) / 2

• 基本操作总数： n + n(n - 1) /2 = n(n + 1) / 2 ~ n²/2

• 所以，时间复杂度为O(n²)，平方级别

3. 空间复杂度

• 在交换素组元素时，需要建立一个临时变量来帮助交换元素，所以空间复杂度为O(1)

4. 稳定性

• 由于选择排序在排序前后会打乱相同键值元素的相对顺序，所以选择排序是不稳定的

关于选择排序的说明就到这里了，下一篇将会是 冒泡排序 。

给颗红心，举手之劳， 谢谢！