选择排序

选择排序(Selection sort) 是一种简单直观的排序算法。它的工作原理如下。首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

选择排序的主要优点与数据移动有关。如果某个元素位于正确的最终位置上，则它不会被移动。选择排序每次交换一对元素，它们当中至少有一个将被移到其最终位置上，因此对n个元素的表进行排序总共进行至多n-1次交换。在所有的完全依靠交换去移动元素的排序方法中，选择排序属于非常好的一种。

算法原理

选择排序算法的原理如下：

  • 首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置

  • 再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。

  • 重复第二步，直到所有元素均排序完毕。

选择排序 - 图1

选择排序算法实现:

  1. func main() {
  2.     var arr = []int{19,28,17,5,13,4,6,7,9,3,10}
  3.     //升序
  4.     selectAscendingSort(arr)
  5.     //降序
  6.     selectDescendingSort(arr)
  7. }
  9. //升序
  10. func selectAscendingSort(arr []int) {
  11.     l := len(arr)
  12.     m := len(arr) - 1
  13.     for i := 0; i < m; i++ {
  14.         k := i
  15.         for j := i+1; j < l; j++ {
  16.             if arr[k] > arr[j] {
  17.                 k = j
  18.             }
  19.         }
  20.         if k != i {
  21.             arr[k],arr[i] = arr[i],arr[k]
  22.         }
  23.     }
  25.     fmt.Println("selectAscendingSort:",arr)
  26. }
  28. //降序
  29. func selectDescendingSort(arr []int) {
  30.     l := len(arr)
  31.     m := len(arr) - 1
  32.     for i := 0; i < m; i++ {
  33.         k := i
  34.         for j := i+1; j < l; j++ {
  35.             if arr[k] < arr[j] {
  36.                 k = j
  37.             }
  38.         }
  39.         if k != i {
  40.             arr[k],arr[i] = arr[i],arr[k]
  41.         }
  42.     }
  44.     fmt.Println("selectDescendingSort:",arr)
  45. }

运行结果:

  1. selectDescendingSort: [3 4 5 6 7 9 10 13 17 19 28]
  3. selectAscendingSort: [28 19 17 13 10 9 7 6 5 4 3]