Master several common sorting - Select Sorting

Selection sort It's a simple sort , The time complexity is O(n^2), stay unsorted Find the smallest number in the array of , Then put it in The starting position , Continue to find the smallest element from the remaining unsorted data , Put it at the end of the sorted , And so on , Until all elements are sorted .

Let's take a look at the code for selecting sorting

function selectSort(arr) {
  const len = arr.length;
  var minIndex, temp;
  for (let i=0;i<len;i++) {
      minIndex = i; // Suppose the current circular index is the smallest element 
      for (let j=i+1;j<len;j++) {
          if (arr[j] < arr[minIndex]) {
              minIndex = j; //  Look for the smallest value 
          }
      }
      //  In exchange for minIndex And i The value of the element 
      temp = arr[i];
      arr[i] = arr[minIndex];
      arr[minIndex] = temp;
  }
  return arr;
}
selectSort([6,12,80,91,8,0]);

Copy

Let's draw a diagram to restore all the processes of sorting , As follows

From each cycle, we can know the selection sorting , In fact, first confirm the index of the starting position , Suppose the first is the minimum position , Find a value smaller than the first position from the remaining elements , If the remaining elements are smaller than it , Then confirm that the current index is the minimum index value , And exchange the positions of the two elements .

Then start with the second element , Suppose the second element is the minimum , Then find the smallest element from the remaining elements , If the remaining elements are smaller than it, exchange positions , without , It is normal not to exchange positions , Until the loop reaches the last element .

Be more concise , Choosing to sort is

1、 Suppose the first element is the minimum

2、 Select from the remaining elements and compare the element size with the first element , Confirm the minimum index value , And then switch places

3、 Cycle from the remaining positions , Assume that the remaining position is the minimum , Then select from the remaining elements to compare , Then confirm whether to exchange positions

4、 Cycle until the last index

summary

1、 Selection sort The time complexity is O(n^2)

2、 Suppose the first element is the smallest element , Compare with it in the remaining unsorted elements , If it's smaller , Just confirm the minimum position index , Swap places with it

3、 Among all the remaining unsorted elements , Suppose the first element is the minimum , Then compare with the remaining elements in turn , Confirm the current minimum index of the element , Swap places , In turn, cycle , Until the end of the last cycle