This is the first day of my participation in Gwen Challenge

preface

Algorithms in Java, JS and other languages can be seen everywhere on the network. This paper mainly uses Dart to implement these common sorting algorithms to make a review.

I am Zero. I have added a very detailed comment to the code below, which can be saved and read slowly

Bubble sort

figure

Code implementation

/// Bubble sort
List<int> bubbleSort(List<int> arr) {
  // Iterate over all elements
  for (var i = 0; i < arr.length; ++i) {
    // Start with the second element
    for (var j = i + 1; j < arr.length; ++j) {
      // retrieve the j bit value
      int temp = arr[j];
      // if the j bit is less than the I bit, switch places and put them in front
      if (temp < arr[i]) {
        // Put the I bit into the j bit
        arr[j] = arr[i];
        // Add the temporary j bit to the I bitarr[i] = temp; }}}return arr;
}
Copy the code

Insertion sort

figure

Code implementation

///Insertion sort
List<int> insertionSort(List<int> arr) {
  for (var i = 1; i < arr.length; i++) {
    // Get the zero time value of the current position
    var temp = arr[i];
    // Get the previous digit of the current position (i.e., the last digit previously sorted)
    int j = i - 1;
    // If j>=0 does not end after the sorted value and the zero value is less than the value of the j bit, then the j bit moves back one bit
    while ((j >= 0) && (temp < arr[j])) {
      arr[j + 1] = arr[j];
      // Move forward one bit
      --j;
    }
    // If traversal reaches the appropriate position (i.e., larger than the previous digit, smaller than the next digit), the current space is inserted
    arr[j + 1] = temp;
  }
  // Return the sorted collection
  return arr;
}
Copy the code

Selection sort

figure

Code implementation

///Selection sort
List<int> selectionSort(List<int> arr) {
  // Return if the data is null
  if(arr? .isEmpty ??true) {
    return arr;
  }
  // loop over
  //arr. Length-1
  for (var i = 0; i < arr.length - 1; ++i) {
    // Minimum position
    int minIndex = i;
    // Iterate to get the minimum position
    for (var j = i + 1; j < arr.length; ++j) {
      // Compare the minimum value
      if (arr[j] < arr[minIndex]) {
        // Update the minimum position to the current position of jminIndex = j; }}// The current minimum position is not equal to the I position
    if(i ! = minIndex) {// Switch places
      inttemp = arr[i]; arr[i] = arr[minIndex]; arr[minIndex] = temp; }}// Returns the sorted array
  return arr;
}
Copy the code

Quick sort

figure

Code implementation

///Quick sort
List<int> quickSort(List<int> arr) {
  return _sort(arr, 0, (arr? .length ??0) - 1);
}

///The sorting
List<int> _sort(List<int> arr, int start, int end) {
  // The start position is smaller than the end position
  if (start < end) {
    // Get the base index
    int pivotIndex = _partition(arr, start, end);
    // Sort on the left
    _sort(arr, start, pivotIndex - 1);
    // Sort the right side
    _sort(arr, pivotIndex + 1, end);
  }
  return arr;
}
Copy the code

///Base index
int _partition(List<int> arr, int lo, int hi) {
  int i = lo, j = hi + 1;
  // Get the base value
  int pivot = arr[lo];
  while (true) {
    // Scan from left to right
    while (arr[++i] < pivot) {
      // go to the right
      if (i == hi) {
        break; }}// Scan from right to left
    while (arr[--j] > pivot) {
      // iterate to the left
      if (j == lo) {
        break; }}// I merges with j
    if (i >= j) {
      break;
    }

    // Switch I and j
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
  }
  // Switch the base value to the j bit (the last bit less than the base value ** the j bit was the first bit greater than the base value, the last scan --j)
  arr[lo] = arr[j];
  arr[j] = pivot;
  return j;
}
Copy the code

conclusion

These kinds of common sorting algorithms are the basis for us to learn and understand other algorithms. This article has added very detailed annotations, and I hope my sharing can make you gain