选择排序

基本思想

  • 每次从未排序的序列中选择最小的数放置在该未排序序列的第一个
  • 不断循环，直到排序完成

步骤

  • 第一层循环：i=0; i < len(list)-1; i++
  • 第二层循环：j := i + 1; j < len(list); j++
  • 寻找未排序序列中最小的数: if list[j] < list[minIndex] { minIndex = j }
  • 将最小的数与放置到当前未排序序列的第一个: list[i], list[minIndex] = list[minIndex], list[i]

By C++

  1. #include <stdio.h>
  2. #define MaxSize 100
  4. typedef int KeyType;        /*关键字类型*/
  6. typedef char ElemType[10];    /*其他数据项类型*/
  8. typedef struct 
  9. {    
  10.     KeyType key;               /*关键字域*/
  11.     ElemType data;             /*其他数据域*/
  12. } LineList;                    /*线性表元素类型*/
  14. void SelectSort(LineList R[],int n)
  15. {
  16.     int i,j,k;
  17.     LineList tmp;
  18.     for (i=0;i<n-1;i++)
  19.     {    
  20.         k=i;
  21.         for (j=i+1;j<n;j++)
  22.             if (R[j].key<R[k].key) 
  23.                 k=j;        /*用k指出每趟在无序区段的最小元素*/
  24.         tmp=R[i];            /*将R[k]与R[i]交换*/
  25.         R[i]=R[k];
  26.         R[k]=tmp;
  27.     }
  28. }
  30. void main()
  31. {
  32.     LineList R[MaxSize];
  33.     KeyType a[]={75,87,68,92,88,61,77,96,80,72};
  34.     int n=10,i;
  35.     for (i=0;i<n;i++)
  36.         R[i].key=a[i];
  37.     printf("排序前:");
  38.     for (i=0;i<n;i++)
  39.         printf("%3d",R[i].key);
  40.     printf("\n");
  41.     SelectSort(R,n);
  42.     printf("排序后:");
  43.     for (i=0;i<n;i++)
  44.         printf("%3d",R[i].key);
  45.     printf("\n");
  46. }

By Golang

  1. package main
  3. import (
  4.     "fmt"
  5. )
  7. // 选择排序
  8. func selectSort(list []int) []int {
  9.     var minIndex int
  10.     for i := 0; i < len(list)-1; i++ {
  11.         minIndex = i
  12.         for j := i + 1; j < len(list); j++ {
  13.             if list[j] < list[minIndex] { // 寻找未排序序列中最小的数
  14.                 minIndex = j
  15.             }
  16.         }
  17.         list[i], list[minIndex] = list[minIndex], list[i] // 将当前数与最小的数交换位置
  18.         fmt.Println("第", i+1, "趟：", list)                 // 打印每趟的序列
  19.     }
  20.     return list
  21. }
  23. func main() {
  24.     list := []int{75, 87, 68, 92, 88, 61, 77, 96, 80, 72}
  25.     fmt.Println("初始序列:", list)
  26.     result := selectSort(list)
  27.     fmt.Println("最终结果:", result)
  28. }

排序过程

  1. 初始序列: [75 87 68 92 88 61 77 96 80 72]
  3. 第 1 趟： [61 87 68 92 88 75 77 96 80 72]
  4. 第 2 趟： [61 68 87 92 88 75 77 96 80 72]
  5. 第 3 趟： [61 68 72 92 88 75 77 96 80 87]
  6. 第 4 趟： [61 68 72 75 88 92 77 96 80 87]
  7. 第 5 趟： [61 68 72 75 77 92 88 96 80 87]
  8. 第 6 趟： [61 68 72 75 77 80 88 96 92 87]
  9. 第 7 趟： [61 68 72 75 77 80 87 96 92 88]
  10. 第 8 趟： [61 68 72 75 77 80 87 88 92 96]
  11. 第 9 趟： [61 68 72 75 77 80 87 88 92 96]
  13. 最终结果: [61 68 72 75 77 80 87 88 92 96]