选择排序算法

选择排序（Selection sort）是一种简单直观的排序算法。它的工作原理如下。首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

选择排序的主要优点与数据移动有关。如果某个元素位于正确的最终位置上，则它不会被移动。选择排序每次交换一对元素，它们当中至少有一个将被移到其最终位置上，因此对 n 个元素的表进行排序总共进行至多 n-1 次交换。在所有的完全依靠交换去移动元素的排序方法中，选择排序属于非常好的一种。

数据结构 : 数组
最坏时间复杂度 : О(n²)
最优时间复杂度 : О(n²)
平均时间复杂度 : О(n²)
最坏空间复杂度 : 总共 О(n)，需要辅助空间 O(1)

动图演示

红色表示当前最小值，黄色表示已排序序列，蓝色表示当前位置。

实现示例

C语言

void selection_sort(int a[], int len) 
{
  int i,j,temp;

  for (i = 0 ; i < len - 1 ; i++) 
    {
    int min = i;
    for (j = i + 1; j < len; j++)     //走訪未排序的元素
    {
      if (a[j] < a[min])    //找到目前最小值
      {
        min = j;    //紀錄最小值
      }
    }
    if(min != i)
    {
      temp=a[min];  //交換兩個變數
      a[min]=a[i];
      a[i]=temp;
    }
       /* swap(&a[min], &a[i]);  */   //做交換
  }
}

/*
void swap(int *a,int *b) //交換兩個變數
{
    int temp = *a;
    *a = *b;
    *b = temp;
}
*/

C++

template<typename T> //整數或浮點數皆可使用，若要使用物件（class）時必須設定大於（>）的運算子功能
void selection_sort(std::vector<T>& arr) {
  for (int i = 0; i < arr.size() - 1; i++) {
    int min = i;
    for (int j = i + 1; j < arr.size(); j++)
      if (arr[j] < arr[min])
        min = j;
    std::swap(arr[i], arr[min]);
  }
}

C#

static void selection_sort<T>(T[] arr) where T : System.IComparable<T>{//整數或浮點數皆可使用
  int i, j, min, len = arr.Length;
  T temp;
  for (i = 0; i < len - 1; i++) {
    min = i;
    for (j = i + 1; j < len; j++)
      if (arr[min].CompareTo(arr[j]) > 0)
        min = j;
    temp = arr[min];
    arr[min] = arr[i];
    arr[i] = temp;
  }
}

VB.net

'進行排序前先建構兩數值交換的程式switch
   Private Sub switch(ByRef a, ByRef b)
       Dim c As Integer
       c = a: a = b: b = c
   End Sub
   
   Private Sub(ByRef Data() as Decimal)
   '選擇排序由小到大
       Dim i, j, count As Integer
       Dim minIndex As Integer
       For i = 0 To UBound(Data) - 2
           minIndex =i
           For j = i + 1 To UBound(Data)-1
               If Data(minIndex) > Data(j) Then 
                   minIndex =j
               end if
           Next 
           if i<> minIndex then
                 switch(Data(i), Data(minIndex))
                 count += 1
           end if
       Next
       MsgBox("一共經過了" & count & "次的排序")
  End Sub

Python

def selection_sort(arr):
    for i in range(len(arr)-1):
        minIndex=i
        for j in range(i+1,len(arr)):
            if arr[minIndex]>arr[j]:
                minIndex=j
        if i==minIndex:
            pass
        else:
            arr[i],arr[minIndex]=arr[minIndex],arr[i]
    return arr


if __name__ == '__main__':
    testlist = [17, 23, 20, 14, 12, 25, 1, 20, 81, 14, 11, 12]
    print(selection_sort(testlist))

Java

    public static void selectionSort(Comparable[] a) {
        int N =a.length;
        for (int i = 0; i < N-1; i++) {
            int min = i;
            for (int j = i+1; j < N; j++) {
                if (less(a[j], a[min])) min = j;
            }
            exch(a, i, min);
        }
    }

    private static boolean less(Comparable v, Comparable w) {
        return v.compareTo(w) < 0;
    }

    private static void exch(Comparable[] a, int i, int j) {
        Comparable t = a[i];
        a[i] = a[j];
        a[j] = t;
    }

JavaScript

Array.prototype.selection_sort = function() {
  let min;
  for (let i = 0; i < this.length - 1; i++) {
    min = i;
    for (let j = i + 1; j < this.length; j++) {
      if (this[min] > this[j]) {
        min = j;
      }
    }
    // swap two value without temp variable
    if (min !== i) {
      this[min] = this[min] ^ this[i];
      this[i] = this[min] ^ this[i];
      this[min] = this[min] ^ this[i];
    }
  }
  return this;
};

PHP

function swap(&$x, &$y) {
  $t = $x;
  $x = $y;
  $y = $t;
}
function selection_sort(&$arr) {//php的陣列視為基本型別，所以必須用傳參考才能修改原陣列
  for ($i = 0; $i < count($arr) - 1; $i++) {
    $min = $i;
    for ($j = $i + 1; $j < count($arr); $j++)
      if ($arr[$min] > $arr[$j])
        $min = $j;
    swap($arr[$min], $arr[$i]);
  }
}

GO

// SelectionSort 选择排序, data必须实现sort包中的Interface接口
func SelectionSort(data sort.Interface) {

  for i := 0; i < data.Len()-1; i++ {
    // 假定首元素为最小元素
    min := i
    for j := min + 1; j < data.Len(); j++ {
      if data.Less(j, min) {
        min = j
      }
    }
    // 将此次筛选出的最小元素放入最左边
      if min != i {
        data.Swap(min, i)
      }
  }
}

Swift

import Foundation
/// 选择排序
///
/// - Parameter list: 需要排序的数组
func selectionSort(_ list: inout [Int]) -> Void {
    for j in 0..<list.count - 1 {
        var minIndex = j
        for i in j..<list.count {
            if list[minIndex] > list[i] {
                minIndex = i
            }
        }
        list.swapAt(j, minIndex)
    }
}

复杂度分析

选择排序的交换操作介于 0 和 n-1 次之间。选择排序的比较操作为 n(n-1)/2 次。选择排序的赋值操作介于 0 和 3(n-1) 次之间。

比较次数

，比较次数与关键字的初始状态无关，总的比较次数 N = (n - 1) + (n - 2) + ... + 1=n * (n - 1) / 2。交换次数

，最好情况是，已经有序，交换 0 次；最坏情况是，逆序，交换 n-1 次。交换次数比冒泡排序较少，由于交换所需CPU时间比比较所需的CPU时间多，n 值较小时，选择排序比冒泡排序快。

原地操作几乎是选择排序的唯一优点，当空间复杂度要求较高时，可以考虑选择排序；实际适用的场合非常罕见。