20-Data structure-Internal sort-Insertion sort

Introduction: Insertion sorting basically has two steps. First, obtain the insertion position through comparison, then move to vacate the position that needs to be inserted, and finally insert the value.

Table of Contents

1. Direct insertion sort

1.1 Introduction:

1.2 Code

2. Half-way insertion sort

2.1 Introduction:

2.2 Code:

3. Hill sorting

3.1 Introduction:

3.2. Code:

4. Total code

1. Direct insertion sort

1.1 Introduction:

Direct insertion sorting has two main steps: first find the position that needs to be inserted, then move it, vacate the position, and finally assign a value. The main ideas are in the notes,

Direct insertion sort is suitable for: sequential storage and chain storage

Stability: Stable, because it is inserted directly according to the position, the front and rear positions will not change. (Password: Steady happiness, Chicken feather inserted into turtle shell – (radix sort, bubble sort, direct insertion and half insertion, merge sort))

Time complexity: The best case is O(n), the sequence has been sorted, The worst case is O( $n^{2}$ ),Every number from beginning to end requires movement judgment ,

Space complexity: O(1)

1.2 code

void InsertSort(int *a,int n)
{
//Pass in the array and the actual number of data
int i,j;
for(i=2;i<=n; + + i)
{
//Find the actual position i that needs to be inserted
if(a[i]<a[i-1])//Because it is arranged in increasing order, if it is found that the latter is smaller than the previous, it needs to be sorted, otherwise it will be skipped and replaced with the next data judgment
{
a[0]=a[i];//Put the actual value to be arranged at the sentinel to facilitate comparison later.
\t\t\t
for(j=i-1;a[j]>a[0];--j)//Because data needs to be inserted for sorting, it needs to be moved from back to front to make room for the inserted position.
{
//Give the position in front of the position that needs to be stored, move backward, and vacate the position. When the data pointed to by j is less than or equal to the sentinel, just put the value of the sentinel at the j + 1 position.
a[j + 1]=a[j];
}
//Insert data into the vacated space.
a[j + 1]=a[0];
}
}
}

2. Half-way insertion sort

2.1 Introduction:

Half insertion is an optimization of direct insertion, which reduces the number of keyword comparisons, but the time complexity and space complexity are the same as those of continuous insertion. The number of moves does not change, but only the number of comparisons is reduced. The number of comparisons depends on the element n in the table.

The idea of halving insertion sorting is to start the halving search from the second element to find the position where the element needs to be inserted. Then, perform a halving search. Finally, after the halving search is completed, the low and high positions are interchanged. The low position is The position that needs to be inserted is then moved, and the low position and everything behind it are moved back, and finally a[low]=a[0] is assigned.

2.2 code:

void InsertHalfSort(int *a,int n)
{
int i,j,low,high,mid;
// Sort the array, first use the half method to find the position
for(i=2;i<=n;i + + )
{
a[0]=a[i];//Start the comparison from the second data
low=1;
high=i-1;
while(low<=high)//Search the interval. After the final search is completed, low and high are interchanged next to each other. High + 1 means that the low position is the place that needs to be inserted.
{
mid=(low + high)/2;
if(a[mid]<a[0])
low=mid+1;
else
high=mid-1;
}
//After folding in half, the low and subsequent data are larger than the high, and the low position is the place that needs to be inserted, so the place behind the low machine needs to be moved back and the low data is emptied.
for(j=i-1;j>=low;--j)
{
a[j + 1]=a[j];
}
a[low]=a[0];
}
}

3. Hill sorting

3.1 Introduction:

Hill is different from direct insertion and half-folding, but divides the table into countless sub-tables, divides and merges each time, judges between the sub-tables of each division, sorting and moving, and summarizes the last pass. The sub-table index of each trip is i, i + d

The space complexity is still not O(1)

The time complexity is O( $n^{1.3}$ ), in the worst case it is O( $n^{2}$ )

Stability: Unstable

Applicability: Only suitable for sequential storage. Random access support is required.

3.2.Code:

void ShellSort(int *a,int n)
{
int i,j,d;
//d is each increment, followed by d/2 each time
for(d=n/2;d>=1;d=d/2) //number of d increments
{
//Start the comparison. From the first pass and the first comparison team, it starts from the second data in the comparison team and compares with the previous one. The first one is i-d.
for(i=d + 1;i<=n;i + + )//After the first comparison team is completed, i + +, proceed to the second comparison team
{
if(a[i]<a[i-d])//If compared by increment, if the latter one is smaller than the previous one, then the exception will be recorded and exchanged
{
a[0]=a[i];
for(j=i-d; j>=0 & amp; & amp;a[j]>a[0] ;j=j-d) //Then start from the first data in the queue, move backward, and move to its The next bit is j + d. When the judgment condition is that j is greater than 0 and the current value is larger than the moved value, the data is moved backward.
{
a[j + d]=a[j];
}
//After the movement is completed, the assignment is performed. At this time, the pair exchange is completed.
a[j + d]=a[0];
}
}
}
\t
}

Four. Total code

#include 
//Insertion sort - direct insertion sort
void InsertSort(int *a,int n)
{
//Pass in the array and the actual number of data
int i,j;
for(i=2;i<=n; + + i)
{
//Find the actual position i that needs to be inserted
if(a[i]<a[i-1])//Because it is arranged in increasing order, if it is found that the latter is smaller than the previous, it needs to be sorted, otherwise it will be skipped and replaced with the next data judgment
{
a[0]=a[i];//Put the actual value to be arranged at the sentinel to facilitate comparison later.
\t\t\t
for(j=i-1;a[j]>a[0];--j)//Because data needs to be inserted for sorting, it needs to be moved from back to front to make room for the inserted position.
{
//Give the position in front of the position that needs to be stored, move backward, and vacate the position. When the data pointed to by j is less than or equal to the sentinel, just put the value of the sentinel at the j + 1 position.
a[j + 1]=a[j];
}
//Insert data into the vacated space.
a[j + 1]=a[0];
}
}
}
//Insertion sort - half insertion
void InsertHalfSort(int *a,int n)
{
int i,j,low,high,mid;
// Sort the array, first use the half method to find the position
for(i=2;i<=n;i + + )
{
a[0]=a[i];//Start the comparison from the second data
low=1;
high=i-1;
while(low<=high)//Search the interval. After the final search is completed, low and high are interchanged next to each other. High + 1 means that the low position is the place that needs to be inserted.
{
mid=(low + high)/2;
if(a[mid]<a[0])
low=mid+1;
else
high=mid-1;
}
//After folding in half, the low and subsequent data are larger than the high, and the low position is the place that needs to be inserted, so the place behind the low machine needs to be moved back and the low data is emptied.
for(j=i-1;j>=low;--j)
{
a[j + 1]=a[j];
}
a[low]=a[0];
}
}
//Insertion sort - Hill sort:
void ShellSort(int *a,int n)
{
int i,j,d;
//d is each increment, followed by d/2 each time
for(d=n/2;d>=1;d=d/2) //number of d increments
{
//Start the comparison. From the first pass and the first comparison team, it starts from the second data in the comparison team and compares with the previous one. The first one is i-d.
for(i=d + 1;i<=n;i + + )//After the first comparison team is completed, i + +, proceed to the second comparison team
{
if(a[i]=0 & amp; & amp;a[j]>a[0] ;j=j-d) //Then start from the first data in the queue, move backward, and move to its The next bit is j + d. When the judgment condition is that j is greater than 0 and the current value is larger than the moved value, the data is moved backward.
{
a[j + d]=a[j];
}
//After the movement is completed, the assignment is performed. At this time, the pair exchange is completed.
a[j + d]=a[0];
}
}
}
\t
}

//Print
void PrintSort(int *a,int n)
{
int i;
for(i=1;i<=n;i + + )
{
printf("%d ",a[i]);
}
printf("\\
");
}

int main()
{
    int a[9]={0,49,38,65,97,76,13,27};
    int size=7;
    printf("Start value\\
");
    PrintSort(a,size);
    //Insert 6 into it
    int x;
printf("Please enter the inserted value\\
");
scanf("%d", & amp;x);
a[size + 1]=x;
size + + ;
printf("\Sort after insertion\\
");
//InsertSort(a,size);//Direct insertion sort
//InsertHalfSort(a,size);//Half insertion sort
ShellSort(a,size);//Hill sorting
PrintSort(a,size);
 }