【Day22】[演算法]-选择排序法Selection Sort

选择排序法(Selection Sort)，原理是反覆从未排序数列中找出最小值，将它与左边的数做交换。可以有两种方式排序，一为由大到小排序时，将最小值放到末端;若由小到大排序时，则将最小值放到前端。例如:未排序的数列中找到最小值的资料，和第1笔资料交换位置，再从剩下未排序的资料列中找到最小值的资料，和第2笔资料交换位置，以此类推。

下面利用40 30 60 50 20由小到大排序。

n=5
第1回合在4个数中找最小值，找4次，n-1次
第2回合在3个数中找最小值，找3次，n-2次
第3回合在2个数中找最小值，找2次，n-3次
第4回合在1个数中找最小值，找1次，n-4次
总共找了4回合，n-1回合

(n-1) + (n-2) + .... + 1 = n(n-1) / 2
平均时间复杂度为: O(n²)

JavaScript

let data = [8,6,1,10,5,3,9,2,7,5]

function SelectionSort(array) { 
  let n = array.length;
  for(let i = 0; i < n; i++) {
    let min = i;
    for(let j = i+1; j < n; j++){
      if(array[j] < array[min]) {
        //记忆最小值的位置
        min=j; 
      }
    }
    if (min != i) {
      [array[i], array[min]] = [array[min], array[i]]; 
    }
  }
  return array;
}
console.log(SelectionSort(data))//[1, 2, 3, 5, 5, 6, 7, 8, 9, 10]

Python

#Selection Sort
data = [89, 34, 23, 78, 67, 100, 66, 29, 79, 55, 78, 88, 92, 96, 96, 23]

def SelectionSort(data):
    n = len(data)
    for i in range(n):
        min_idx = i
        for j in range(i+1, n):
            if data[j] < data[min_idx]:
                min_idx = j
        if min_idx != i:
            data[i], data[min_idx] = data[min_idx], data[i]
    return data        

print(SelectionSort(data))
#[23, 23, 29, 34, 55, 66, 67, 78, 78, 79, 88, 89, 92, 96, 96, 100]