This is the 26th day of my participation in the August Text Challenge.More challenges in August

Insertion sort

Basic idea: Insert the records to be sorted one at a time into the previously sorted subsequence by their keyword size until all records are inserted

Insert sort directly

The state of L[n] is as follows:

Insert L[I] into the ordered pair of subsequences L[1,2… i-1] as follows:

① Find the insertion position K of L[I] in the subsequence

② Move all elements in L[k,k+1… I -1] back one position

Copy L[I] to L[k]

Initially, L[1] can be assumed to be an ordered subsequence, and then L[2]~L[n] can be inserted into the previously ordered subsequence successively, and an ordered table can be obtained after n-1 insertion

Insert the sorting code implementation directly

Insert L[I] into the ordered pair of subsequences L[1,2… i-1] as follows:

① Find the insertion position K of L[I] in the subsequence

② Move all elements in L[k,k+1… I -1] back one position

Copy L[I] to L[k]

void  InsertSort(ElemType  A[],int  n){
int  i,j;
for(i = 2; i<=n; i++)if(A[i].key<A[i- 1].key){
A[0]=A[i];
for(j=i- 1; A[0].key<A[j].key; --j)
A[j+1]=A[j]; 
A[j+1]=A[0]; }}Copy the code

Note:

  • A[0] is called “sentry” and can help speed up the search for position K to be inserted
  • The space complexity is O(1), that is, the algorithm is an in-place algorithm
  • Best time complexity: the elements in the table are in order, each element is compared only once and there is no need to move elements, so the best time complexity O(n)
  • Worst time complexity: the elements in the table are in reverse order. In this case, the number of comparisons and moves for the ith element is I and I +1. Therefore, the total number of comparisons and moves for the n elements in the table is: 𝑖=2𝑛 𝑖 +𝑖 +1 = 𝑛2 +2𝑛 𝑖 −3.
  • Average time complexity: the elements to be sorted are random. At this time, the total number of comparison and movement are about 𝑛2/4, so the average time complexity is O(𝑛2).
  • Stability: Direct insertion sort is a stable sort method
  • Applicability: It is suitable for basic ordered sorting list, both sequential storage and chain storage. When chain storage, the position k to be inserted can be searched from front to back