计算机科学

首页 > 计算机科学

选择排序

2018-08-28 09:42:52     所属分类:排序算法
选择排序
选择排序动画演示
分类 排序算法
数据结构 数组
最坏时间复杂度 О(n²)
最优时间复杂度 О(n²)
平均时间复杂度 О(n²)
最坏空间复杂度 О(n) total, O(1) auxiliary
选择排序的示例动画。红色表示当前最小值,黄色表示已排序序列,蓝色表示当前位置。

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

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

目录

  • 1 实现示例
    • 1.1 C语言
    • 1.2 C++
    • 1.3 C#
    • 1.4 VB.net
    • 1.5 Python
    • 1.6 Java
    • 1.7 JavaScript
    • 1.8 PHP
    • 1.9 GO
    • 1.10 Swift
  • 2 复杂度分析
  • 3 外部链接

实现示例

C语言

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

	for (i = 0 ; i < len - 1 ; i++) 
    {
		int min = i;
		for (j = i + 1; j < len; j++)     //走訪未排序的元素
			if (arrj < arrmin)    //找到目前最小值
				min = j;    //紀錄最小值
	   	swap(&arrmin, &arri);    //做交換
	}
}

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 (arrj < arrmin)
				min = j;
		std::swap(arri, arrmin);
	}
}

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 (arrmin.CompareTo(arrj) > 0)
				min = j;
		temp = arrmin;
		arrmin = arri;
		arri = 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(L):
    N = len(L)
    exchanges_count = 0
    for i in range(N-1):
        min_index = i
        for j in range(i+1, N):
            if Lmin_index > Lj:
                min_index = j
        if min_index != i:
            Lmin_index, Li = Li, Lmin_index
        exchanges_count += 1
        print('iteration #{}: {}'.format(i, L))
    print('Total {} swappings'.format(exchanges_count))
    return L

testlist = 17, 23, 20, 14, 12, 25, 1, 20, 81, 14, 11, 12
print('Before selection sort: {}'.format(testlist))
print('After selection sort:  {}'.format(selection_sort(testlist)))

Java

public static void selection_sort(int arr) {
	int i, j, min, temp, len = arr.length;
	for (i = 0; i < len - 1; i++) {
		min = i;//未排序序列中最小数据数组下标
		for (j = i + 1; j < len; j++)//在未排序元素中继续寻找最小元素,并保存其下标
			if (arrmin > arrj){
				min = j;}
		temp = arrmin; //将最小元素放到已排序序列的末尾
		arrmin = arri;
		arri = temp;
	}
}

JavaScript

Array.prototype.selection_sort = function() {
	var i, j, min;
	var temp;
	for (i = 0; i < this.length - 1; i++) {
		min = i;
		for (j = i + 1; j < this.length; j++)
			if (thismin > thisj)
				min = j;
		temp = thismin;
		thismin = thisi;
		thisi = temp;
	}
};

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

// SelectSort 选择排序, data必须实现sort包中的Interface接口
func SelectSort(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
			}
		}
		// 将此次筛选出的最小元素放入最左边
		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 listminIndex > listi {
                minIndex = i
            }
        }
        list.swapAt(j, minIndex)
    }
}

复杂度分析

选择排序的交换操作介于次之间。选择排序的比较操作次。选择排序的赋值操作介于次之间。


比较次数,比较次数与关键字的初始状态无关,总的比较次数。交换次数,最好情况是,已经有序,交换0次;最坏情况是,逆序,交换次。交换次数比冒泡排序较少,由于交换所需CPU时间比比较所需的CPU时间多,值较小时,选择排序比冒泡排序快。

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

外部链接


上一篇:鸡尾酒排序
下一篇:鸽巢排序
相关推荐