1. Insertion sort
What is insertion sort, and what is the principle of insertion sort?
Insertion sort is just like drawing a card and inserting it into the appropriate position.
Principle of code implementation:
for (int i = 1; i < n; i + + )
{
int end = i - 1;
int tmp = a[i];
while (end >= 0)
{
if (a[end] > tmp)
{
a[end + 1] = a[end];
--end;
}
else
{
break;
}
}
a[end + 1] = tmp;
}
Principle simulation diagram:
Time complexity: O(N*N) in the worst case. At this time, the columns to be sorted are in reverse order, or close to reverse order.
The best case is O(N). At this time, the columns to be sorted are in ascending order, or close to ascending order.
Space complexity: O(1)
2. Hill sorting
What is Hill sorting and what is the principle of Hill sorting?
Hill sort is similar to insertion sort but adds a step of pre-sorting before insertion sort.
Pre-sorting is to select a gap before sorting, and sort the small arrays at each gap position, such as an array of length 8, 1, 3, 6, 4, 7, 2, 8, 5. Set gap as 2, then 1 6 7 8 and 3 4 2 5 are a group. First sort 1 6 7 8 and 2 3 4 5, and then the array is 1 2 6 3 7 4 8 5, which becomes a relatively more ordered array
Principle code implementation:
void ShellSort(int* a, int n)//Hill sorting, pre-sorting first, then insertion sorting
{
int gap = n;
while (gap > 1)
{
gap = gap / 2;
for (int i = 0; i < n - gap; i + + )
{
int end = i;
int tmp = a[end + gap];
while (end >= 0)
{
if (a[end] > tmp)
{
a[end + gap] = a[end];
end -= gap;
}
else
{
break;
}
}
a[end + gap] = tmp;
}
}
}
Illustration:
Average time complexity: O(N^1.3)
Space complexity: O(1)
3. Selection sort
Idea: Select a minimum value from the sequence to be sorted each time, and then place it at the beginning of the sequence until all the data to be sorted is completed.
Illustration:
Code implementation:
void SelectSort(int* a, int n)//Select sort deformation
{
int begin = 0;
int end = n - 1;
while (begin < end)
{
int min = begin;
int max = begin;
for (int i = begin; i <= end; i + + )
{
if (a[i] < a[min])
{
min = i;
}
if (a[i] > a[max])
{
max = i;
}
}
Swap( & amp;a[min], & amp;a[begin]);
//If begin and max overlap, max will be switched to the min position, so it must be exchanged once.
if (begin == max)
{
max = min;
}
Swap( & amp;a[max], & amp;a[end]);
begin++;
end--;
}
}
Time complexity: Worst case: O(N^2)
Best case: O(N^2)
Space complexity: O(1)
4. Heap sort
Ideas:
The first step is to construct the unordered sequence into a heap, and select a large top heap or a small top heap according to the ascending and descending order requirements
The second step is to exchange the top element and the last element of the heap, and “sink” the largest element/minimum element to the end of the array
The third step re-adjusts the structure to meet the heap definition, and then continues to exchange the top element of the heap with the current end element
Graphic explanation: If you want the array to be in ascending order, first create a large root heap. We use the upward adjustment algorithm to build a large root heap
Define the subscript of the last element as len
Then exchange the root node and the last node len and then reduce it by one to the penultimate position index. Then use the downward adjustment algorithm to find the second largest element and exchange it with the penultimate element, and loop until until arranged in ascending order.
void AdjustUp(int* a, int child)//big pile
{
int parent = (child - 1) / 2;
//while (parent >= 0)
while (child > 0)
{
if (a[child] > a[parent])
{
Swap( & amp;a[child], & amp;a[parent]);
child = parent;
parent = (child - 1) / 2;
}
else
{
break;
}
}
}
void AdjustDown(int* a, int n, int parent)//Premise: The left subtree must be a large heap/small heap. Here we use a large heap
{
int child = parent * 2 + 1;//parent is equal to (child-1)/2
while (child < n)//The child continues within the array range
{
//The right child exists and the larger of the left and right children is selected.
if (child + 1 <= n & amp; & amp; a[child + 1] > a[child])
{
+ + child;
}
if (a[child] > a[parent])
{
Swap( & amp;a[child], & amp;a[parent]);
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}
}
void HeapSort(int* a, int len)
{
for (int child = 1; child < len; child + + )//Create a large top heap
{
AdjustUp(a, child);
}
int n = len - 1;//The subscript of the last child
while (n > 0)
{
Swap( & amp;a[0], & amp;a[n]);
n--;//Let the maximum value be at the end of the current array
AdjustDown(a, n, 0);
}
}
The time complexity is:
5. Quick sort
Idea: Here we talk about the best way to understand the digging method
1. Select a piece of data (usually the leftmost or rightmost one) and store it in the key variable, forming a pit at the data location.
2. Define an L and an R. L goes from left to right, and R goes from right to left. (If you dig a hole on the far left, you need R to go first; if you dig a hole on the far right, you need L to go first)
3. Let’s dig a pit on the far left as an example. R first finds a location smaller than the key and fills it into the pit. This location is a new pit. Then use L to find a location larger than the key to the right. Put the value into the pit and set the position as the new pit, and repeat until L>=R
, finally fill the key into the last pit, and the first quick sort is completed.
4. After the first pass is completed, the array is divided into a side smaller than the key and a side larger than the key, and then continue to use the recursive method to arrange the left and right sides of the key in ascending order.
First trip illustration:
int PartSort2(int* a, int left, int right)
{
int key = a[left];
int hole = left;
while (left < right)
{ //Find the small value on the right and fill the small value into the hole on the left
while (left<right & amp; & amp;a[right] >= key)
{
right--;
}
a[hole] = a[right];
hole = right;
//Find the big value on the left and fill the big value into the hole on the right
while (left < right & amp; & amp; a[left] <= key)
{
left + + ;
}
a[hole] = a[left];
hole = left;
}
a[left] = key;//Fill in the hole
return left;
}
void QuickSort(int* a, int left, int right)
{
if (left>=right)
{
return;
}
int keyi = PartSort2(a, left, right);
QuickSort(a, left, keyi - 1);
QuickSort(a, keyi + 1, right);
}
6. Counting sorting
Idea: Use a hash table to record the number of each element in the array, such as 1 1, 2 3, 4 6, 3 9 and then output them all in order
void CountSort(int* a, int n)
{
int min = a[0], max = a[0];
for (int i = 0; i < n; i + + )
{
if (a[i] < min)
{
min = a[i];
}
if (a[i] > max)
{
max = a[i];
}
}
int range = max - min + 1;
int* countA = (int*)malloc(sizeof(int) * range);
memset(countA, 0, sizeof(int) * range);
//Number of statistics
for (int i = 0; i < length; i + + )
{
countA[a[i] - min] + + ;
}
//Sort
for (int j = 0; j < range; j + + )
{
while (countA[j]--)//Sort in ascending order
{
a[k + + ] = j + min;
}
}
}
The knowledge points of the article match the official knowledge files, and you can further learn related knowledge. Algorithm skill tree Home page Overview 56,890 people are learning the system