选择排序(Selection sort)是一种简单直观的排序算法。它的工作原理如下。首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置,然后,再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾。以此类推,直到所有元素均排序完毕。
选择排序的主要优点与数据移动有关。如果某个元素位于正确的最终位置上,则它不会被移动。选择排序每次交换一对元素,它们当中至少有一个将被移到其最终位置上,因此对n个元素的表进行排序总共进行至多n-1次交换。在所有的完全依靠交换去移动元素的排序方法中,选择排序属于非常好的一种。
##选择排序C语言实现:
void selection_sort(int arr[], int len) { int i, j, min, temp; for (i = 0; i < len - 1; i++) { min = i; for (j = i + 1; j < len; j++) if (arr[min] > arr[j]) min = j; temp = arr[min]; arr[min] = arr[i]; arr[i] = 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; } }
##选择排序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 L[min_index] > L[j]: min_index = j if min_index != i: L[min_index], L[i] = L[i], L[min_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 (arr[min] > arr[j]) min = j; temp = arr[min]; //将最小元素放到已排序序列的末尾 arr[min] = arr[i]; arr[i] = 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 (this[min] > this[j]) min = j; temp = this[min]; this[min] = this[i]; this[i] = 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) } }