【选择排序算法详解】Java/Go/Python/JS/C 不同语言实现说明

选择排序(Selection Sort)是一种简单直观的排序算法。跟冒泡、插入排序一样,它将数列分为已排序和待排序两个区间。首先在待排序序列中找到最小(或最大)的元素,追加到已排序序列中,然后继续从待排序序列中寻找最小(或最大)的元素,追加到已排序序列的尾部。以此类推,直到所有元素均排序完毕。可以通过同时找出最小和最大项来优化性能,详见源码。

实现过程

  1. 先建立两个循环,外循环用于逐个交换数据,内循环用来遍历找到最小(或最大)值。
  2. 设第 1 项为最小值,在内循环中将其逐个与后项进行比较,如果遇到更小的值,则更新最小值,并记录下最小值的下标。
  3. 在外循环中将第 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) {    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) { 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

其他排序算法源码:https://github.com/microwind/algorithms