（3）選擇排序 (Selection Sort)

算法原理

選擇排序（Selection Sort）是一種簡單直觀的排序算法。它的工作原理如下，首先在未排序序列中找到最?。ù螅┰?，存放到排序序列的起始位置，然后，再從剩余未排序元素中繼續(xù)尋找最小（大）元素，然后放到已排序序列的末尾。以此類推，直到所有元素均排序完畢。

選擇排序的主要優(yōu)點與數(shù)據(jù)移動有關。如果某個元素位于正確的最終位置上，則它不會被移動。選擇排序每次交換一對元素，它們當中至少有一個將被移到其最終位置上，因此對n個元素的序列進行排序總共進行至多n-1次交換。在所有的完全依靠交換去移動元素的排序方法中，選擇排序屬于非常好的一種。

圖片來源于維基百科

實例分析

以數(shù)組 arr = [8, 5, 2, 6, 9, 3, 1, 4, 0, 7] 為例，先直觀看一下每一步的變化，后面再介紹細節(jié)

第一次從數(shù)組 [8, 5, 2, 6, 9, 3, 1, 4, 0, 7] 中找到最小的數(shù) 0，放到數(shù)組的最前面（與第一個元素進行交換）：

                               min
                                ↓
8   5   2   6   9   3   1   4   0   7
↑                               ↑
└───────────────────────────────┘

交換后：

0   5   2   6   9   3   1   4   8   7

在剩余的序列中 [5, 2, 6, 9, 3, 1, 4, 8, 7] 中找到最小的數(shù) 1，與該序列的第一個個元素進行位置交換：

                       min
                        ↓
0   5   2   6   9   3   1   4   8   7
    ↑                   ↑
    └───────────────────┘

交換后：

0   1   2   6   9   3   5   4   8   7

在剩余的序列中 [2, 6, 9, 3, 5, 4, 8, 7] 中找到最小的數(shù) 2，與該序列的第一個個元素進行位置交換（實際上不需要交換）：

       min
        ↓
0   1   2   6   9   3   5   4   8   7
        ↑

重復上述過程，直到最后一個元素就完成了排序。

                   min
                    ↓
0   1   2   6   9   3   5   4   8   7
            ↑       ↑
            └───────┘

                           min
                            ↓
0   1   2   3   9   6   5   4   8   7
                ↑           ↑
                └───────────┘

                       min
                        ↓
0   1   2   3   4   6   5   9   8   7
                    ↑   ↑
                    └───┘

                       min
                        ↓
0   1   2   3   4   5   6   9   8   7
                        ↑   

                                   min
                                    ↓
0   1   2   3   4   5   6   9   8   7
                            ↑       ↑
                            └───────┘  

                               min
                                ↓
0   1   2   3   4   5   6   7   8   9
                                ↑      

                                   min
                                    ↓
0   1   2   3   4   5   6   7   8   9
                                    ↑

圖片來源于維基百科

JavaScript 語言實現(xiàn)

function selectionSort(array) {
  var length = array.length,
      i,
      j,
      minIndex,
      minValue,
      temp;
  for (i = 0; i < length - 1; i++) {
    minIndex = i;
    minValue = array[minIndex];
    for (j = i + 1; j < length; j++) {
      if (array[j] < minValue) {
        minIndex = j;
        minValue = array[minIndex];
      }
    }

    // 交換位置
    temp = array[i];
    array[i] = minValue;
    array[minIndex] = temp;
  }
  return array
}

參考文章

• en.wikipedia.org
• wikibooks
• 維基百科
• Selection sort in JavaScript
• 直接選擇排序(Straight Selection Sort)
• 經(jīng)典排序算法 - 選擇排序 Selection Sort
• 選擇排序算法