1. Bubble sorting
Average time complexity: O(n^2)
Worst time complexity: O(n^2)
Space complexity: O(1)
Stable: Yes
Principle: it repeatedly visits the sequence to be sorted, compares two elements at a time, and exchanges them if they are in the wrong order. The work of visiting the sequence is repeated until there is no need to exchange, that is, the sequence has been sorted. The name of this algorithm comes from the fact that smaller elements will slowly "float" to the top of the sequence through exchange.

// When the sequence itself is in order, you only need to scan it once
void BubbleSortFlag(vector<int>& vec) {
    for (int i = 0; i < vec.size() - 1; i++) {
        bool swapFlag = true;
        for (int j = 0; j < vec.size() - 1 - i; j++) {
            if (vec[j] > vec[j + 1]) {
                swap(vec[j], vec[j + 1]);
                swapFlag = false;
            }
        }
        if (swapFlag) break;
    }
}

2. Insert sort
Average time complexity: O(n^2)
Worst time complexity: O(n^2)
Space complexity: O(1)
Stable: Yes
Principle: by constructing an ordered sequence, for unordered data, scan from back to front in the sorted sequence, find the corresponding position and insert it. In the implementation of insertion sort, in place sort is usually adopted (that is, the sort that only needs the additional space of O(1)). Therefore, in the process of scanning from back to front, the sorted elements need to be moved back step by step to provide insertion space for the latest elements.

//Sequentially select data from the (right) unordered sequence and insert it into the (left) ordered sequence
void InsertSort(vector<int>& vec) {
	// By default, the first element is ordered, and only the remaining n-1 numbers need to be inserted, that is, scanned n-1 times. Therefore, it only needs to start from i = 1
	for (int i = 1; i < vec.size(); i++) {
		int temp = vec[i];
		int j=i-1;
		// Starting from the tail of the ordered sequence, it is convenient to move. i was ordered before
		for (; j >= 0; j--) {//Find where to insert
			if(vec[j]>temp) vec[j + 1] = vec[j];//Data movement
			else break;
		}
		vec[j + 1] = temp; // insert
	}
}

3. Select sort
Average time complexity: O(n^2)
Worst time complexity: O(n^2)
Space complexity: O(1)
Stable: no
Principle: first, find the smallest (large) element in the unordered sequence and store it at the beginning of the sorted sequence. Then, continue to find the smallest (large) element from the remaining unordered elements, and then put it at the end of the sorted sequence. And so on until all elements are sorted.

void SelectSort(vector<int>& vec) {
	// Traverse n-1 times
	for (int i = 0; i < vec.size() - 1; i++) {
		int minn = i;
		for (int j = i + 1; j < vec.size(); j++) {//Find the location of the minimum value
			if (vec[j] < vec[minn]) minn = j;
		}
		if(minn != i)
			swap(vec[minn], vec[i]); //  Put the maximum value at the starting position
	}
}

4. Merge sort
Average time complexity: O(nlog2n)
Worst time complexity: O(nlog2n)
Space complexity: O(n)
Stable: Yes
Principle: it is a very typical application of Divide and Conquer, and each layer of Divide and Conquer recursion can be carried out at the same time. Segmentation: recursively divide the current sequence into two halves. Integration: integrate the subsequences obtained in the previous step (merge) while maintaining the element order.

//Merge two ordered arrays with subscripts l~mid and mid+1~r respectively
void merge(vector<int>& vec, int l, int mid, int r) {
	vector<int> temp(r - l + 1);
	int i=l,j=mid+1,k=0;
	while (i <= mid && j<=r) {
		if (vec[i] < vec[j]) {
			temp[k++] = vec[i++];
		}
		else {
			temp[k++] = vec[j++];
		}
	}
	while (i <= mid) {
		temp[k++] = vec[i++];
	}
	while (j <= r) {
		temp[k++] = vec[j++];
	}
	//copy the contents of temp back to vec[l...r]
	for(i = 0; i < r-l+1; i++){
		vec[l+i] = temp[i];
	}
}

//Traditional recursive divide and conquer
void MergeSort(vector<int>& vec, int l, int r) {
	if (l >= r) return;
	
	int mid = l + (r - l) / 2;
	MergeSort(vec, l, mid);
	MergeSort(vec, mid + 1, r);
	
	//Merge vec[1...mid] and vec[mid+1...r] into vec[l...r]
	merge(vec, l, mid, r);
}

5. Quick sort
Average time complexity: O(nlog2n)
Worst complexity: n ^ 2
Space complexity: O(log2n)
Stable: no
tip: insert sorting is more effective when the array is small.

// Start from right to left to find the number smaller than pivot, then from left to right to find the number larger than pivot, then exchange, and repeat the above steps until I > = J
int partition(vector<int>& vec, int l, int r) {
	int pivot = vec[l];
	int i = l, j = r; // i=l + 1 is not allowed. When l+1=r, 1 and 2 numbers will be exchanged. In fact, they should not be exchanged. i=l, because the position of i will not be changed when calculating the position of j, even if the exchange is in place
	while (i < j) {
		while (i < j && vec[j] >= pivot) j--;
		while (i < j && vec[i] <= pivot) i++;	// Why is the equal sign? Because i starts from l and is compared with itself. If equality is not considered, i advances one less bit
		if (i < j) swap(vec[i], vec[j]);
	}
	if (l != i) {
		vec[l] = vec[i];
		vec[i] = pivot;
	}
	return i;
}
void QuickSort(vector<int>& vec, int l, int r) {
	if (l >= r) return;
	int q = partition(vec, l, r);//Get partition point subscript

	QuickSort(vec, l, q-1);
	QuickSort(vec, q + 1, r);
}
void sort(vector<int>& vec) {
	QuickSort(vec, 0, vec.size()-1);
}