免費(fèi)AI編程助手
（3）選擇排序 (Selection Sort)
算法原理
選擇排序（Selection Sort）是一種簡(jiǎn)單直觀的排序算法。它的工作原理如下，首先在未排序序列中找到最?。ù螅┰?，存放到排序序列的起始位置，然后，再從剩余未排序元素中繼續(xù)尋找最?。ù螅┰?，然后放到已排序序列的末尾。以此類推，直到所有元素均排序完畢。
選擇排序的主要優(yōu)點(diǎn)與數(shù)據(jù)移動(dòng)有關(guān)。如果某個(gè)元素位于正確的最終位置上，則它不會(huì)被移動(dòng)。選擇排序每次交換一對(duì)元素，它們當(dāng)中至少有一個(gè)將被移到其最終位置上，因此對(duì)n個(gè)元素的序列進(jìn)行排序總共進(jìn)行至多n-1次交換。在所有的完全依靠交換去移動(dòng)元素的排序方法中，選擇排序?qū)儆诜浅：玫囊环N。
圖片來源于維基百科
實(shí)例分析
以數(shù)組 arr = [8, 5, 2, 6, 9, 3, 1, 4, 0, 7] 為例，先直觀看一下每一步的變化，后面再介紹細(xì)節(jié)
第一次從數(shù)組 [8, 5, 2, 6, 9, 3, 1, 4, 0, 7] 中找到最小的數(shù) 0，放到數(shù)組的最前面（與第一個(gè)元素進(jìn)行交換）：
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，與該序列的第一個(gè)個(gè)元素進(jìn)行位置交換：
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，與該序列的第一個(gè)個(gè)元素進(jìn)行位置交換（實(shí)際上不需要交換）：
min
↓
0 1 2 6 9 3 5 4 8 7
↑重復(fù)上述過程，直到最后一個(gè)元素就完成了排序。
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 語言實(shí)現(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
}
更多建議：