!! Part of this chapter is taken from the network!!

catalogue

        1. Contents of this chapter

2. Algorithm classification

3. Algorithm complexity

4.1 insert sort

4.2 selection and sorting

4.3 bubble sorting

4.4 quick sort

4.5 merge sort

5. Sorting algorithm code

4.1 insert sort

4.2 selection and sorting

4.3 bubbling sequence

4.4 quick sort

4.5 merge sort

1. Contents of this chapter

This chapter will explain insertion, merging, quick sorting, etc.

2. Algorithm classification

Ten common sorting algorithms can be divided into two categories:

• Comparison sort: the relative order between elements is determined by comparison. Because its time complexity cannot exceed O(nlogn), it is also called nonlinear time comparison sort.
• Non comparison sort: the relative order between elements is not determined by comparison. It can break through the lower bound of time based on comparison sort and run in linear time. Therefore, it is also called linear time non comparison sort.

3. Algorithm complexity

• Stable: if a is in front of b and a=b, a is still in front of b after sorting.
• Unstable: if a was originally in front of b and a=b, a may appear after b after sorting.

4.1 insert sort

1. Starting with the first element, the element can be considered to have been sorted
2. Take out the next element and scan the sorted elements from back to front
3. If the element (sorted) is larger than the new element, move the element to the next position
4. Repeat step 3 until you find where the sorted element is less than or equal to the new element
5. After inserting the new element into this position
6. Repeat steps 2 to 5

4.2 selection and sorting

4.3 bubble sorting

4.4 quick sort

1. Select the first number as the benchmark
2. Exchange the number smaller than the benchmark to the front, and the number beat than the benchmark to the back
3. Repeat the second step for the left and right intervals until there is only one number in each interval

4.5 merge sort

1. The input sequence with length n is divided into two subsequences with length n/2
2. The two subsequences are sorted by merging
3. Merge the two sorted subsequences into a final sorting sequence

5. Sorting algorithm code

4.1 insert sort

void insertSort(int* a,int len)
{
    for (int i = 0; i < len - 1; i++) {
        int j = i + 1;
        while (a[j] < a[j - 1] && j > 0) {
            int tmp = a[j];
            a[j] = a[j - 1];
            a[j - 1]=tmp;
            j--;
        }
    }
}

4.2 selection and sorting

void selectionSort(int *a, int len)
{
    int minn = 0;
    for (int i = 0; i < len; i++) {
    	minn = i;
        for (int j = i + 1; j < len; j++) {
            if (a[j] < a[minn]) {
                minn = j;
            }
        }
        int tmp = a[i];
        a[i] = a[minn];
        a[minn] = tmp;
    }
}

4.3 bubbling sequence

void bubbleSort(int* a, int len)
{
    for (int i = 0; i < len - 1; i++) {
        for (int j = 0; j < len - i - 1; j++) {
            if (a[j] > a[j + 1]) {
                int tmp = a[j];
                a[j] = a[j+1];
                a[j+1] = tmp;
            }
        }
    }
}

4.4 quick sort

#include <iostream>
#include <ctime>
#include <cstdlib>

using namespace std;

int a[1000001];

void print(int n)
{
	for(int i=1;i<=n;i++)
		cout<<a[i]<<" ";
	cout<<endl;
}

int getRand(int l,int r)
{
	srand(time(0));
	return rand()%(r-l+1)+l;
}

void quicksort(int l,int r)
{
	int flag=a[getRand(l,r)];
	int i=l,j=r;
	while(i<=j)
	{
		while(a[i]<flag)
			i++;
		while(a[j]>flag)
			j--;
		if(i<=j)
		{
			swap(a[i],a[j]);
			j--,i++;
		}
	}
	if(i<r)
		quicksort(i,r);
	if(l<j)
		quicksort(l,j);
}

int main()
{
	int n;
	cin>>n;
	for(int i=1;i<=n;i++)
		cin>>a[i];
	quicksort(1,n);
	print(n);
	return 0;
}

4.5 merge sort

void MergeSort(int l,int r)
{
	if (l == r) {
		return ;
    }
	int mid = (l + r) / 2;
	MergeSort(l, mid);
	MergeSort(mid + 1, r);
	int i = l, j = mid + 1, k = l;
	while (i <= mid && j <= r) {
		if (a[i] <= a[j]) {
			t[k++] = a[i++];
		} else {
			t[k++] = a[j++];
		}
	}
	while (i <= mid) {
		t[k++] = a[i++];
    }
	while (j <= r) {
		t[k++] = a[j++];
    }
	for (int i = l; i <= r; i++) {
		a[i] = t[i];
    }
}