Incremental insertion sort algorithm (Incremental) Strategy to solve problems , Add one element at a time to the sorted subsequence , Gradually sort the entire array , Its time complexity is O(n2
). Here is another typical sorting algorithm -- Merge sort , It divides and governs (Divide-and-Conquer) Strategy of , Time complexity is Θ(nlgn). The steps of merging and sorting are as follows :

*
Divide: Set the length to n The input sequence of is divided into two lengths n/2 Subsequence of .

*
Conquer: Merge and sort the two subsequences respectively .

*
Combine: Merge two sorted subsequences into a final sorting sequence .

When describing the steps of merging and sorting, the merging and sorting itself is called , So this is a recursive process .

#include <stdio.h> #define LEN 8 int a[LEN] = { 5, 2, 4, 7, 1, 3, 2, 6 }; void
merge(int start, int mid, int end) { int n1 = mid - start + 1; int n2 = end -
mid; int left[n1], right[n2]; int i, j, k; for (i = 0; i < n1; i++) /* left
holds a[start..mid] */ left[i] = a[start+i]; for (j = 0; j < n2; j++) /* right
holds a[mid+1..end] */ right[j] = a[mid+1+j]; i = j = 0; k = start; while (i <
n1 && j < n2) if (left[i] < right[j]) a[k++] = left[i++]; else a[k++] =
right[j++]; while (i < n1) /* left[] is not exhausted */ a[k++] = left[i++];
while (j < n2) /* right[] is not exhausted */ a[k++] = right[j++]; } void
sort(int start, int end) { int mid; if (start < end) { mid = (start + end) / 2;
printf("sort (%d-%d, %d-%d) %d %d %d %d %d %d %d %d\n", start, mid, mid+1, end,
a[0], a[1], a[2], a[3], a[4], a[5], a[6], a[7]); sort(start, mid); sort(mid+1,
end); merge(start, mid, end); printf("merge (%d-%d, %d-%d) to %d %d %d %d %d %d
%d %d\n", start, mid, mid+1, end, a[0], a[1], a[2], a[3], a[4], a[5], a[6],
a[7]); } } int main(void) { sort(0, LEN-1); return 0; }

Technology
©2019-2020 Toolsou All rights reserved,
TP6 Application examples of verifier and correct verification data ESP8266/ESP32 System : Optimize system startup time 2021 year 2 Chinese programming language ranking 2021 year 1 Monthly programmer salary statistics , average 14915 element CSS architecture design It's not depravity that's terrible , It's about knowing you're falling Gude Haowen serial - You deserve to be an engineer ( Preface ) Software testing BUG describe C Course design of language programming of 《 Student achievement management system 》vue In the project axios Global encapsulation of