选择排序

选择排序
	選擇排序動畫演示
概况
類別	排序算法
資料結構	數組
复杂度
平均時間複雜度	О(n²)
最坏时间复杂度	О(n²)
最优时间复杂度	О(n²)
空間複雜度	總共О(n)，需要輔助空間O(1)
最佳解	偶尔出现
相关变量的定义

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

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

选择排序的主要优点与数据移动有关。如果某个元素位于正确的最终位置上，则它不会被移动。选择排序每次交换一对元素，它们当中至少有一个将被移到其最终位置上，因此对 $n$ 个元素的表进行排序总共进行至多 $(n-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)$ 次之间。

比较次数 $O(n^{2})$ ，比较次数与关键字的初始状态无关，总的比较次数 $N=(n-1)+(n-2)+...+1=n\times (n-1)/2$ 。交换次数 $O(n)$ ，最好情况是，已经有序，交换0次；最坏情况是，逆序，交换 $n-1$ 次。交换次数比冒泡排序较少，由于交换所需CPU时间比比较所需的CPU时间多， $n$ 值较小时，选择排序比冒泡排序快。

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

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.