1- Introduction to sorting
sort ： Rearrange unordered keys , Make it orderly
Key set ： Set of keys , Here, the data to be sorted is unique by default , That is, there is no duplicate data , This is an ideal situation , It's usually not the focus
Order ： Ascending and descending
Inner sort and outer sort ： Memory data sorting and external memory data sorting （ Generally, external sorting is realized by calling into memory ）
stability ： Suppose that in a data to be sorted , The same data exists , The physical order before sorting is the same as that after sorting , That is, for all data , Arbitrary sort , As long as you still use this algorithm , The order will not change
Three categories and six sorting algorithms ：
(1)： Direct insertion sort , Shell Sort
(2)： Direct selection sort , Heap sort （ Using complete binary tree ）
(3)： Direct exchange sort （ Bubble sort ）, Quick sort
For each sort algorithm , We usually need to study from the following aspects ：
(1)： algorithm
(2)：C Implementation of code
(3)： Time complexity of the algorithm
(4)： Extreme efficiency analysis of the algorithm （ Best case , Worst case ）
(5)： stability analysis
2- Direct insertion sort for (i = 1; i < count; i++) { tmp = data[i]; for (j = 0; j < i && tmp
>= data[j]; j++) { } for (t = i; t > j; t--) { data[t] = data[t - 1]; // stay j ~
i-1 All elements in are moved back one bit from back to front } data[j] = tmp; } }
3- Direct selection sort for (i = 0; i < count - 1; i++) { minIndex = i; for (j = i; j < count
; j++) { if (data[j] < data[minIndex]) { minIndex = j; } } if (minIndex != i) {
tmp= data[i]; data[i] = data[minIndex]; data[minIndex] = tmp; } }
4- Direct exchange sort （ Bubble sort ） int hasSwap = 1; for (i = 0; hasSwap && i < count - 1; i++) {
hasSwap= 0; for (j = 0; j < count - i - 1; j++) { if (data[j] > data[j+1]) { tmp
= data[j]; data[j] = data[j+1]; data[j+1] = tmp; hasSwap = 1; } } }
To sort a set of numbers to be sorted , Compare two adjacent numbers each time , Of the two numbers , Put the big ones in the back , Small values are swapped to the front , After the first round of exchange , The last number is the largest number in the sequence to be sorted , After the second round , The penultimate number is the second largest number , Stop until there is only one number left
5- Shell Sort ( Improved direct insertion sort ) void shellOneSort(int *data, int count, int start, int step)
{ int i; int j; int t; int tmp; for(i = start + step; i < count; i+=step) {
// Subscript as start+=step Put the elements in a group tmp = data[i]; for(j = start; j < i && tmp >= data[j]
; j += step){ // This group starts direct insertion sorting ; // Traverse to find the right place in turn } for(t = i; t > j; t -= step) {
// The interval between the two values to be exchanged is step data[t] = data[t - step]; // The elements in the middle of the two values are moved back in turn step position } data[j] =
tmp; } } void shellSort(int *data, int count) { int start; int step; for(step =
count/2; step; step/2) { // calculation step,step Cannot be less than 0 for(start = 0; start < step; start++
) { // Control the number of groups ,step Why , Just a few start shellOneSort(data, count, start, step);
// Several start, Sort one group at a time } } }
Direct insertion sort is done in steps of 1 Hill's ranking
6- Heap sort ( Improved direct selection sorting )
Heap sorting is based on direct selection sorting , The concept of complete binary tree is used
be based on Big root pile ( Ascending order ) Small root pile ( Descending order ) Finish sorting
Big root pile ： A complete binary tree , The value of any of its non cotyledon nodes , Both of them are larger than the maximum values in the left and right subtrees （ Small root heap refers to this concept ）
in fact , Any continuous , yes n One dimensional array of elements , Can be regarded as a complete binary tree , And it has the following characteristics ：（ In the subscript 0 Under the premise of ）
If the subscript of a non cotyledon node is i： The left child subscript is 2 * i + 1,
Right child subscript 2 * i + 2, The subscript value of the largest non cotyledon node is n / 2 - 1
The process of sorting with big root heap ：
1- Insert the data in the array into the complete binary tree in turn , Build a big root heap
2- Adjust the big root pile , Until satisfied ： The value of the parent node must be greater than that of the left and right children
3- Compare the number of the last cotyledon node with the maximum value （ Top root node ） Swap positions , The node of the largest number of cotyledons is removed from the big root pile
4- After removal , Continue to adjust the big root heap , Perform the second step , Let big numbers float first , Decimal sinking
After adjustment , Go to the third step , Until sorting is complete
Initialize a large root heap
Using big root heap to complete heap sorting
void adjustHeap(int *data,int count, int root) { int left; int right; int
maxNode; int tmp; while(root <= count/2 - 1) { // count/2-1 Is the largest number of non cotyledon nodes ,
// Including it and larger than it are non cotyledon nodes left = 2*root - 1; right = left + 1; // The left and right child subscripts of the non cotyledon node maxNode =
right>= count ? left :(data[left] > data[right] ? left : right);
// Compare the left and right child size of a non cotyledon node , Right child subscript cannot be greater than or equal to count // The left child is the biggest , Or comparison value , Output subscript with larger value maxNode = data[root]
> data[maxNode] ? root : maxNode; // Compare the value sum of the non cotyledon node maxNode, Identify new maxNode if(maxNode ==
root) { return; // The value of non cotyledon node is the maximum , Do nothing } tmp = data[root]; data[root] = data[
maxNode]; data[maxNode] = tmp; // If not cotyledon point value is small , Then exchange the value root = maxNode;
// Let the value of the new non cotyledon node be maxNode //data[0] Is the root node , here root It means the non cotyledon node for each judgment } } void headSort(int *
data, int count) { int root; int tmp; for(root = count / 2 - 1; root > 0; root--
){ adjustHeap(data, count, root); // Traverse up from the last non cotyledon node // Until there's only the top element left ,
// every time adjust The value of the node and the values of its left and right children , // Make the big value float up , Small values sink }; while(count) { adjustHeap(data, count
, 0); // At this point, adjust the value of the topmost element to the maximum value tmp = data[0]; data[0] = data[count - 1];
// Take out the small value of the cotyledon node at the end of the current array data[count - 1] = tmp; // Put the maximum number in the end of the array --count;
// After getting a maximum every time , // Remove the last cotyledon node // Array length minus one } } 7- Quick sort void quickOnce(int *data, int
count, int head, int tail) { int tmp = data[head]; int start = head; int end =
tail; if (head >= tail) { return; } while (head < tail) { while (head < tail &&
data[tail] >= tmp) { --tail; } if (head < tail) { data[head] = data[tail]; ++
head; } while (head < tail && data[head] <= tmp) { ++head; } if (head < tail) {
data[tail] = data[head]; --tail; } } data[head] = tmp; // Determine the position of the first reference number quickOnce
(data, count, start, head - 1); quickOnce(data, count, head + 1, end);
// For the present tmp The two groups of numbers on the left and right are arranged recursively , // Until there are only two groups left } void qucikSort(int *data, int count) {
quickOnce(data, count, 0, count - 1); }
8- Sorting integration
Through a pointer to a function , Define an array to store the sort type , And define the sort name with macro , when in use , Enter the subscript corresponding to the sort method , It's easy to use
Technology