1. Concept of sorting

Sorting is to make a string of data compare according to a specific law , Perform the arranged operations .

Common sorting algorithms

// Interface of sorting implementation void InsertSort(int* a,int n); // Insert sort void ShellSort(int* a,int n);
// Shell Sort void SelectSort(int* a, int n); // Select sort void AdjustDwon(int* a, int n,
int root); void HeapSort(int* a, int n);// Heap sort // Bubble sort void BubbleSort(int* a,
int n) // Recursive implementation of quick sort // Quick sort hoare edition int PartSort1(int* a, int left, int right);
// Quick sequencing excavation method int PartSort2(int* a, int left, int right); // Quick sort before and after pointer method int
PartSort3(int* a, int left, int right); void QuickSort(int* a, int left, int
right); // Quick sort Non recursive implementation void QuickSortNonR(int* a, int left, int right) //
Recursive implementation of merge sort void MergeSort(int* a, int n) // Non recursive implementation of merge sort void MergeSortNonR(int* a,
int n) // Count sort void CountSort(int* a, int n)
2. Implementation of common sorting

1. Insert sort

Direct insertion

Direct insertion method is a simple insertion sorting method , Is to insert the elements to be sorted one by one into an ordered sequence that has been sorted , Form a new ordered sequence .

It's like {3,6,1,5} Insert into {2,4} in , obtain {1,2,3,4,5,6}.

How did it come about ?

Directly inserted properties

*  1. The closer the element is to order before insertion , The more efficient the insertion is
* 2. Time complexity ：O（N^2）
* 3. Spatial complexity ：O（1）
* 4. stability ： stable

Shell Sort （ Reduce incremental sort ）

Hill sort is to select an integer first , Divide the elements to be sorted into several groups , All those with equal distance are divided into the same group , And sort each group of elements .

Characteristics of Hill sort

*  1. Hill sort is an optimization of direct insertion sort
* 2.gap>1 Are pre sorted , The purpose is to make the sorting elements closer to order .
* 3. Time complexity ：O（N^1.3——N^2）
* 4. stability ： instable
2. Select sort

Select the smallest from the elements to be sorted each time （ maximum ） One of , Place at the beginning of the sequence , Until all elements are arranged .

Select Sorting directly

Direct selection is to compare the elements to be sorted , Choose the largest or smallest one , Then repeat this operation for the remaining elements , Until the remaining elements are 1, Stop operation .

Directly select the characteristics of sorting

* 1. Direct selection and sorting is easy to understand , But the efficiency is not very good , Rarely used in practice
* 2. Time complexity ：O（N^2）
* 3. Spatial complexity ：O（1）
* 4. stability ： instable

Heap sort

Heap sort is a sort algorithm designed by using the data structure heap , It is a kind of selective sorting . Remember to build a lot in ascending order , Build small piles in descending order .

Characteristics of heap sorting

* 1. Heap sort uses heap to select numbers , Much more efficient .
* 2. Time complexity ：O(N*logN)
* 3. Spatial complexity ：O(1)
* 4. stability ： instable
3. Exchange sort

Exchange the order of the two elements according to the comparison results of the two elements , Move the larger value to the tail , Smaller values move forward .

Bubble sort

Characteristics of bubble sorting

*  1. Bubble sort is a sort that is very easy to understand
* 2. Time complexity ：O(N^2)
* 3. Spatial complexity ：O(1)
* 4. stability ： stable

Quick sort

Fast sorting is a sort method of binary tree exchange , Take any element as the reference value , Then the set is divided into two sequences , Left less than right , Repeat as above .

Common ways to divide the interval into left and right halves according to the benchmark value are ：

* 1. hoare edition
* 2. Excavation method
* 3. Front and back pointer versions

4. Merge sort

Merge sort is to sort the existing subsequences , Merge two ordered tables into one ordered table .

Characteristics of merging and sorting

* 1. The disadvantage of merging is the need O(N) Spatial complexity of , The thinking of merging and sorting is more about solving the problem of external sorting in the disk .
* 2. Time complexity ：O(N*logN)
* 3. Spatial complexity ：O(N)
* 4. stability ： stable
5. Non comparative sort

Characteristics of non comparative sorting

*  1. When the count sort is in the data range set , Very efficient , However, the scope of application and scenarios are limited .
* 2. Time complexity ：O(MAX(N, Range ))
* 3. Spatial complexity ：O( Range )
* 4. stability ： stable

Technology
Daily Recommendation