Sort

The concept of sorting and its application

The concept of sequencing

== Sort ：== So called sorting , Is to make a string of records , According to the size of one or some of the keywords , An operation arranged in ascending or descending order .
== stability ：== Assume in the sequence of records to be sorted , There are multiple records with the same keyword , If sorted , The relative order of these records remains the same , In the original sequence ,r[i]=r[j], And r[i] stay r[j] Before , In the sorted sequence ,r[i] Still in r[j] Before , We call this sort algorithm stable ; Otherwise it is called unstable .
== Internal sorting ：== Sorting in which all data elements are placed in memory .
== External sorting ：== Too many data elements to be in memory at the same time , According to the requirements of the sorting process, data sorting cannot be moved between internal and external storage .

Sorting application

== Come to Jingdong ==

== University Rankings ==

Common sorting algorithms

Implementation of common sorting algorithms

Insertion sort

The basic idea

Direct insertion sort is a simple insertion sort method , The basic idea is this ： Insert the records to be sorted into an ordered sequence one by one according to their key values , Until all the records are inserted , We get a new ordered sequence .

In fact, when we play cards , We use the idea of insertion sort

== But arrays are definitely not ordered , So we have to order the array first ==

First peel out the print array

//  Print array void PrintArray(int* a, int n) {	assert(a);	int i = 0;	for (i = 0; i < n; i++) {		printf("%d ", a[i]);	}	printf("\n");}

Insertion sort

//  Insertion sort void InsertSort(int* a, int n) {	assert(a);	int i = 0;	for (i = 0; i < n - 1; i++)	{		int end = i;		int x = a[end+1];		while (end >= 0) {			// If the number to be inserted is smaller than the number in the sequence, prepare to move the position 			if (a[end] > x) {				a[end + 1] = a[end];				end--;			}			else {				// If the number inserted is larger than that in the order, jump out 				break;			}		}		// Jump out of two situations 		//1.end == -1  When 		//2.break  When 		// hold x to end Front one 		a[end + 1] = x;	}}

The time complexity of insertion sort ：O(N^2^)

best ：O(N) — In order （ Close to order ）

The worst ：O(N^2^) — The reverse

The space complexity of the insertion sort ：O(1)

Shell Sort ( Reduced delta sort ) ( Anyway, hill is awesome )

== Hill sort is optimizing direct insertion sort , And the effect is super obvious ==, Why optimization , Because we know that when the direct insertion sort is close to order, it will be very fast , Then I'll create such an order , Make his time complexity close to O(N),== We know the time complexity of sorting. The best case is O(N)==, And we're close to O(N) It's also quite amazing , Almost close to the ceiling

Hill's ranking method is also called reducing increment method . The basic idea of Hill's ranking is ： Choose an integer first , Divide all the records in the file to be sorted into groups , All records at a distance of are in the same group , And sort the records in each group . then , take , Repeat the above work of grouping and sorting . When they arrive in =1 when , All records are arranged in a unified group .

Hill sort steps

1. Group pre sort ---- Arrays are nearly ordered

Press gap grouping , Insert and sort the grouped values == Divide into gap Group ==

2. Direct insert sort Arrays are nearly ordered , The time complexity of direct insertion is O(N)

== Single group lie more ==

== Multiple groups of inserts ==

Spacing is gap The time complexity of multi group scheduling implementation O(gap*(1+…+N/gap))

best ：O(N)

best ：O(N)

The worst ：O(gap*(1+…+N/gap))

gap The bigger it is , Faster pre scheduling , The less orderly it is after pre arrangement

gap The smaller it is , The slower the pre scheduling , The closer to order after pre arrangement

== Multi group stew in one pot （ We can also stew in one pot if it's troublesome ）==

== Multiple pre sort (gap > 1)+ Directly inserted into the （gap == 1）==

==gap/2==

==gap/3==

Time complexity O(N^1.3^)== Just remember. , Just remember that hill is awesome anyway , Hill sort quickly ==

Test the performance of direct insertion sort and Hill sort （ Let me show you what Hill sort is ）

Code

Sort.h

#pragma once#include <stdio.h>#include <stdlib.h>#include <assert.h>#include <time.h>//  Interface for sorting implementation //  Print array extern void PrintArray(int* a, int n);//  Insertion sort extern void InsertSort(int* a, int n);//  Shell Sort extern void ShellSort(int* a, int n);//  Selection sort extern void SelectSort(int* a, int n);//  Heap sort extern void AdjustDwon(int* a, int n, int root);extern void HeapSort(int* a, int n);//  Bubble sort extern void BubbleSort(int* a, int n);//  Quick sort recursive implementation //  Quick sort hoare edition extern int PartSort1(int* a, int left, int right);//  Quick sort digging extern int PartSort2(int* a, int left, int right);//  Pointer before and after quick sort extern int PartSort3(int* a, int left, int right);extern void QuickSort(int* a, int left, int right);//  Quick sort   Non recursive implementation extern void QuickSortNonR(int* a, int left, int right);//  Merge sort recursive implementation extern void MergeSort(int* a, int n);//  Merge sort non recursive implementation extern void MergeSortNonR(int* a, int n);//  Count sorting extern void CountSort(int* a, int n);

Sort.c

#define _CRT_SECURE_NO_WARNINGS 1#include "Sort.h"//  Print array void PrintArray(int* a, int n) {	assert(a);	int i = 0;	for (i = 0; i < n; i++) {		printf("%d ", a[i]);	}	printf("\n");}//  Insertion sort void InsertSort(int* a, int n) {	assert(a);	int i = 0;	for (i = 0; i < n - 1; i++)	{		int end = i;		int x = a[end+1];		while (end >= 0) {			// If the number to be inserted is smaller than the number in the sequence, prepare to move the position 			if (a[end] > x) {				a[end + 1] = a[end];				end--;			}			else {				// If the number inserted is larger than that in the order, jump out 				break;			}		}		// Jump out of two situations 		//1.end == -1  When 		//2.break  When 		// hold x to end Front one 		a[end + 1] = x;	}}//  Shell Sort void ShellSort(int* a, int n) {	// grouping 	int gap = n;	// Multiple pre sort （gap>1）+  Directly inserted into the （gap == 1）	while (gap>1){		//gap /= 2;		// Divided by three, we know we don't have to pass 1, So we +1 Let him have a must 1 Conditions 		gap = gap / 3 + 1;		// Single group lie more 		int i = 0;		for (i = 0; i < n - gap; i++) {		int end = i;		int x = a[end + gap];		while (end >= 0) {			if (a[end] > x) {				a[end + gap] = a[end];				// Step length is gap				end -= gap;			}			else {				break;			}		}		a[end + gap] = x;	}	}	}

test.c

#define _CRT_SECURE_NO_WARNINGS 1#include "Sort.h"//  Test the performance comparison of sorting void TestOP(){	// Set a random starting point 	srand(time(NULL));	// The size of the array to be created 	const int N = 100000;	int* a1 = (int*)malloc(sizeof(int) * N);	int* a2 = (int*)malloc(sizeof(int) * N);	for (int i = 0; i < N; ++i)	{		// Ensure that the two arrays are the same 		a1[i] = rand();		a2[i] = a1[i];	}	int begin1 = clock();// Starting time 	InsertSort(a1, N);	int end1 = clock();  // End time 	int begin2 = clock();	ShellSort(a2, N);	int end2 = clock();	int begin3 = clock();	printf("InsertSort:%d\n", end1 - begin1);// End time minus start time  	printf("ShellSort:%d\n", end2 - begin2);	free(a1);	free(a2);}// Test insert sort void TestInsertSort() {	int a[] = { 1,5,3,7,0,9 };	InsertSort(a, sizeof(a) / sizeof(a[0]));		PrintArray(a, sizeof(a) / sizeof(a[0]));}// Test Hill sort void TestShellSort() {	int a[] = { 9,1,2,5,7,4,8,6,3,5 };	ShellSort(a, sizeof(a) / sizeof(a[0]));	PrintArray(a, sizeof(a) / sizeof(a[0]));}int main(){	//TestInsertSort();	//TestShellSort();	TestOP();	return 0;}