【选择排序算法详解】Java/Go/Python/JS/C 不同语言实现
说明
选择排序（Selection Sort）是一种简单直观的排序算法。跟冒泡、插入排序一样，它将数列分为已排序和待排序两个区间。首先在待排序序列中找到最小（或最大）的元素，追加到已排序序列中，然后继续从待排序序列中寻找最小（或最大）的元素，追加到已排序序列的尾部。以此类推，直到所有元素均排序完毕。可以通过同时找出最小和最大项来优化性能，详见源码。
实现过程
- 先建立两个循环，外循环用于逐个交换数据，内循环用来遍历找到最小(或最大)值。
- 设第 1 项为最小值，在内循环中将其逐个与后项进行比较，如果遇到更小的值，则更新最小值，并记录下最小值的下标。
- 在外循环中将第 1 项与最小值进行交换，然后以第 2 项作为最小值，再重复执行步骤 2，直到遍历完全部待排序区间。
示意图
性能分析
平均时间复杂度：O(N^2) 最佳时间复杂度：O(N^2) 最差时间复杂度：O(N^2) 空间复杂度：O(1) 排序方式：In-place 稳定性：不稳定 选择排序的交换操作介于和(n-1)次之间。选择排序的比较操作为n(n-1)/2次之间。选择排序的赋值操作介于0和3(n-1)次之间。 比较次数O(n^2)，比较次数与关键字的初始状态无关，总的比较次数N = (n-1) + (n-2) +…+ 1 = n x (n-1)/2。交换次数O(n)，最好情况是，已经有序，交换0次；最坏情况是，逆序，交换n-1次。
代码
Java
// java选择排序标准版，更多版本请看源码文件 class SelectionSort { static int[] selectionSort1(final int[] arr) { int min; int minIdx; int tmp; int l = arr.length; for (int i = 0; i < l - 1; i++) { min = arr[i]; minIdx = i; int j = i + 1; for (; j < l; j++) { // 从待排序列表找到最小值和位置 if (arr[j] < min) { min = arr[j]; minIdx = j; } } System.out.println("i=" + i + " j=" + j + " min=" + min + "minIdx=" + minIdx + " arr[]" + Arrays.toString(arr)); // 将待排序里最小值交换到已排序最后面 if (minIdx != i) { tmp = arr[i]; arr[i] = min; arr[minIdx] = tmp; } } return arr; } } // 选择排序优化版，同时找出最小和最大值进行交换，可减少1半遍历 // 把数列分为前中后三个区间，分别代表最小已排序、中间待排序以及最大已排序区间 // 遍历中间待排序同时找最大和最小值，分别交换到最小值区间和最大值区间 class SelectionSort { static int[] sort(final int[] arr) { int minValue, maxValue, minIdx, maxIdx; int minListIdx, maxListIdx; int arrLen = arr.length; for (int i = 0; i < arrLen - 1; i++) { // 待排序里面初始最小值和下标 minIdx = i; minValue = arr[minIdx]; // 待排序里面初始最大值和下标 maxIdx = i; maxValue = arr[maxIdx]; // 最小和最大序列里最新待交换的下标 // 最小序列的下标从0开始，自前往后递加 minListIdx = minIdx; // 最大序列的下标从数组最后1位开始，自后往前递减 maxListIdx = arrLen - 1 - i; // 如果最小和最大下标相同，说明只剩下1个数字，则终止循环 if (minListIdx == maxListIdx) { break; } // 逐一遍历待排序区间，找出最小和最大值 // 待排序区间在最小值序列和和最大值序列之间 // 待比较区间的下标j从i+1开始，到最大已排序前结束 for (int j = i + 1; j < arrLen - i; j++) { // 从待排序列表中分别找到最小值和最大值 if (arr[j] < minValue) { minIdx = j; minValue = arr[minIdx]; } else if (arr[j] > maxValue) { maxIdx = j; maxValue = arr[maxIdx]; } } // 如果最小值等于最小序列待交换的值，且最大值等于最大序列里待交换的值，则跳过 if (arr[minIdx] == arr[minListIdx] && arr[maxIdx] == arr[maxListIdx]) { continue; } // 先交换小值，再交换大值 arr[minIdx] = arr[minListIdx]; arr[minListIdx] = minValue; // 如果最大值被交换了，则需要更新最大值的下标 if (arr[minIdx] == maxValue) { maxIdx = minIdx; } arr[maxIdx] = arr[maxListIdx]; arr[maxListIdx] = maxValue; } return arr; } }
Python
# python选择排序标准版本，更多实现版本请查看源文件 # 新建数组版，无需交换 def selection_sort2(arr): new_list = [] i = 0 l = len(arr) while (i < l): min = arr[i] min_idx = i j = i + 1 while (j < l): # 找到并记录下最小值和位置 if (arr[j] < min): min = arr[j] min_idx = j j += 1 # 将待排序里最小值添加到新数组中去 new_list.append(min) # 原数组中删除对应的项 arr.remove(min) l -= 1 return new_list """ # 选择排序优化版，同时找出最小和最大值进行交换，可减少1半遍历 # 把数列分为前中后三个区间，分别代表最小已排序、中间待排序以及最大已排序区间 # 遍历中间待排序同时找最大和最小值，分别交换到最小值区间和最大值区间 """ def selection_sort(arr): arr_len = len(arr) for i in range(arr_len - 1): # 初始最小值和下标 min_idx = i min_value = arr[min_idx] # 初始最大值和下标 max_idx = i max_value = arr[max_idx] # 最小和最大序列里最新待交换的下标 # 最小序列的下标从0开始，自前往后递加 min_list_idx = min_idx # 最大序列的下标从数组最后1位开始，自后往前递减 max_list_idx = arr_len - 1 - i # 如果最小和最大下标相同，说明只剩下1个数字，则终止循环 if min_list_idx == max_list_idx: break # 逐一遍历待排序区间，找出最小和最大值 # 待排序区间在最小值序列和和最大值序列之间 # 待比较区间的下标j从i+1开始，到最大已排序前结束 j = i + 1 while j < arr_len - i: # 从待排序列表找到最小值和最大值及位置 if arr[j] < min_value: min_idx = j min_value = arr[min_idx] elif arr[j] > max_value: max_idx = j max_value = arr[max_idx] j += 1 # 如果最小值等于最小序列待交换的值，且最大值等于最大序列里待交换的值，则跳过 if arr[min_idx] == arr[min_list_idx] and arr[max_idx] == arr[ max_list_idx]: continue print('min_value=', min_value, 'max_value=', max_value, 'min_idx=', min_idx, 'max_idx=', max_idx, 'min_list_idx=', min_list_idx, 'max_list_idx=', max_list_idx) # 先交换小值，再交换大值 arr[min_list_idx], arr[min_idx] = arr[min_idx], arr[min_list_idx] # 如果最大值被交换了，则需要更新最大值的下标 if arr[min_idx] == max_value: max_idx = min_idx arr[max_list_idx], arr[max_idx] = arr[max_idx], arr[max_list_idx] return arr
Go
// go选择排序标准版，其他版本请查看源文件 func selectionSort1(arr []int) []int { var min = arr[0] var minIdx = 0 var tmp = -1 var arrLen = len(arr) for i := 0; i < arrLen-1; i++ { min = arr[i] minIdx = i var j = i + 1 for ; j < arrLen; j++ { // 从待排序列表中找到最小值和位置，用作交换 if arr[j] < min { min = arr[j] minIdx = j } } fmt.Println("i=", i, " j=", j, "min=", min, "minIdx=", minIdx, "arr[]=", arr) // 将待排序里最小值交换到已排序最后面 if minIdx != i { tmp = arr[i] arr[i] = min arr[minIdx] = tmp } } return arr } // 选择排序优化版，同时找出最小和最大值进行交换，可减少1半遍历 // 把数列分为前中后三个区间，分别代表最小已排序、中间待排序以及最大已排序区间 // 遍历中间待排序同时找最大和最小值，分别交换到最小值区间和最大值区间 func selectionSort(arr []int) []int { var minValue int var maxValue int var minIdx int var maxIdx int var minListIdx int var maxListIdx int var arrLen = len(arr) for i := 0; i < arrLen-1; i++ { // 待排序里面初始最小值和下标 minIdx = i minValue = arr[minIdx] // 待排序里面初始最大值和下标 maxIdx = i maxValue = arr[maxIdx] // 最小和最大序列里最新待交换的下标 // 最小序列的下标从0开始，自前往后递加 minListIdx = minIdx // 最大序列的下标从数组最后1位开始，自后往前递减 maxListIdx = arrLen - 1 - i // 如果最小和最大下标相同，说明只剩下1个数字，则终止循环 if minListIdx == maxListIdx { break } // 逐一遍历待排序区间，找出最小和最大值 // 待排序区间在最小值序列和和最大值序列之间 // 待比较区间的下标j从i+1开始，到最大已排序前结束 for j := i + 1; j < arrLen-i; j++ { // 从待排序列表中分别找到最小值和最大值 if arr[j] < minValue { minIdx = j minValue = arr[minIdx] } else if arr[j] > maxValue { maxIdx = j maxValue = arr[maxIdx] } } // 如果最小值等于最小序列待交换的值，且最大值等于最大序列里待交换的值，则跳过 if arr[minIdx] == arr[minListIdx] && arr[maxIdx] == arr[maxListIdx] { continue } fmt.Println("minValue=", minValue, " maxValue=", maxValue, " minIdx=", minIdx, " maxIdx=", maxIdx, " minListIdx=", minListIdx, " maxListIdx=", maxListIdx) // 先交换小值，再交换大值 arr[minListIdx], arr[minIdx] = arr[minIdx], arr[minListIdx] // 如果最大值被交换了，则需要更新最大值的下标 if arr[minIdx] == maxValue { maxIdx = minIdx } arr[maxListIdx], arr[maxIdx] = arr[maxIdx], arr[maxListIdx] } return arr }
JS
// js选择排序徐标准版，更多实现版本详见源码文件 // 新建数组版，无需交换 function selectionSort2(arr) { var min, minIdx var newArr = [] var arrLen = arr.length for (var i = 0; i < arrLen; i++) { min = arr[i] minIdx = i let j = i + 1 for (; j < arrLen; j++) { // 找到并记录下最小值和位置 if (arr[j] < min) { min = arr[j] minIdx = j } } console.log('i=' + i, ' j=' + j, 'min=' + min, 'minIdx=' + minIdx, 'arr[]=', arr) // 将待排序里最小值添加到新数组中去 newArr.push(min) // 原数组中删除对应的项 arr.splice(minIdx, 1) arrLen-- i-- } return newArr } // 选择排序优化版，同时找出最小和最大值进行交换，可减少1半遍历 // 把数列分为前中后三个区间，分别代表最小已排序、中间待排序以及最大已排序区间 // 遍历中间待排序同时找最大和最小值，分别交换到最小值区间和最大值区间 function selectionSort(arr) { let minValue, maxValue, minIdx, maxIdx let minListIdx, maxListIdx const arrLen = arr.length // 外循环，从第1项开始与后面待排序项逐个对比，最后1位无需再比较 for (let i = 0; i < arrLen - 1; i++) { // 待排序里面初始最小值和下标 minIdx = i minValue = arr[minIdx] // 待排序里面初始最大值和下标 maxIdx = i maxValue = arr[maxIdx] // 最小和最大序列里最新待交换的下标 // 最小序列的下标从0开始，自前往后递加 minListIdx = minIdx // 最大序列的下标从数组最后1位开始，自后往前递减 maxListIdx = arrLen - 1 - i // 如果最小和最大下标相同，说明只剩下1个数字，则终止循环 if (minListIdx === maxListIdx) { break } // 逐一遍历待排序区间，找出最小和最大值 // 待排序区间在最小值序列和和最大值序列之间 // 待比较区间的下标j从i+1开始，到最大已排序前结束 for (let j = i + 1; j < arrLen - i; j++) { // 从待排序列表中分别找到最小值和最大值 if (arr[j] < minValue) { minIdx = j minValue = arr[minIdx] } else if (arr[j] > maxValue) { maxIdx = j maxValue = arr[maxIdx] } } // 如果最小值等于最小序列待交换的值，且最大值等于最大序列里待交换的值，则跳过 if (arr[minIdx] === arr[minListIdx] && arr[maxIdx] === arr[maxListIdx]) { continue } console.log('minValue=', minValue, 'maxValue=', maxValue, 'minIdx=', minIdx, 'maxIdx=', maxIdx, 'minListIdx=', minListIdx, 'maxListIdx=', maxListIdx) // 先交换小值，再交换大值 ;[arr[minListIdx], arr[minIdx]] = [arr[minIdx], arr[minListIdx]] // 如果最大值被交换了，则需要更新最大值的下标 if (arr[minIdx] === maxValue) { maxIdx = minIdx } ;[arr[maxListIdx], arr[maxIdx]] = [arr[maxIdx], arr[maxListIdx]] } return arr }
TS
// TS标准版，其他版本请查看源码文件 class SelectionSort { constructor() {} // 标准版 selectionSort1(arr: Array<number>) { let min: number, minIdx: number, tmp: number let l = arr.length for (let i = 0; i < l - 1; i++) { min = arr[i] minIdx = i let j = i + 1 for (; j < l; j++) { // 从待排序列表找到最小值和位置 if (arr[j] < min) { min = arr[j] minIdx = j } } // 将待排序里最小值交换到已排序最后面 if (minIdx !== i) { tmp = arr[i] arr[i] = min arr[minIdx] = tmp } } return arr } }
class SelectionSort { // 选择排序优化版，同时找出最小和最大值进行交换，可减少1半遍历 // 把数列分为前中后三个区间，分别代表最小已排序、中间待排序以及最大已排序区间 // 遍历中间待排序同时找最大和最小值，分别交换到最小值区间和最大值区间 sort(arr: Array<number>) { let minValue: number, maxValue: number, minIdx: number, maxIdx: number let minListIdx: number, maxListIdx: number const arrLen = arr.length // 外循环，从第1项开始与后面待排序项逐个对比，最后1位无需再比较 for (let i = 0; i < arrLen - 1; i++) { // 待排序里面初始最小值和下标 minIdx = i minValue = arr[minIdx] // 待排序里面初始最大值和下标 maxIdx = i maxValue = arr[maxIdx] // 最小和最大序列里最新待交换的下标 // 最小序列的下标从0开始，自前往后递加 minListIdx = minIdx // 最大序列的下标从数组最后1位开始，自后往前递减 maxListIdx = arrLen - 1 - i // 如果最小和最大下标相同，说明只剩下1个数字，则终止循环 if (minListIdx === maxListIdx) { break } // 逐一遍历待排序区间，找出最小和最大值 // 待排序区间在最小值序列和和最大值序列之间 // 待比较区间的下标j从i+1开始，到最大已排序前结束 for (let j = i + 1; j < arrLen - i; j++) { // 从待排序列表中分别找到最小值和最大值 if (arr[j] < minValue) { minIdx = j minValue = arr[minIdx] } else if (arr[j] > maxValue) { maxIdx = j maxValue = arr[maxIdx] } } // 如果最小值等于最小序列待交换的值，且最大值等于最大序列里待交换的值，则跳过 if (arr[minIdx] === arr[minListIdx] && arr[maxIdx] === arr[maxListIdx]) { continue } // 先交换小值，再交换大值 arr[minIdx] = arr[minListIdx]; arr[minListIdx] = minValue; // 如果最大值被交换了，则需要更新最大值的下标 if (arr[minIdx] == maxValue) { maxIdx = minIdx; } arr[maxIdx] = arr[maxListIdx]; arr[maxListIdx] = maxValue; } return arr } }
C
// c语言选择排序标准版，其他版本请查看源码文件 void *selection_sort1(int arr[], int len) { int min_value, min_idx, tmp; for (int i = 0; i < len - 1; i++) { min_value = arr[i]; min_idx = i; int j = i + 1; for (; j < len; j++) { // 从待排序列表找到最小值和位置 if (arr[j] < min_value) { min_value = arr[j]; min_idx = j; } } // 将待排序里最小值交换到已排序最后面 if (min_idx != i) { tmp = arr[i]; arr[i] = min_value; arr[min_idx] = tmp; } } return arr; }
// 选择排序优化版，同时找出最小和最大值进行交换，可减少1半遍历 // 把数列分为前中后三个区间，分别代表最小已排序、中间待排序以及最大已排序区间 // 遍历中间待排序同时找最大和最小值，分别交换到最小值区间和最大值区间 void *selection_sort(int arr[], int len) { int min_value, max_value, min_idx, max_idx; int min_list_idx, max_list_idx; for (int i = 0; i < len - 1; i++) { // 待排序里面初始最小值和下标 min_idx = i; min_value = arr[min_idx]; // 待排序里面初始最大值和下标 max_idx = i; max_value = arr[max_idx]; // 最小和最大序列里最新待交换的下标 // 最小序列的下标从0开始，自前往后递加 min_list_idx = min_idx; // 最大序列的下标从数组最后1位开始，自后往前递减 max_list_idx = len - 1 - i; // 如果最小和最大下标相同，说明只剩下1个数字，则终止循环 if (min_list_idx == max_list_idx) { break; } // 逐一遍历待排序区间，找出最小和最大值 // 待排序区间在最小值序列和和最大值序列之间 // 待比较区间的下标j从i+1开始，到最大已排序前结束 for (int j = i + 1; j < len - i; j++) { // 从待排序列表中分别找到最小值和最大值 if (arr[j] < min_value) { min_idx = j; min_value = arr[min_idx]; } else if (arr[j] > max_value) { max_idx = j; max_value = arr[max_idx]; } } // 如果最小值等于最小序列待交换的值，且最大值等于最大序列里待交换的值，则跳过 if (arr[min_idx] == arr[min_list_idx] && arr[max_idx] == arr[max_list_idx]) { continue; } // 先交换小值，再交换大值 arr[min_idx] = arr[min_list_idx]; arr[min_list_idx] = min_value; // 如果最大值被交换了，则需要更新最大值的下标 if (arr[min_idx] == max_value) { max_idx = min_idx; } arr[max_idx] = arr[max_list_idx]; arr[max_list_idx] = max_value; } return arr; }
链接
选择排序算法源码：https://github.com/microwind/algorithms/tree/master/sorts/selectionsort
