Selection sort

Selection sort (Selection-sort) It is a simple and intuitive sorting algorithm . How it works ： First, find the minimum in the unsorted sequence （ Big ） Elements , To the beginning of the collating sequence , then , Continue to find the smallest from the remaining unsorted elements （ Big ） Elements , And then at the end of the sorted sequence . And so on , Until all the elements are sorted . 

2.1 Algorithm description

n The direct selection and sorting of records can go through n-1 The direct selection and sorting of passes get ordered results . The specific algorithm is described as follows ：

• The initial state ： The disorder area is R[1..n], The ordered area is empty ;
• The first i Trip to sort (i=1,2,3…n-1) At the beginning of the , At present, the ordered region and the disordered region are R[1..i-1] and R(i..n）. The sequence is from the current unordered area - Select the record with the smallest keyword R[k], Connect it with the disordered area 1 A record R In exchange for , send R[1..i] and R[i+1..n) The number of records increases 1 The number of new ordered areas and records decreased 1 A new disorder area ;
• n-1 The end of the trip , The array is ordered .

2.2 Dynamic diagram demonstration

　　

2.3 Code implementation

function selectionSort(arr) {
    var len = arr.length;
    var minIndex, temp;
    for (var i = 0; i < len - 1; i++) {
        minIndex = i;
        for (var j = i + 1; j < len; j++) {
            if (arr[j] < arr[minIndex]) {     //  Look for the smallest number 
                minIndex = j;                 //  Save the decimal index 
            }
        }
        temp = arr[i];
        arr[i] = arr[minIndex];
        arr[minIndex] = temp;
    }
    return arr;
} 

One of the most stable sorting algorithms , Because whatever data goes in is O(n2) Time complexity of , So when you use it , The smaller the data, the better . The only benefit may be that it doesn't take up extra memory space . Theoretically speaking , Selection sorting may also be the most common sorting method that ordinary people think of .2.4 Algorithm analysis