1. This code implements a total of 7 common sorts, of which the idea of direct insertion sort and half insertion sort is the same, but the half insertion sort adopts the dichotomy when looking for the insertion position, which is faster than direct insertion sort.

2. Bubble sorting is very simple, but you can go one step further and add a flag in the inner loop j to judge whether there is value exchange in this loop. If so, the value of flag changes. If it doesn't happen, break the loop directly to save time and improve efficiency.

3. Hill sorting belongs to advanced sorting method, which adopts the idea of reducing increment. Before starting a formal sort (this formal sort can be understood as direct insertion sort). First, sort a small part of the sequence. The quantity of this small part is controlled by the increment deta, and then reduce the increment step by step until the increment is 1, that is, it evolves into direct insertion sort. When the direct insertion sort is true, the foreshadowing has been made, and there is no need to spend a lot of time You can finish sorting. However, it is worth noting that there is no unified good method to select incremental functions, but we should ensure that all incremental functions are coprime as much as possible. Before formal Hill sorting, we need to create an incremental array and get the number of elements in the incremental array. This number is the total number of times we sort the sequence.

4. Quick sort, as the name suggests, is the shortest average time among all sorting methods. For it, the more chaotic the original sequence, the faster it will be. If the original sequence itself is orderly, it is not suitable for quick sorting. The central idea of quick sort is to take any element as the central point pivot, if it is the first element, and then take this element as the center, put less than it on the left and greater than it on the right, so as to form the left and right sub tables. Then, using the idea of recursion, quickly sort the left and right sub tables, and the same process. The key point is how to find the location of the center point I selected? The excavation method is adopted here. See the code for details

5. Selection and sorting is very simple and will not be repeated.

The 6. heap sort first needs to understand the meaning of small heap and big heap, and how to build an unordered sequence into a small heap (big root heap), and then how to adjust the heap in the process of sorting.

All seven sort codes are put together

Upper Code:

#include <iostream>
#include <algorithm>
using namespace std;

#define OK 1
#define ERROR 0
#define Status int

typedef struct {
	int* data; //An array that stores primary information
	int length; //Sequence table length
	int listSize; //Space size
}SqList;

//Initialization sequence table
Status InitSqList(SqList& L) {
	L.data = (int *) malloc(100 * sizeof(int));
	L.length = 0;
	L.listSize = 100;
	return OK;
}

//Enter values into the sequence table
void CreatSqList(SqList& L) {
	cout << "Please enter the sequence:(with-1 Is the end number)" << endl;
	int i, index = 1; //Position 0 as sentry
	cin >> i;
	while (i != -1) {
		if (i != -1) {
			L.data[index] = i;
			index++;
			L.length++;
			cin >> i;
		}
		else
			break;
	}
}

//Print sequence table
void PrintSqList(SqList L) {
	cout << "The sequence table is:" << endl;
	for (int i = 1; i <= L.length; i++) {
		cout << L.data[i] << " ";
	}
	cout << endl;
}

//Direct insert sort
void DirectInsertSort(SqList& L) {
	int j;
	for (int i = 2; i <= L.length; i++) {  //i starts from 2. Since 0 is the sentinel and 1 is the starting element, the comparison starts from 2
		if (L.data[i] < L.data[i - 1]) { //Compare only when the value at i is less than i-1, otherwise it is not necessary to compare at all, which saves time
			L.data[0] = L.data[i]; //Give the i-th element value to be compared to the sentinel
			for (j = i - 1; L.data[0] < L.data[j]; j--) {
				L.data[j + 1] = L.data[j]; //Element backward
			}
			L.data[j + 1] = L.data[0];//Insert in the correct position j+1
		}
	}
}

//Split search sort
void HalfInsertSort(SqList& L) {
	for (int i = 2; i <= L.length; i++) { //Insert 2~n elements in turn, except the first one
		int low = 1, high = i - 1;
		L.data[0] = L.data[i]; //sentry
		while (low <= high) {
			int mid = (low + high) / 2;
			if (L.data[i] < L.data[mid])
				high = mid - 1;
			else
				low = mid + 1;
		}//After the while is finished, high + 1 or low is the insertion position, and drawing analysis can be done
		for (int j = i - 1; j >= high + 1; j--) { //Move element to low
			L.data[j + 1] = L.data[j];
		}
		L.data[high + 1] = L.data[0];
	}//for
}

//Advanced bubble sorting
void BubbleSort(SqList& L) {
	int tmp; //Auxiliary variable
	for (int i = 1; i < L.length; i++) { //Note that the first position is useless when creating the sequence table, so start from 1
		int flag = 0;
		for (int j = 1; j < L.length - i + 1; j++) {
			if (L.data[j] > L.data[j + 1]) {
				tmp = L.data[j];
				L.data[j] = L.data[j + 1];
				L.data[j + 1] = tmp;
				flag = 1;
			}
		}
		if (flag == 0)
			break;
	}
}

//Shell Sort 
void ShellInsert(SqList& L, int Increment) {
	int j;
	for (int i = Increment + 1; i <= L.length; i++) { // The number of comparisons corresponding to an increment
		if (L.data[i] < L.data[i - Increment]) { //Sort only when this is the case
			L.data[0] = L.data[i];
			for (j = i - Increment; j > 0 && (L.data[0] < L.data[j]); j = j - Increment) {
				L.data[j + Increment] = L.data[j]; //Element backward
			}
			L.data[j + Increment] = L.data[0];
		}
	}
}

void ShellSort(SqList& L) {
	int Increment[10]; //Incremental sequence
	int cnt = 0; //Calculates the number of elements in the incremental sequence array with several increments
	int i = L.length;
	while (i > 1) {
		i = i / 3 + 1; //The increment is calculated by dividing 3 and 1 to make the increment sequence mutual prime as much as possible
		Increment[cnt] = i; //Assign value to incremental array
		cnt++;
	}
	cout << "The incremental sequence is:";
	for (int j = 0; j < cnt; j++) cout << Increment[j] << " ";
	cout << endl;
	for (int j = 0; j < cnt; j++) {
		ShellInsert(L, Increment[j]);
	}
}

//Quick sort (pit digging method)
int Partition(SqList& L,int low, int high) {//Find the location of the center point and give it to the main program QuickSort
	int pivotValue = L.data[low]; //Take the value at the low position as the center point value. It can be imagined that the value at the low position is hollowed out
	while (low < high) {
		while (low < high && L.data[high] > pivotValue) high--;
		//When the loop jumps out, it indicates that the value at high is less than pivotValue, so it is placed at the hollowed out place on the left, i.e. low
		L.data[low] = L.data[high];
		while (low < high && L.data[low] < pivotValue) low++;
		//When the loop jumps out, it indicates that the value at low is greater than pivotValue, so it is placed in the hollowed out place on the right
		L.data[high] = L.data[low];
	}
	//At the end of the whole cycle, low == high is the position where we want to place the center point. Let's fill in the value first
	L.data[low] = pivotValue; //low or high is OK
	return low;
}

void QuickSort(SqList& L, int low, int high) { //Recursive body of quick sort
	if (low < high) {
		int pivot = Partition(L, low, high);
		QuickSort(L, low, pivot - 1); // Recursive quick sorting of left sub table
		QuickSort(L, pivot + 1, high); // Recursive quick sort of right sub table
	}
}

//Simple selection sort
void SelectSort(SqList& L) {
	for (int i = 1; i < L.length; i++) {
		int k = i; //Auxiliary variables are used to record the location of the minimum value
		for (int j = i + 1; j <= L.length; j++) {
			if (L.data[j] < L.data[i]) k = j; //Record the subscript of the minimum value
		}
		if (k != i) {
			int t;
			t = L.data[k];
			L.data[k] = L.data[i];
			L.data[i] = t;
		}
	}
}

//Heap adjustment
void HeapAdjust(SqList& L, int front, int last) {
	/*
	* It is known that the keywords recorded in R[front...last] meet the definition of heap except R[front]. This function is used to adjust the R[front] keyword
	* Make R[front...last] a small root heap
	*/
	int cur = L.data[front]; //cur indicates the node whose position needs to be adjusted
	for (int i = 2 * front; i <= last; i *= 2) { //i start from the left child of the root node to the right child
		if (i < last && L.data[i] > L.data[i + 1]) i++; //Find the smaller one
		if (cur <= L.data[i]) break; //If the current position to be adjusted is smaller than the smaller one, directly break out of the loop, and the current position is correct
		//If the current is larger, swap down
		L.data[front] = L.data[i]; front = i; //Move the node that needs to be adjusted to position i
	}
	L.data[front] = cur;
}

//Heap sort
void HeapSort(SqList& L) {
	for (int i = L.length / 2; i >= 1; i--) {
		HeapAdjust(L, i, L.length); //Establish the initial small root heap from the unordered sequence
	}
	for (int i = L.length; i > 1; i--) {
		swap(L.data[1], L.data[i]); //The root is swapped with the last element
		//Then perform heap adjustment
		HeapAdjust(L, 1, i - 1);
	}
	//After heap adjustment, because the smallest node in each step is not deleted, all of them are stored in the array
	for (int i = L.length; i >= 1; i--)
		cout << L.data[i] << " ";
	cout << endl;
}

int main() {
	SqList L;

	InitSqList(L);
	CreatSqList(L);
	PrintSqList(L);
	cout << endl;

	int choice;
	while (1) {
		cout << "0.Exit program" << "\n1.Direct insert sort" << "\n2.Sort by half insertion" << "\n3.Bubble sort" << "\n4.Perform Hill sort"  << "\n5.Quick sort" << "\n6.Select sort" << "\n7.Heap sort" << endl;
		cout << "Please enter a selection:";
		cin >> choice;
		switch (choice) {
		case 0:
			cout << "Program exited!";
			exit(0);
		case 1:
			DirectInsertSort(L);
			PrintSqList(L);
			break;
		case 2:
			HalfInsertSort(L);
			PrintSqList(L);
			break;
		case 3:
			BubbleSort(L);
			PrintSqList(L);
			break;
		case 4:
			ShellSort(L);
			PrintSqList(L);
			break;
		case 5:
			QuickSort(L, 1, L.length);
			PrintSqList(L);
			break;
		case 6:
			SelectSort(L);
			PrintSqList(L);
			break;
		case 7:
			HeapSort(L);
			break;
		default:
			break;
		}
	}

}