1、 Selection sort

【 thought 】

   The so-called selective sorting , Is to exchange the smallest element with the first element in the current unordered sequence every time .
  1、 find 0 ~ n-1 The minimum value of and 0 The number exchange of positions , here 0 The number of positions is small ;
   2、 Next find 1 ~ n-1 The minimum value of and 1 The number exchange of positions , here 1 The number of positions is the second smallest ;
   3、 Next find 2 ~ n-1 The minimum value of and 2 The number exchange of positions , here 2 The number of positions is the third smallest ;
   …
   In this way , Finally, the sequence is ordered .

【 Code 】

void selectionSort(int arr[], int size) {
     // Selection sort 
    if (size < 2) return ;
    for (int start = 0; start < size; start++) {
    
        int minValInd = start;
        for (int k = start + 1; k < size; k++) {
    
            minValInd = arr[k] < arr[minValInd] ? k : minValInd;
        }
        swap(arr, start, minValInd);
    }
}

2、 Bubble sort

【 thought 】

   Bubble sorting , Is to compare the size of adjacent elements , Who's older, who's back .（ Order from small to large ）
  1、 stay 0 ~ n-1 In the range , By comparing the size of adjacent elements , Finally, the maximum value is put into n-1 Location ;
   2、 stay 0 ~ n-2 In the range , By comparing the size of adjacent elements , The last big value was put into n-2 Location ;
   …
   In this way , Finally, the sequence is ordered .

【 Code 】

void bubbleSort(int arr[], int size) {
    
    if (size < 2) 
        return ;

    for (int end = size - 1; end >= 0; end--) {
    
        for (int second = 1; second <= end; second++) {
    
            if (arr[second - 1] > arr[second]) 
                swap(arr, second - 1, second);
        }
    }
}

3、 Insertion sort

【 thought 】

   The so-called insert sort , Is to put the new element in the right place in the ordered sequence .

  1、 bring 0~0 Range order , The range has only one element , So it's orderly ;
   2、 bring 0~1 Range order , The new element is 1 The number of positions , Compare this value with the value of the ordered position （ namely 0 The value of the location ） size , If the new value is small , Then exchange the two ;
   3、 bring 0~2 Range order , The new element is 2 The number of positions , Compare this value with the ordered sequence in turn （ namely 0 Location and 1 The value of the location ）, Until the value in the sequence is smaller than that value ;
   …
   In this way , Finally, the sequence is ordered .

【 Code 】

void insertSort(int arr[], int size) {
    
    if (size < 2)
        return ;

    for (int end = 1; end < size; end++) {
    
        // at present end The element at position is the new element 
        for (int pre = end - 1; pre >= 0 && arr[pre] > arr[pre + 1]; pre--) {
    
            swap(arr, pre, pre + 1);
        }
    }
}

4、 Use a logarithm to verify the sorting algorithm

/************************************************************************* > File Name:  The logarithm validates the sorting algorithm .cpp > Author: Maureen > Mail: [email protected] > Created Time:  One  4/18 21:03:15 2022 ************************************************************************/

#include <iostream>
using namespace std;

// Array backup 
int* copyArray(int arr[], int size) {
    
    int *ans = new int[size];

    for (int i = 0; i < size; i++) {
    
        ans[i] = arr[i];
    }
    return ans;
}

// Determine whether the array is ordered 
bool isSorted(int arr[], int size) {
    
    if (size < 2) 
        return true;
    int max = arr[0];
    for (int i = 1; i < size; i++) {
    
        if (max > arr[i])
            return false;
    }

    return true;
}

void swap(int arr[], int i, int j) {
    
    int tmp = arr[i];
    arr[i] = arr[j];
    arr[j] = tmp;
}


//0~n-1  Find the minimum value and 0 The number exchange of positions 
//1~n-1  Find the minimum value and 1 The number exchange of positions 
//...
void selectionSort(int arr[], int size) {
     // Selection sort 
    if (size < 2) return ;
    for (int start = 0; start < size; start++) {
    
        int minValInd = start;
        for (int k = start + 1; k < size; k++) {
    
            minValInd = arr[k] < arr[minValInd] ? k : minValInd;
        }
        swap(arr, start, minValInd);
    }
}


//0~n-1  Chinese pairwise comparison , The maximum value is put to n-1 Location 
//0~n-2  Chinese pairwise comparison , The next largest value is put into n-2 Location 
//0~n-3
void bubbleSort(int arr[], int size) {
    
    if (size < 2) 
        return ;

    for (int end = size - 1; end >= 0; end--) {
    
        for (int second = 1; second <= end; second++) {
    
            if (arr[second - 1] > arr[second]) 
                swap(arr, second - 1, second);
        }
    }
}

//0~0  Make it orderly （ Only one element has been completed ）
//0~1 Make it orderly 
//0~2 Make it orderly 
//0~n-1 Make it orderly 
void insertSort(int arr[], int size) {
    
    if (size < 2)
        return ;

    for (int end = 1; end < size; end++) {
    
        // at present end The element at position is the new element 
        for (int pre = end - 1; pre >= 0 && arr[pre] > arr[pre + 1]; pre--) {
    
            swap(arr, pre, pre + 1);
        }
    }
}


int main() {
    
    int maxLen = 50;
    int maxValue = 1000;
    int testTime = 10000;
    
    // Generate random arrays 
    int len = rand() % maxLen;
    int *arr = new int[len];
    for (int i = 0; i < len; i++) {
    
        arr[i] = (int)(rand() % maxValue);
    }

    for (int i = 0; i < testTime; i++) {
    
        int *tmp = copyArray(arr, len);
        //selectionSort(arr, len);
        //bubbleSort(arr, len);
        insertSort(arr, len);
        if (!isSorted(arr, len)) {
    
            for (int i = 0; i < len; i++) {
    
                cout << tmp[i] << " ";
            }
            cout << endl;
            cout << "SelectionSort is wrong!" << endl;
            break;
        }
    }

    return 0;
}