Kindergarten children will line up to do exercises
Pupils will line up to eat
Aunt shopping will also grab “ line up ” Pay the bill
You as a procedural ape , Do you know the following sorting algorithm ?
Objectives of this section
1. Concept and significance of ranking
2. Implementation and analysis of direct insertion and Hill sort
3. Implementation and analysis of direct selection and heap sorting
First, let's take a look at the basic seven sorts , Today, let's learn the first four together ：
1, Probability and significance of ranking
sort ： So called sorting , Is to make a series of records , According to the size of one or some of the keywords , An increasing or decreasing arrangement Operation from .
stability ： It is assumed that in the sequence of records to be sorted , There are multiple records with the same keyword , If sorted , These records
The relative order of records remains unchanged , That is, in the original sequence ,r[i]=r[j], And r[i] stay r[j] before , And in the sorted sequence ,r[i] still stay r[j] before , The sorting algorithm is said to be stable
of ; Otherwise, it is called unstable .
Internal sorting ： Sorting of all data elements in memory .
External sorting ： There are too many data elements to put in memory at the same time , According to the requirements of sorting process, data cannot be moved between internal and external memory Sort of .
Application of sorting ： For example, when shopping on Taobao, we can , sales volume , Praise …… Sort .
2, Implementation and analysis of direct insertion and Hill sort
2.1. Direct insertion sort
① basic thought
Direct insertion sort is a simple insertion sort method , Its basic idea is ： The records to be sorted are sorted by their key values
Insert into an ordered sequence that has been ordered , Until all records are inserted , A new ordered sequence is obtained . In practice, when we play poker , The idea of insertion sorting is used ：
② Direct insertion sort
Ascending order ：
#include<stdio.h> void InsertSort(int *a, int n) { for (int i = 0; i<n - 1;
i++) { int end = i; int tmp = a[end + 1]; while (end >= 0) { if (n > 1 &&
a[end] > tmp) { a[end + 1] = a[end]; --end; } else { break; } } a[end + 1] =
tmp; } } void PrintArray(int* a, int n) { for (int i = 0; i < n; i++) {
printf("%d ", a[i]); } printf("\n"); } void TestInsertSort() { int a[] = { 1,
3, 2, 6, 8, 7, 9, 4, 5, 0 }; int size = sizeof(a) / sizeof(int); InsertSort(a,
size); PrintArray(a, size); } int main() { TestInsertSort(); return 0; }
thought ： At the beginning of execution ,end Is the subscript of the first element of the array ,tmp Stored is end The value of the next element , Let the array end Value corresponding to subscript and tmp Compare the values of . If in ascending order ,end If the value corresponding to the subscript is greater than tmp The values stored in are exchanged , Then let end--, then while Circular let end Value corresponding to subscript and tmp compare , if end<0 Just jump out , if end The value of the corresponding subscript is less than tmp want break（ Avoid unnecessary comparisons ）, Jump out of the inner loop and let end+1 The subscript corresponds to an array element equal to tmp. Then make end Subscript to the second element , The same method is compared in turn .
summary ：
1. The closer the set of elements is to order , The time efficiency of direct insertion sorting algorithm is higher
2. Time complexity ：O(N^2)
3. Spatial complexity ：O(1), It is a stable sorting algorithm
4. stability ： stable
2.2 Shell Sort
Hill sort can be said to be an advanced version of direct insertion sort .
Hill sorting consists of two parts ： Pre sort （ Near order ）, Direct insertion sort （ Orderly ）
Hill ranking method is also known as reduced incremental method . The basic idea of Hill ranking method is ： Select an integer first , All the files to be sorted
The records are divided into groups , All records with distance are grouped in the same group , And sort the records in each group . then , take , heavy Repeat the above grouping and sorting work . When arrived =1 Time , All records shall be arranged in a unified group .
Observe the following order ：
Multi group interval is gap Pre sort of ,gap Have become smaller
gap Bigger , The larger the number, the faster it can reach the back , The smaller the number, the faster it can get to the front , The less the preorder is, the less ordered it is
gap Smaller , The closer to order
gap==1 It is a direct insertion sort
code ：
#define _CRT_SECURE_NO_WARNINGS 1 #include<stdio.h> // Shell Sort ： Optimization based on direct insertion sorting
//1, First row pre sort , Make the array close to order （ Grouping arrangement ） //2, Direct insertion sort // The time complexity is log₂N*N Or log₃N*N void
ShellSort(int* a, int n) { int gap = n; while (gap > 1) { //gap = gap / 2;
//log₂N gap = gap / 3 + 1;//log₃N //gap>1 All are pre sorted Near order //gap==1 It is a direct insertion sort Orderly
//gap Very large , The following pre sort time complexity O(n) //gap Very hour , Arrays are very close to being ordered , It's almost the same O(n) // Set the interval as gap Multiple groups of data are arranged at the same time for
(int i = 0; i<n - gap; i++) { int end = i; int tmp = a[end + gap]; while (end
>= 0) { if (n > 1 && a[end] > tmp) { a[end + gap] = a[end]; end -= gap; } else
{ break; } } a[end + gap] = tmp; } } } void PrintArray(int* a, int n) { for
(int i = 0; i < n; i++) { printf("%d ", a[i]); } printf("\n"); } void
TestInsertSort() { int a[] = { 1, 3, 2, 6, 8, 7, 9, 4, 5, 0 }; int size =
sizeof(a) / sizeof(int); ShellSort(a, size); PrintArray(a, size); } int main()
{ TestInsertSort(); return 0; }
Summary of characteristics of Hill sort ：
① Hill sort is an optimization of direct insertion sort
② When gap > 1 All are pre sorted , The purpose is to make the array closer to order . When gap == 1 Time ,
Direct insertion sort . The difference between it and direct insertion sort is that there is an additional pre sort , This makes time more efficient
③ The time complexity of hill sorting is not easy to calculate , Derivation is required , The average time complexity is derived ： O(N^1.3— N^2）
④ stability ： instable
3, Implementation and analysis of direct selection and heap sorting
Basic idea of selective sorting ： Select the smallest one from the data elements to be sorted each time （ Or maximum ） An element of , Stored at the beginning of the sequence , Until all the data elements to be sorted are finished .
3.1 Direct selection sorting
code ：
#define _CRT_SECURE_NO_WARNINGS 1 #include<stdio.h> void Swap(int* p1, int*
p2) { int tmp = *p1; *p1 = *p2; *p2 = tmp; } // Direct selection sorting void SelectSort(int* a,
int n) { int begin = 0, end = n - 1; while (begin < end) { int mini = begin,
maxi = begin; for (int i = begin; i <= end; ++i) { if (a[i] < a[mini]) { mini =
i; } if (a[i] > a[maxi]) { maxi = i; } } Swap(&a[mini], &a[begin]); if (maxi ==
begin) { maxi = mini; } Swap(&a[maxi], &a[end]); begin++; --end; } } void
PrintArray(int* a, int n) { for (int i = 0; i < n; i++) { printf("%d ", a[i]);
} printf("\n"); } void TestInsertSort() { int a[] = { 1, 3, 2, 6, 8, 7, 9, 4,
5, 0 }; int size = sizeof(a) / sizeof(int); SelectSort(a, size); PrintArray(a,
size); } int main() { TestInsertSort(); return 0; }
Summary of characteristics of direct selection sorting ：
1. It's very easy to think about direct selection and sorting , 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
3.2 Heap sort
3.2.1 Two characteristics of heap sorting
* Structural ： Complete binary tree represented by array
* Order ： The keyword of any node is the maximum value of all nodes in its subtree （ Or minimum ）
* Maximum heap , Also known as large top reactor ： Maximum
* Minimum heap , Also known as small top pile ： minimum value
* Requirements for large top reactor ： All fathers in the tree are greater than or equal to children
* Requirements for small top pile ： All fathers in the tree are less than or equal to children
3.2.2 Heap physical storage structure and parent-child relationship
The heap is physically stored as an array
A complete binary tree is imaginary
The parent-child relationship can be found by subscript
leftchild=parent*2+1
rightchild=parent*2+1+1=leftchild+1
parent=（child-1）/ 2
3.2.3 Downward adjustment algorithm （ The premise is that both the left and right subtrees must be heaps ）
example ： Build a small pile
Downward adjustment algorithm
First, the left and right subtrees must be small piles
First step , First judge whether the left and right subtrees are small piles , If it is a small heap, the second step down adjustment algorithm can be carried out
Step two , Downward adjustment algorithm , Find the left subtree and the right subtree of the root node , Then compare with the root node. If it is less than the root node, it will be exchanged （ If not less than , Then the whole number is a small pile and does not need to be exchanged ）. Sequential circulation , Terminate until the leaf node is found
If the left and right subtrees are not small piles , You can't directly use the downward adjustment algorithm ! What should I do? ?
way ： Start from the last subtree upside down , Walk backwards , Leaves don't need to be adjusted , Start with the last non leaf subtree , Sequential adjustment , Turn this tree into a pile .
Build a pile in ascending order , Because a lot of root nodes are the maximum value of the whole tree
Build small reactor in descending order , Because the root node of the small heap is the minimum value of the whole tree
After the heap is built, it needs to be sorted , Swap the first with the last , Then the last number is not considered in the heap , front n-1 Adjust the number downward to select the next largest number , Then exchange with the penultimate position
code ：
#define _CRT_SECURE_NO_WARNINGS 1 #include<stdio.h> void Swap(int* p1, int*
p2) { int tmp = *p1; *p1 = *p2; *p2 = tmp; } void AdjustDwon(int* a, int n, int
root) { int parent = root; int child = parent * 2 + 1; // The default is left child while (child <
n) { // 1, Choose the older of the left and right children if (child + 1 < n && a[child + 1] > a[child]) { child +=
1; } if (a[child] > a[parent]) { Swap(&a[child], &a[parent]); parent = child;
child = parent * 2 + 1; } else { break; } } } void HeapSort(int* a, int n) { //
Build pile O(N) for (int i = (n - 1 - 1) / 2; i >= 0; --i) { AdjustDwon(a, n, i); } //
Ascending order , Build a pile or a small pile ? Build a pile int end = n - 1; while (end > 0) { Swap(&a[0], &a[end]);
AdjustDwon(a, end, 0); --end; } } void PrintArray(int* a, int n) { for (int i =
0; i < n; i++) { printf("%d ", a[i]); } printf("\n"); } void TestInsertSort() {
int a[] = { 1, 3, 2, 6, 8, 7, 9, 4, 5, 0 }; int size = sizeof(a) / sizeof(int);
HeapSort(a, size); PrintArray(a, size); } int main() { TestInsertSort(); return
0; }
Summary of characteristics of heap sorting ：
* Heap sorting uses the heap to select numbers , The efficiency is much higher .
* Time complexity ：O(N*logN)
* Spatial complexity ：O(1)
* stability ： instable
Technology