经验首页 前端设计 程序设计 Java相关 移动开发 数据库/运维 软件/图像 大数据/云计算 其他经验
当前位置:技术经验 » Java相关 » Java » 查看文章
【选择排序算法详解】Java/Go/Python/JS/C 不同语言实现
来源:cnblogs  作者:刀法如飞  时间:2023/3/8 11:00:25  对本文有异议

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

 

说明

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

 

实现过程

  1. 先建立两个循环,外循环用于逐个交换数据,内循环用来遍历找到最小(或最大)值。
  2. 设第 1 项为最小值,在内循环中将其逐个与后项进行比较,如果遇到更小的值,则更新最小值,并记录下最小值的下标。
  3. 在外循环中将第 1 项与最小值进行交换,然后以第 2 项作为最小值,再重复执行步骤 2,直到遍历完全部待排序区间。

 

示意图

 

 

 

性能分析

  1. 平均时间复杂度:O(N^2)
  2. 最佳时间复杂度:O(N^2)
  3. 最差时间复杂度:O(N^2)
  4. 空间复杂度:O(1)
  5. 排序方式:In-place
  6. 稳定性:不稳定
  7.  
  8. 选择排序的交换操作介于和(n-1)次之间。选择排序的比较操作为n(n-1)/2次之间。选择排序的赋值操作介于03(n-1)次之间。
  9. 比较次数O(n^2),比较次数与关键字的初始状态无关,总的比较次数N = (n-1) + (n-2) +…+ 1 = n x (n-1)/2。交换次数O(n),最好情况是,已经有序,交换0次;最坏情况是,逆序,交换n-1次。

代码

Java

 

  1. // java选择排序标准版,更多版本请看源码文件
  2. class SelectionSort {
  3. static int[] selectionSort1(final int[] arr) {
  4. int min;
  5. int minIdx;
  6. int tmp;
  7. int l = arr.length;
  8. for (int i = 0; i < l - 1; i++) {
  9. min = arr[i];
  10. minIdx = i;
  11. int j = i + 1;
  12. for (; j < l; j++) {
  13. // 从待排序列表找到最小值和位置
  14. if (arr[j] < min) {
  15. min = arr[j];
  16. minIdx = j;
  17. }
  18. }
  19. System.out.println("i=" + i + " j=" + j + " min=" + min + "minIdx=" + minIdx + " arr[]" + Arrays.toString(arr));
  20. // 将待排序里最小值交换到已排序最后面
  21. if (minIdx != i) {
  22. tmp = arr[i];
  23. arr[i] = min;
  24. arr[minIdx] = tmp;
  25. }
  26. }
  27. return arr;
  28. }
  29. }
  30. // 选择排序优化版,同时找出最小和最大值进行交换,可减少1半遍历
  31. // 把数列分为前中后三个区间,分别代表最小已排序、中间待排序以及最大已排序区间
  32. // 遍历中间待排序同时找最大和最小值,分别交换到最小值区间和最大值区间
  33. class SelectionSort {
  34. static int[] sort(final int[] arr) {
  35. int minValue, maxValue, minIdx, maxIdx;
  36. int minListIdx, maxListIdx;
  37. int arrLen = arr.length;
  38. for (int i = 0; i < arrLen - 1; i++) {
  39. // 待排序里面初始最小值和下标
  40. minIdx = i;
  41. minValue = arr[minIdx];
  42. // 待排序里面初始最大值和下标
  43. maxIdx = i;
  44. maxValue = arr[maxIdx];
  45. // 最小和最大序列里最新待交换的下标
  46. // 最小序列的下标从0开始,自前往后递加
  47. minListIdx = minIdx;
  48. // 最大序列的下标从数组最后1位开始,自后往前递减
  49. maxListIdx = arrLen - 1 - i;
  50. // 如果最小和最大下标相同,说明只剩下1个数字,则终止循环
  51. if (minListIdx == maxListIdx) {
  52. break;
  53. }
  54. // 逐一遍历待排序区间,找出最小和最大值
  55. // 待排序区间在最小值序列和和最大值序列之间
  56. // 待比较区间的下标j从i+1开始,到最大已排序前结束
  57. for (int j = i + 1; j < arrLen - i; j++) {
  58. // 从待排序列表中分别找到最小值和最大值
  59. if (arr[j] < minValue) {
  60. minIdx = j;
  61. minValue = arr[minIdx];
  62. } else if (arr[j] > maxValue) {
  63. maxIdx = j;
  64. maxValue = arr[maxIdx];
  65. }
  66. }
  67. // 如果最小值等于最小序列待交换的值,且最大值等于最大序列里待交换的值,则跳过
  68. if (arr[minIdx] == arr[minListIdx] && arr[maxIdx] == arr[maxListIdx]) {
  69. continue;
  70. }
  71. // 先交换小值,再交换大值
  72. arr[minIdx] = arr[minListIdx];
  73. arr[minListIdx] = minValue;
  74. // 如果最大值被交换了,则需要更新最大值的下标
  75. if (arr[minIdx] == maxValue) {
  76. maxIdx = minIdx;
  77. }
  78. arr[maxIdx] = arr[maxListIdx];
  79. arr[maxListIdx] = maxValue;
  80. }
  81. return arr;
  82. }
  83. }

 

Python

 

  1. # python选择排序标准版本,更多实现版本请查看源文件
  2. # 新建数组版,无需交换
  3. def selection_sort2(arr):
  4. new_list = []
  5. i = 0
  6. l = len(arr)
  7. while (i < l):
  8. min = arr[i]
  9. min_idx = i
  10. j = i + 1
  11. while (j < l):
  12. # 找到并记录下最小值和位置
  13. if (arr[j] < min):
  14. min = arr[j]
  15. min_idx = j
  16. j += 1
  17.  
  18. # 将待排序里最小值添加到新数组中去
  19. new_list.append(min)
  20. # 原数组中删除对应的项
  21. arr.remove(min)
  22. l -= 1
  23.  
  24. return new_list
  25. """
  26. # 选择排序优化版,同时找出最小和最大值进行交换,可减少1半遍历
  27. # 把数列分为前中后三个区间,分别代表最小已排序、中间待排序以及最大已排序区间
  28. # 遍历中间待排序同时找最大和最小值,分别交换到最小值区间和最大值区间
  29. """
  30. def selection_sort(arr):
  31. arr_len = len(arr)
  32. for i in range(arr_len - 1):
  33. # 初始最小值和下标
  34. min_idx = i
  35. min_value = arr[min_idx]
  36. # 初始最大值和下标
  37. max_idx = i
  38. max_value = arr[max_idx]
  39. # 最小和最大序列里最新待交换的下标
  40. # 最小序列的下标从0开始,自前往后递加
  41. min_list_idx = min_idx
  42. # 最大序列的下标从数组最后1位开始,自后往前递减
  43. max_list_idx = arr_len - 1 - i
  44. # 如果最小和最大下标相同,说明只剩下1个数字,则终止循环
  45. if min_list_idx == max_list_idx:
  46. break
  47.  
  48. # 逐一遍历待排序区间,找出最小和最大值
  49. # 待排序区间在最小值序列和和最大值序列之间
  50. # 待比较区间的下标j从i+1开始,到最大已排序前结束
  51. j = i + 1
  52. while j < arr_len - i:
  53. # 从待排序列表找到最小值和最大值及位置
  54. if arr[j] < min_value:
  55. min_idx = j
  56. min_value = arr[min_idx]
  57. elif arr[j] > max_value:
  58. max_idx = j
  59. max_value = arr[max_idx]
  60. j += 1
  61.  
  62. # 如果最小值等于最小序列待交换的值,且最大值等于最大序列里待交换的值,则跳过
  63. if arr[min_idx] == arr[min_list_idx] and arr[max_idx] == arr[
  64. max_list_idx]:
  65. continue
  66.  
  67. print('min_value=', min_value, 'max_value=', max_value, 'min_idx=',
  68. min_idx, 'max_idx=', max_idx, 'min_list_idx=', min_list_idx,
  69. 'max_list_idx=', max_list_idx)
  70. # 先交换小值,再交换大值
  71. arr[min_list_idx], arr[min_idx] = arr[min_idx], arr[min_list_idx]
  72. # 如果最大值被交换了,则需要更新最大值的下标
  73. if arr[min_idx] == max_value:
  74. max_idx = min_idx
  75. arr[max_list_idx], arr[max_idx] = arr[max_idx], arr[max_list_idx]
  76. return arr

 

Go

 

  1. // go选择排序标准版,其他版本请查看源文件
  2. func selectionSort1(arr []int) []int {
  3. var min = arr[0]
  4. var minIdx = 0
  5. var tmp = -1
  6. var arrLen = len(arr)
  7. for i := 0; i < arrLen-1; i++ {
  8. min = arr[i]
  9. minIdx = i
  10. var j = i + 1
  11. for ; j < arrLen; j++ {
  12. // 从待排序列表中找到最小值和位置,用作交换
  13. if arr[j] < min {
  14. min = arr[j]
  15. minIdx = j
  16. }
  17. }
  18. fmt.Println("i=", i, " j=", j, "min=", min, "minIdx=", minIdx, "arr[]=", arr)
  19. // 将待排序里最小值交换到已排序最后面
  20. if minIdx != i {
  21. tmp = arr[i]
  22. arr[i] = min
  23. arr[minIdx] = tmp
  24. }
  25. }
  26. return arr
  27. }
  28. // 选择排序优化版,同时找出最小和最大值进行交换,可减少1半遍历
  29. // 把数列分为前中后三个区间,分别代表最小已排序、中间待排序以及最大已排序区间
  30. // 遍历中间待排序同时找最大和最小值,分别交换到最小值区间和最大值区间
  31. func selectionSort(arr []int) []int {
  32. var minValue int
  33. var maxValue int
  34. var minIdx int
  35. var maxIdx int
  36. var minListIdx int
  37. var maxListIdx int
  38.  
  39. var arrLen = len(arr)
  40. for i := 0; i < arrLen-1; i++ {
  41. // 待排序里面初始最小值和下标
  42. minIdx = i
  43. minValue = arr[minIdx]
  44. // 待排序里面初始最大值和下标
  45. maxIdx = i
  46. maxValue = arr[maxIdx]
  47. // 最小和最大序列里最新待交换的下标
  48. // 最小序列的下标从0开始,自前往后递加
  49. minListIdx = minIdx
  50. // 最大序列的下标从数组最后1位开始,自后往前递减
  51. maxListIdx = arrLen - 1 - i
  52. // 如果最小和最大下标相同,说明只剩下1个数字,则终止循环
  53. if minListIdx == maxListIdx {
  54. break
  55. }
  56. // 逐一遍历待排序区间,找出最小和最大值
  57. // 待排序区间在最小值序列和和最大值序列之间
  58. // 待比较区间的下标j从i+1开始,到最大已排序前结束
  59. for j := i + 1; j < arrLen-i; j++ {
  60. // 从待排序列表中分别找到最小值和最大值
  61. if arr[j] < minValue {
  62. minIdx = j
  63. minValue = arr[minIdx]
  64. } else if arr[j] > maxValue {
  65. maxIdx = j
  66. maxValue = arr[maxIdx]
  67. }
  68. }
  69. // 如果最小值等于最小序列待交换的值,且最大值等于最大序列里待交换的值,则跳过
  70. if arr[minIdx] == arr[minListIdx] && arr[maxIdx] == arr[maxListIdx] {
  71. continue
  72. }
  73. fmt.Println("minValue=", minValue, " maxValue=", maxValue, " minIdx=", minIdx, " maxIdx=", maxIdx, " minListIdx=", minListIdx, " maxListIdx=", maxListIdx)
  74. // 先交换小值,再交换大值
  75. arr[minListIdx], arr[minIdx] = arr[minIdx], arr[minListIdx]
  76. // 如果最大值被交换了,则需要更新最大值的下标
  77. if arr[minIdx] == maxValue {
  78. maxIdx = minIdx
  79. }
  80. arr[maxListIdx], arr[maxIdx] = arr[maxIdx], arr[maxListIdx]
  81. }
  82. return arr
  83. }

 

JS

  1. // js选择排序徐标准版,更多实现版本详见源码文件
  2. // 新建数组版,无需交换
  3. function selectionSort2(arr) {
  4. var min, minIdx
  5. var newArr = []
  6. var arrLen = arr.length
  7. for (var i = 0; i < arrLen; i++) {
  8. min = arr[i]
  9. minIdx = i
  10. let j = i + 1
  11. for (; j < arrLen; j++) {
  12. // 找到并记录下最小值和位置
  13. if (arr[j] < min) {
  14. min = arr[j]
  15. minIdx = j
  16. }
  17. }
  18. console.log('i=' + i, ' j=' + j, 'min=' + min, 'minIdx=' + minIdx, 'arr[]=', arr)
  19. // 将待排序里最小值添加到新数组中去
  20. newArr.push(min)
  21. // 原数组中删除对应的项
  22. arr.splice(minIdx, 1)
  23. arrLen--
  24. i--
  25. }
  26. return newArr
  27. }
  28. // 选择排序优化版,同时找出最小和最大值进行交换,可减少1半遍历
  29. // 把数列分为前中后三个区间,分别代表最小已排序、中间待排序以及最大已排序区间
  30. // 遍历中间待排序同时找最大和最小值,分别交换到最小值区间和最大值区间
  31. function selectionSort(arr) {
  32. let minValue, maxValue, minIdx, maxIdx
  33. let minListIdx, maxListIdx
  34. const arrLen = arr.length
  35. // 外循环,从第1项开始与后面待排序项逐个对比,最后1位无需再比较
  36. for (let i = 0; i < arrLen - 1; i++) {
  37. // 待排序里面初始最小值和下标
  38. minIdx = i
  39. minValue = arr[minIdx]
  40. // 待排序里面初始最大值和下标
  41. maxIdx = i
  42. maxValue = arr[maxIdx]
  43. // 最小和最大序列里最新待交换的下标
  44. // 最小序列的下标从0开始,自前往后递加
  45. minListIdx = minIdx
  46. // 最大序列的下标从数组最后1位开始,自后往前递减
  47. maxListIdx = arrLen - 1 - i
  48. // 如果最小和最大下标相同,说明只剩下1个数字,则终止循环
  49. if (minListIdx === maxListIdx) {
  50. break
  51. }
  52. // 逐一遍历待排序区间,找出最小和最大值
  53. // 待排序区间在最小值序列和和最大值序列之间
  54. // 待比较区间的下标j从i+1开始,到最大已排序前结束
  55. for (let j = i + 1; j < arrLen - i; j++) {
  56. // 从待排序列表中分别找到最小值和最大值
  57. if (arr[j] < minValue) {
  58. minIdx = j
  59. minValue = arr[minIdx]
  60. } else if (arr[j] > maxValue) {
  61. maxIdx = j
  62. maxValue = arr[maxIdx]
  63. }
  64. }
  65. // 如果最小值等于最小序列待交换的值,且最大值等于最大序列里待交换的值,则跳过
  66. if (arr[minIdx] === arr[minListIdx] && arr[maxIdx] === arr[maxListIdx]) {
  67. continue
  68. }
  69. console.log('minValue=', minValue, 'maxValue=', maxValue, 'minIdx=', minIdx, 'maxIdx=', maxIdx, 'minListIdx=', minListIdx, 'maxListIdx=', maxListIdx)
  70. // 先交换小值,再交换大值
  71. ;[arr[minListIdx], arr[minIdx]] = [arr[minIdx], arr[minListIdx]]
  72. // 如果最大值被交换了,则需要更新最大值的下标
  73. if (arr[minIdx] === maxValue) {
  74. maxIdx = minIdx
  75. }
  76. ;[arr[maxListIdx], arr[maxIdx]] = [arr[maxIdx], arr[maxListIdx]]
  77. }
  78. return arr
  79. }

 

 

TS

  1. // TS标准版,其他版本请查看源码文件
  2. class SelectionSort {
  3. constructor() {}
  4. // 标准版
  5. selectionSort1(arr: Array<number>) {
  6. let min: number, minIdx: number, tmp: number
  7. let l = arr.length
  8. for (let i = 0; i < l - 1; i++) {
  9. min = arr[i]
  10. minIdx = i
  11. let j = i + 1
  12. for (; j < l; j++) {
  13. // 从待排序列表找到最小值和位置
  14. if (arr[j] < min) {
  15. min = arr[j]
  16. minIdx = j
  17. }
  18. }
  19. // 将待排序里最小值交换到已排序最后面
  20. if (minIdx !== i) {
  21. tmp = arr[i]
  22. arr[i] = min
  23. arr[minIdx] = tmp
  24. }
  25. }
  26. return arr
  27. }
  28. }

  29. class SelectionSort {
  30. // 选择排序优化版,同时找出最小和最大值进行交换,可减少1半遍历
  31. // 把数列分为前中后三个区间,分别代表最小已排序、中间待排序以及最大已排序区间
  32. // 遍历中间待排序同时找最大和最小值,分别交换到最小值区间和最大值区间
  33. sort(arr: Array<number>) {
  34. let minValue: number, maxValue: number, minIdx: number, maxIdx: number
  35. let minListIdx: number, maxListIdx: number
  36. const arrLen = arr.length
  37. // 外循环,从第1项开始与后面待排序项逐个对比,最后1位无需再比较
  38. for (let i = 0; i < arrLen - 1; i++) {
  39. // 待排序里面初始最小值和下标
  40. minIdx = i
  41. minValue = arr[minIdx]
  42. // 待排序里面初始最大值和下标
  43. maxIdx = i
  44. maxValue = arr[maxIdx]
  45. // 最小和最大序列里最新待交换的下标
  46. // 最小序列的下标从0开始,自前往后递加
  47. minListIdx = minIdx
  48. // 最大序列的下标从数组最后1位开始,自后往前递减
  49. maxListIdx = arrLen - 1 - i
  50. // 如果最小和最大下标相同,说明只剩下1个数字,则终止循环
  51. if (minListIdx === maxListIdx) {
  52. break
  53. }
  54. // 逐一遍历待排序区间,找出最小和最大值
  55. // 待排序区间在最小值序列和和最大值序列之间
  56. // 待比较区间的下标j从i+1开始,到最大已排序前结束
  57. for (let j = i + 1; j < arrLen - i; j++) {
  58. // 从待排序列表中分别找到最小值和最大值
  59. if (arr[j] < minValue) {
  60. minIdx = j
  61. minValue = arr[minIdx]
  62. } else if (arr[j] > maxValue) {
  63. maxIdx = j
  64. maxValue = arr[maxIdx]
  65. }
  66. }
  67. // 如果最小值等于最小序列待交换的值,且最大值等于最大序列里待交换的值,则跳过
  68. if (arr[minIdx] === arr[minListIdx] && arr[maxIdx] === arr[maxListIdx]) {
  69. continue
  70. }
  71. // 先交换小值,再交换大值
  72. arr[minIdx] = arr[minListIdx];
  73. arr[minListIdx] = minValue;
  74. // 如果最大值被交换了,则需要更新最大值的下标
  75. if (arr[minIdx] == maxValue) {
  76. maxIdx = minIdx;
  77. }
  78. arr[maxIdx] = arr[maxListIdx];
  79. arr[maxListIdx] = maxValue;
  80. }
  81. return arr
  82. }
  83. }

 

 

C

  1. // c语言选择排序标准版,其他版本请查看源码文件
  2. void *selection_sort1(int arr[], int len)
  3. {
  4. int min_value, min_idx, tmp;
  5. for (int i = 0; i < len - 1; i++)
  6. {
  7. min_value = arr[i];
  8. min_idx = i;
  9. int j = i + 1;
  10. for (; j < len; j++)
  11. {
  12. // 从待排序列表找到最小值和位置
  13. if (arr[j] < min_value)
  14. {
  15. min_value = arr[j];
  16. min_idx = j;
  17. }
  18. }
  19. // 将待排序里最小值交换到已排序最后面
  20. if (min_idx != i)
  21. {
  22. tmp = arr[i];
  23. arr[i] = min_value;
  24. arr[min_idx] = tmp;
  25. }
  26. }
  27. return arr;
  28. }

  29. // 选择排序优化版,同时找出最小和最大值进行交换,可减少1半遍历
  30. // 把数列分为前中后三个区间,分别代表最小已排序、中间待排序以及最大已排序区间
  31. // 遍历中间待排序同时找最大和最小值,分别交换到最小值区间和最大值区间
  32. void *selection_sort(int arr[], int len)
  33. {
  34. int min_value, max_value, min_idx, max_idx;
  35. int min_list_idx, max_list_idx;
  36. for (int i = 0; i < len - 1; i++)
  37. {
  38. // 待排序里面初始最小值和下标
  39. min_idx = i;
  40. min_value = arr[min_idx];
  41. // 待排序里面初始最大值和下标
  42. max_idx = i;
  43. max_value = arr[max_idx];
  44. // 最小和最大序列里最新待交换的下标
  45. // 最小序列的下标从0开始,自前往后递加
  46. min_list_idx = min_idx;
  47. // 最大序列的下标从数组最后1位开始,自后往前递减
  48. max_list_idx = len - 1 - i;
  49. // 如果最小和最大下标相同,说明只剩下1个数字,则终止循环
  50. if (min_list_idx == max_list_idx)
  51. {
  52. break;
  53. }
  54. // 逐一遍历待排序区间,找出最小和最大值
  55. // 待排序区间在最小值序列和和最大值序列之间
  56. // 待比较区间的下标j从i+1开始,到最大已排序前结束
  57. for (int j = i + 1; j < len - i; j++)
  58. {
  59. // 从待排序列表中分别找到最小值和最大值
  60. if (arr[j] < min_value)
  61. {
  62. min_idx = j;
  63. min_value = arr[min_idx];
  64. }
  65. else if (arr[j] > max_value)
  66. {
  67. max_idx = j;
  68. max_value = arr[max_idx];
  69. }
  70. }
  71. // 如果最小值等于最小序列待交换的值,且最大值等于最大序列里待交换的值,则跳过
  72. if (arr[min_idx] == arr[min_list_idx] && arr[max_idx] == arr[max_list_idx])
  73. {
  74. continue;
  75. }
  76. // 先交换小值,再交换大值
  77. arr[min_idx] = arr[min_list_idx];
  78. arr[min_list_idx] = min_value;
  79. // 如果最大值被交换了,则需要更新最大值的下标
  80. if (arr[min_idx] == max_value)
  81. {
  82. max_idx = min_idx;
  83. }
  84. arr[max_idx] = arr[max_list_idx];
  85. arr[max_list_idx] = max_value;
  86. }
  87. return arr;
  88. }

 

 

链接

选择排序算法源码:https://github.com/microwind/algorithms/tree/master/sorts/selectionsort

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

原文链接:https://www.cnblogs.com/letjs/p/17188965.html

 友情链接:直通硅谷  点职佳  北美留学生论坛

本站QQ群:前端 618073944 | Java 606181507 | Python 626812652 | C/C++ 612253063 | 微信 634508462 | 苹果 692586424 | C#/.net 182808419 | PHP 305140648 | 运维 608723728

W3xue 的所有内容仅供测试,对任何法律问题及风险不承担任何责任。通过使用本站内容随之而来的风险与本站无关。
关于我们  |  意见建议  |  捐助我们  |  报错有奖  |  广告合作、友情链接(目前9元/月)请联系QQ:27243702 沸活量
皖ICP备17017327号-2 皖公网安备34020702000426号