- 2020-06-03 05:11
*views 3*- Data structure and algorithm series

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

- Java378 articles
- Python197 articles
- Linux110 articles
- MySQL83 articles
- Vue78 articles
- SpringBoot68 articles
- Spring61 articles
- javascript56 articles
- more...

Daily Recommendation

©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