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