The concept of sorting:
Sort: The so-called sorting is the operation of arranging a string of records in increasing or decreasing order according to the size of one or some keywords in it.
Stability: Assume that there are multiple records with the same keyword in the record sequence to be sorted. If sorted, the relative order of these records remains unchanged, that is, in the original sequence, r[ i]=r[j], and r[i] is before r[j],and in the sorted sequence, r[i] is still before r[j], then this sorting algorithm is called Stable; otherwise called unstable.
Internal sorting (in-memory sorting): Sorting in which all data elements are placed in memory.
External sorting (sorting on disk): There are too many data elements that cannot be placed in the memory at the same time. According to the requirements of the sorting process, the data cannot be moved between internal and external memory.Note:The eight sortings in this article are all internal sorting, while merge sorting can be said to be internal sorting or external sorting.
Insertion sort:
Basic idea: Insert the records to be sorted into an already sorted sequence one by one according to the size of their key values, until all records are inserted, and a new ordered sequence is obtained. sequence. For example: Landlords.
Direct insertion sort:
When inserting the i (i>=1) element, the previous array[0], array[1],…,array[i-1] have been sorted. At this time, use the sorting code of array[i] and The sorting code order of array[i-1], array[i-2],… is compared. When the insertion position is found, array[i] is inserted, and the order of the elements at the original position is moved backward.
Direct insertion sort implementation:
//Direct insertion sorting
//Time complexity: O(n^2) Complexity range: O(n)-O(n^2)
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 (a[end] > tmp)
{
a[end + 1] = a[end];
}
else
{
break;
}
end--;
}
a[end + 1] = tmp;
}
}
Feature summary of direct insertion sort:
1. The closer the element set is to order, the higher the time efficiency of the direct insertion sort algorithm.
2. Time complexity: O(N^2)
3. Space complexity: O(1), it is a stable sorting algorithm
4. Stability: Stable
Hill sorting (reducing incremental sorting):
Hill sorting method is also called shrinking increment method. The basic idea of Hill sorting method is: first select an integer, divide all the records in the file to be sorted into groups, put all the records with a distance of The records are sorted. Then, repeat the above grouping and sorting work. When =1 is reached, all records are sorted in the same group.
Pre-sorting (gap>1): Large numbers go to the back faster, small numbers go to the front faster, the larger the gap, the faster the jump, the less close to order, the smaller the gap. The slower the jump, the closer it is to ordering. When gap=1, sorting is completed.
//Hill sorting
//Time complexity: O(nlogn) Complexity range: O(n^1.3)-O(nlogn)
void ShellSort(int* a, int n)
{
int gap = n;
while (gap > 1)
{
//gap = gap / 2;
gap = gap / 3 + 1;
for (int i = 0; i < n - gap; i + + )
{
int end = i;
int tmp = a[i + gap];
while (end >= 0)
{
if (a[end] > tmp)
{
a[end + gap] = a[end];
}
else
{
break;
}
end -= gap;
}
a[gap + end] = tmp;
}
}
}
Summary of features of Hill sort:
1. Hill sort is an optimization of direct insertion sort.
2. When gap > 1, it is pre-sorted to make the array closer to order. When gap == 1, the array is already nearly ordered, so it will be fast. In this way, overall optimization results can be achieved. After we implement it, we can compare the performance tests.
3. The time complexity of Hill sorting is difficult to calculate because there are many ways to value gap, which makes it difficult to calculate. Therefore, the time complexity of Hill sorting given in many trees is not fixed:“Data Structure – Description Using Object-Oriented Methods and C++” — Yin Renkun
Because our gap is calculated according to the method proposed by Knuth, and Knuth has conducted a large number of experimental statistics, we will temporarily calculate it according to: O(n^1.25) to O(1.6^1.25).
4. Stability: unstable
Select sort:
Basic idea: Each time, the smallest (or largest) element is selected from the data elements to be sorted and stored at the beginning of the sequence until all the data elements to be sorted are arranged.
Direct selection sorting:
Basic idea:
1. Select the data element with the largest (smallest) key code in the element set array[i]–array[n-1]
2. If it is not the last (first) element in this group of elements, exchange it with the last (first) element in this group of elements
3. Repeat the above steps in the remaining array[i]–array[n-2] (array[i + 1]–array[n-1]) set until there is 1 element left in the set
//Select sort directly
//Time complexity: O(n^2) Complexity range: O(n^2)-O(n^2)
void Swap(int* p1, int* p2)
{
int tmp = *p1;
*p1 = *p2;
*p2 = tmp;
}
void SelectSort(int* a, int n)
{
int end = n - 1;
int begin = 0;
while (end > begin)
{
int maxi = begin;
int mini = begin;
for (int i = begin + 1; i <= end; i + + )
{
if (a[maxi] < a[i])
{
maxi = i;
}
if (a[mini] > a[i])
{
mini = i;
}
}
Swap( & amp;a[maxi], & amp;a[end]);
if (mini == end)
{
mini = maxi;
}
Swap( & amp;a[mini], & amp;a[begin]);
end--;
begin++;
}
}
Feature summary of direct selection sorting:
1. Direct selection and sorting thinking is very easy to understand, but the efficiency is not very good. Rarely used in practice
2. Time complexity: O(N^2)
3. Space complexity: O(1)
4. Stability: unstable
Heap sort:
Heapsort refers to a sorting algorithm designed using a data structure such as a stacked tree (heap). It is a type of selection sorting. It selects data through the heap. It should be noted that a large heap should be built in ascending order, and a small heap should be built in descending order.
//Heap sort
//Time complexity: O(nlogn) Complexity range: O(nlogn)-O(nlogn)
//Adjust downward (create a large pile at this time)
void Swap(int* p1, int* p2)
{
int tmp = *p1;
*p1 = *p2;
*p2 = tmp;
}
void Adjustdown(int* a, int n, int parent)
{
int child = (parent * 2) + 1;
while (child < n)
{
if (child + 1 < n & amp; & amp; a[child] < a[child + 1])
{
child + + ;
}
if (a[parent] < a[child])
{
Swap( & amp;a[child], & amp;a[parent]);
parent = child;
child = (parent * 2) + 1;
}
else
{
break;
}
}
}
void HeapSort(int* a, int n)
{
for (int i = (n - 1 - 1) / 2;i > 0;i--)
{
Adjustdown(a, n, i);
}
int end = n;
while (end > 0)
{
Swap( & amp;a[0], & amp;a[end - 1]);
Adjustdown(a, end - 1, 0);
end--;
}
}
Feature summary of direct selection sorting:
1. Heap sort uses a heap to select numbers, which is much more efficient.
2. Time complexity: O(N*logN)
3. Space complexity: O(1)
4. Stability: unstable
Swap sort:
Basic idea: The so-called exchange is to exchange the positions of the two records in the sequence based on the comparison results of the key values of the two records in the sequence. The characteristics of exchange sorting are: the one with the larger key value Records move toward the tail of the sequence, and records with smaller key values move toward the front of the sequence.
Bubble sort:
Each pass sorts the largest number to the last position in the range. After each pass, the range number is reduced by one. The second pass sorts the next largest number to the penultimate position. When one pass of sorting does not change the order of the array, it means the sorting Completed, exit the loop directly, otherwise sort the entire array in sequence.
//Bubble sort
//Time complexity: O(n^2) Complexity range: O(n)-O(n^2)
void Swap(int* p1, int* p2)
{
int tmp = *p1;
*p1 = *p2;
*p2 = tmp;
}
void BubblingSort(int* a, int n)
{
for (int i = 0; i < n; i + + )
{
int change = 0;
for (int j = 1; j < n - i; j + + )
{
if (a[j - 1] > a[j])
{
Swap( & amp;a[j - 1], & amp;a[j]);
change = 1;
}
}
if (change == 0)
{
break;
}
}
}
Summary of features of bubble sort:
1. Bubble sorting is a very easy to understand sorting
2. Time complexity: O(N^2)
3. Space complexity: O(1)
4. Stability: Stable
Quick sort:
Quick sort is a binary tree structure exchange sorting method proposed by Hoare in 1962. Its basic idea is to take any element in the sequence of elements to be sorted as a reference value, and divide the set to be sorted into two subsequences according to the sorting code. , all elements in the left subsequence are less than the reference value, all elements in the right subsequence are greater than the reference value, and then the process is repeated in the left and right subsequences until all elements are arranged in the corresponding positions.
hoare version:
The right node moves from right to left. If the node’s value is greater than or greater than the base element (a[right] >= a[key]), then move to the left. Otherwise, the left node moves from left to right. If the node’s value is less than or greater than the base element, then move to the left. The element (a[left] <= a[key]) then moves to the right. After it stops, the current node value is exchanged. After the loop ends, the base element is exchanged with the left node. Then divide and conquer recursively to solve the sorting problem.
Note (problems may be missed during the process):
1. When comparing the current node with the base node, the equal sign must be used. Otherwise, when the node value and the base node value are the same, an infinite loop will occur;
2. Pay attention to consider left < right when moving nodes, otherwise the array may go out of bounds;
Q: The encounter position is smaller than the key. How to do it?
Answer: The one on the right who walked first did it.
Encounter situation analysis:
1. R moves and L does not move, and goes to meet L (the meeting position is the position of L. L and R were exchanged in the previous round. After the exchange, the value of the L position is smaller than the key)2. L moved and R did not move, and went to meet R (R went first, found the big one smaller than the key, and stopped. At this time, L looked for the big one but could not find it and met R, and the meeting position was smaller than the key)
Quick sort optimization:
1. Choose the key by finding the middle of three numbers
2. When recursing to a small subrange, you can consider using insertion sort.
//Three numbers to hit
int Middle(int* a,int left, int right)
{
int mid = (left + right) / 2;
if (a[left] > a[right])
{
if (a[left] > a[mid])
{
if (a[right] > a[mid])
{
return right;
}
else
{
return mid;
}
}
else
{
return left;
}
}
else
{
if (a[right] > a[mid])
{
if (a[left] > a[mid])
{
return left;
}
else
{
return mid;
}
}
else
{
return right;
}
}
}
//hoare method
int Hoare(int* a, int left, int right)
{
int mid = Middle(a,left, right);
Swap( & amp;a[left], & amp;a[mid]);
int key = left;
while (left < right)
{
while (left < right & amp; & amp; a[right] >= a[key])
{
right--;
}
while (left < right & amp; & amp; a[left] <= a[key])
{
left + + ;
}
Swap( & amp;a[left], & amp;a[right]);
}
Swap( & amp;a[key], & amp;a[left]);
return left;
}
void QuickSort(int* a, int begin, int end)
{
if (begin >= end)
{
return;
}
int key = Hoare(a, begin, end);
QuickSort(a, begin, key - 1);
QuickSort(a, key + 1, end);
}
Quick sort feature summary:
1. The overall comprehensive performance and usage scenarios of quick sort are relatively good, so we dare to call it quick sort.
2. Time complexity: O(N*logN)3. Space complexity: O(logN)
4. Stability: unstable
Digging method:
First store the first element in the temporary variable front to form a pit (empty), then repeat the steps of the hoare method, and finally fill in the stored elements and pit. Then divide and conquer recursively to solve the sorting problem.
//Three numbers to hit
int Middle(int* a,int left, int right)
{
int mid = (left + right) / 2;
if (a[left] > a[right])
{
if (a[left] > a[mid])
{
if (a[right] > a[mid])
{
return right;
}
else
{
return mid;
}
}
else
{
return left;
}
}
else
{
if (a[right] > a[mid])
{
if (a[left] > a[mid])
{
return left;
}
else
{
return mid;
}
}
else
{
return right;
}
}
}
//dig hole method
int Hold(int* a, int left, int right)
{
int mid = Middle(a, left, right);
Swap( & amp;a[left], & amp;a[mid]);
int front = a[left];
int hold = left;
while (left < right)
{
while (left < right & amp; & amp; a[right] >= front)
{
right--;
}
a[hold] = a[right];
hold = right;
while (left < right & amp; & amp; a[left] <= front)
{
left + + ;
}
a[hold] = a[left];
hold = left;
}
a[hold] = front;
return hold;
}
void QuickSort(int* a, int begin, int end)
{
if (begin >= end)
{
return;
}
int key = Hold(a, begin, end);
QuickSort(a, begin, key - 1);
QuickSort(a, key + 1, end);
}
Up and down pointer method:
Initially, the prev pointer points to the beginning of the sequence, and the cur pointer points to the position after the prev pointer. When a[cur] < a[key] and + + prev != cur, the prev and cur nodes are exchanged, otherwise cur is + 1 alone; After the loop ends, the beginning and prev node values are exchanged. Then divide and conquer recursively to solve the sorting problem.
1cur finds the small value, + + prev, exchange the values of prev and cur
There are two types of prev:
1. When cur has not encountered a value larger than key, prev follows cur.
2. When cur encounters a value larger than key, prev is in front of a group of values larger than key.The essence is to push an interval larger than the key to the right like pushing a box, and at the same time throw the smaller interval to the left.
//Three numbers to hit
int Middle(int* a,int left, int right)
{
int mid = (left + right) / 2;
if (a[left] > a[right])
{
if (a[left] > a[mid])
{
if (a[right] > a[mid])
{
return right;
}
else
{
return mid;
}
}
else
{
return left;
}
}
else
{
if (a[right] > a[mid])
{
if (a[left] > a[mid])
{
return left;
}
else
{
return mid;
}
}
else
{
return right;
}
}
}
//Up and down pointer method
int Pointer(int* a, int left, int right)
{
int mid = Middle(a, left, right);
Swap( & amp;a[left], & amp;a[mid]);
int key = left;
int prev = left;
int cur = left + 1;
while (cur <= right)
{
if (a[cur] < a[key] & amp; & amp; + + prev != cur)
{
Swap( & amp;a[prev], & amp;a[cur]);
}
cur + + ;
}
Swap( & amp;a[key], & amp;a[prev]);
return prev;
}
void QuickSort(int* a, int begin, int end)
{
if (begin >= end)
{
return;
}
int key = Pointer(a, begin, end);
QuickSort(a, begin, key - 1);
QuickSort(a, key + 1, end);
}
Non-recursive implementation of quick sort:
int Pointer(int* a, int left, int right)
{
int mid = Middle(a, left, right);
Swap( & amp;a[left], & amp;a[mid]);
int key = left;
int prev = left;
int cur = left + 1;
while (cur <= right)
{
if (a[cur] < a[key] & amp; & amp; + + prev != cur)
{
Swap( & amp;a[prev], & amp;a[cur]);
}
cur + + ;
}
Swap( & amp;a[key], & amp;a[prev]);
return prev;
}
//Quick sort non-recursive
void QuickSortNonR(int* a, int begin, int end)
{
SL sl;
SLInit( &sl);
SLPush( &sl, end);
SLPush( & amp;sl, begin);
while (!SLEmpty( & amp;sl))
{
int left = SLTTop( & amp;sl);
SLPop( &sl);
int right = SLTTop( & amp;sl);
SLPop( &sl);
int key = Pointer(a, left, right);
if (key + 1 < right)
{
SLPush( & amp;sl, right);
SLPush( & amp;sl, key + 1);
}
if (left < key - 1)
{
SLPush( & amp;sl, key - 1);
SLPush( &sl, left);
}
}
}
Quick sort (optimized):
When there are ten elements left in the sorting divide-and-conquer recursion, insertion sorting is performed directly to complete the sorting (when there are ten remaining elements, divide-and-conquer recursion is also performed, and multiple recursions waste space).
void QuickSort2(int* a, int begin, int end)
{
if (begin >= end)
{
return;
}
//Optimization: direct insertion sorting when there are ten left
if (end - begin + 1 > 10)
{
int key = Pointer(a, begin, end);
QuickSort2(a, begin, key - 1);
QuickSort2(a, key + 1, end);
}
else
{
InsertSort(a + begin,end - begin + 1);
}
}
Merge sort:
Basic idea: Merge sort (MERGE-SORT) is an effective sorting algorithm based on merge operations. This algorithm is a very typical application of the divide and conquer method (Divide and Conquer). Merge the already ordered subsequences to obtain a completely ordered sequence; that is, first make each subsequence orderly, and then make the subsequence segments orderly. If two ordered lists are merged into one ordered list, it is called a two-way merge.
//Merge sort (recursive)
void _MergeSort(int* a,int* tmp,int begin,int end)
{
if (begin >= end)
{
return;
}
int mid = (begin + end) / 2;
_MergeSort(a, tmp, begin, mid);
_MergeSort(a, tmp, mid + 1, end);
int begin1 = begin;
int end1 = mid;
int begin2 = mid + 1;
int end2 = end;
int cur = begin;
while (begin1 <= end1 & amp; & amp; begin2 <= end2)
{
if (a[begin1] < a[begin2])
{
tmp[cur + + ] = a[begin1 + + ];
}
else
{
tmp[cur + + ] = a[begin2 + + ];
}
}
while (begin1 <= end1)
{
tmp[cur + + ] = a[begin1 + + ];
}
while (begin2 <= end2)
{
tmp[cur + + ] = a[begin2 + + ];
}
memcpy(a + begin, tmp + begin, (end - begin + 1) * sizeof(int));
}
//Merge sort
void MergeSort(int* a, int n)
{
int* tmp = (int*)malloc(sizeof(int) * n);
if (tmp == NULL)
{
perror("malloc fail");
return;
}
_MergeSort(a, tmp, 0, n - 1);
free(tmp);
}
Summary of features of merge sort:
1. The disadvantage of merging is that it requires O(N) space complexity. The thinking of merging and sorting is more about solving the external sorting problem on the disk.
2. Time complexity: O(N*logN)
3. Space complexity: O(N)
4. Stability: Stable
Non-recursive implementation of merge sort:
//Merge sort is non-recursive
void MergeSortNonR(int* a, int n)
{
int* tmp = (int*)malloc(sizeof(int) * n);
if (tmp == NULL)
{
perror("malloc fail");
return;
}
int gap = 1;
while (gap < n)
{
for (int i = 0; i < n; i + = 2 * gap)
{
int begin1 = i;
int end1 = i + gap - 1;
int begin2 = i + gap;
int end2 = i + 2 * gap - 1;
int cur = i;
if (begin2 > n - 1)
{
break;
}
if (end2 > n - 1)
{
end2 = n - 1;
}
while (begin1 <= end1 & amp; & amp; begin2 <= end2)
{
if (a[begin1] < a[begin2])
{
tmp[cur + + ] = a[begin1 + + ];
}
else
{
tmp[cur + + ] = a[begin2 + + ];
}
}
while (begin1 <= end1)
{
tmp[cur + + ] = a[begin1 + + ];
}
while (begin2 <= end2)
{
tmp[cur + + ] = a[begin2 + + ];
}
memcpy(a + i, tmp + i, sizeof(int) * (end2 - i + 1));
}
gap *= 2;
}
free(tmp);
}
Non-comparison sorting:
Basic idea: Counting sort, also known as the pigeonhole principle, is a deformed application of the hash direct addressing method.
Steps:
1. Count the number of occurrences of the same element
2. Recycle the sequence into the original sequence based on the statistical results
Counting sort:
Record the number of each element in an array, and then traverse and print out the array.
//Counting sorting
void CountSort(int* a, int n)
{
int max = a[0];
int min = a[0];
for (int i = 0; i < n; i + + )
{
if (a[i] > max)
{
max = a[i];
}
if (a[i] < min)
{
min = a[i];
}
}
//scope
int range = max - min + 1;
int* count = (int*)calloc(range,sizeof(int));
if (count == NULL)
{
perror("ralloc fail");
return;
}
for (int i = 0; i < n; i + + )
{
count[a[i] - min] + + ;
}
int j = 0;
for (int i = 0; i < range; i + + )
{
while (count[i]--)
{
a[j + + ] = i + min;
}
}
}
Feature summary of counting sort:
1. Counting sorting is very efficient when the data range is concentrated, but its applicable scope and scenarios are limited.
2. Time complexity: O(MAX(N, range))
3. Space complexity: O(range)4. Stability: Stable
Complexity and stability analysis of sorting algorithm:
Stability:
Stability: It means that when there are the same elements in the array before sorting, and the relative position of the same elements does not change after the sorting is completed, it means that the sorting is stable. On the contrary, it is unstable. (Test scores are the same, the one who submitted the paper first will be in front)
example:
Before sorting: 2 5 9 6 5 3 7 1
After sorting:1 2 3 5 5 6 7 9 Explain that this sorting algorithm is stable!
On the contrary: after sorting: 1 2 3 5 5 6 7 9 Explain that this sorting algorithm is unstable!
Unstable Analysis:
Hill sort: During pre-sorting, the same elements are assigned to different groups.
Selection sort: Example: 3 3 1 1; In this case, the first 3 has been swapped.
Heap sorting:Example: 9 8 9 6 2; In this case, the order is in ascending order in a large heap, and it will become unstable after the first one is swapped to the end.
Quick sort:Example: 5 8 5 4 5; this type is not exchanged because it is the same. At the end, the first one is unstable when exchanged with left.
Extension:
Because the following ranking is of low practicality, except for examinations, there are basically no inspections, and the work is basically not used, so I will not describe it in detail.
Radix sort: An algorithm for sorting by ones, tens, hundreds, and thousands.
Bucket sort:
The above is the personal opinions and analysis of personal learning of linear tables. All the experts are welcome to comment. District discussion!
Thank you guys for your one-click triple combo! Thanks to the big guys for the one-click three-way connection! Thank you guys for the one-click triple connection!
