write first
Yesterday I summarized Quick Sort as a self-disciplined "author" (mistake). Yesterday, I said that writing a summary and merge sort article today is definitely not a pigeon (dog head).
Mergesort
Merge sort, as introduced yesterday quick sort It is also a sorting method based on the idea of divide and conquer based on the merge operation. The so-called merge operation refers to the operation of merging two sorted sequences into one sequence. Therefore, based on the idea of divide and conquer and the merge operation, the specific steps of merge sort are as follows.
Recursive method steps:
- Divide the sequence to be sorted into two subsequences, and apply for two spaces of the size of two subsequences to store the two subsequences.
- Two pointers L and R are allocated, and the initial positions respectively point to the starting positions of the two sorted sequences. Then allocate a pointer list, pointing to the starting position of the sequence to be sorted.
- Compare the size of the elements pointed to by the two pointers, place the smaller element at the start of the sequence to be sorted, and add one to the corresponding pointer position (if L points to a small element, add one to L and list, otherwise add one to R and list).
- Repeat step 3 until one of the two pointers of the subsequence reaches the end of the sequence.
- Assign the remaining elements of the sequence to the end of the list directly from the current position of the list to the sequence to be sorted.
An illustration of the sorting steps is as follows:
Suppose the sequence to be sorted is [3,5,9,6,2,8,2,6][3,5,9,6,2,8,2,6][3,5,9,6,2, 8,2,6]
The process is as follows:
The complete code is as follows:
C language version:
#include <stdio.h> #include <stdlib.h> void merge(int nums[], int low, int mid, int high); void mergeSort(int nums[], int low, int high); int main(){ int nums[8] = {3,5,9,6,2,8,2,6}; //sequence to be sorted mergeSort(nums, 0, 8-1); for(int i=0; i<8; i++) //output sorted sequence printf("%d ", nums[i]); printf("\n"); return 0; } void merge(int nums[], int low, int mid, int high){ int n_L, n_R, i, j, k; n_L = mid - low + 1; //length of subsequence 1 n_R = high - mid; //length of subsequence 2 int *nums_L = (int*)malloc(sizeof(int)*n_L); int *nums_R = (int*)malloc(sizeof(int)*n_R); for(i=0; i<n_L; i++) //Assign the first half of the sequence to be sorted to subsequence 1 nums_L[i] = nums[low+i]; for(j=0; j<n_R; j++) //Assign the second half of the sequence to be sorted to subsequence 2 nums_R[j] = nums[mid+1+j]; i = 0, j = 0, k = low; while(i < n_L && j < n_R) //Cyclic comparison of two pointers to two subsequences nums[k++] = nums_L[i] <= nums_R[j] ? nums_L[i++] : nums_R[j++]; while(i < n_L) //Assign all remaining elements to the sequence to be sorted nums[k++] = nums_L[i++]; while(j < n_R) nums[k++] = nums_R[j++]; free(nums_L); free(nums_R); } void mergeSort(int nums[], int low, int high){ int mid; if(low < high){ mid = (low + high) / 2; //Evenly divide the sequence to be sorted mergeSort(nums, low, mid); //Sort first half mergeSort(nums, mid+1, high); //Sort the second half merge(nums, low, mid, high); //Merge two subsequences } }
Python3 version:
class Solution: def merge(self, nums, low, mid, high): n_L = mid - low + 1 #length of subsequence 1 n_R = high - mid #length of subsequence 2 nums_L = [0] * n_L nums_R = [0] * n_R for i in range(n_L): #Assign the first half of the sequence to be sorted to subsequence 1 nums_L[i] = nums[low+i] for j in range(n_R): #Assign the second half of the sequence to be sorted to subsequence 2 nums_R[j] = nums[mid+1+j] i, j, k = 0, 0, low while i < n_L and j < n_R: #Two pointers to two subsequences cyclically compare the size if nums_L[i] < nums_R[j]: nums[k] = nums_L[i] i += 1 else: nums[k] = nums_R[j] j += 1 k += 1 while i < n_L: #Assign all remaining elements to the column to be sorted nums[k] = nums_L[i] i += 1 k += 1 while j < n_R: nums[k] = nums_R[j] j += 1 k += 1 def mergeSort(self, nums, low, high): if low < high: mid = (high + low) // 2 #Equally divide the sequence to be sorted self.mergeSort(nums, low, mid) #Sort first half self.mergeSort(nums, mid+1, high) #Sort the second half self.merge(nums, low, mid, high) #Merge two subsequences return nums nums = [1,4,7,2,5,1,4,3,8,6] #subsequence to be sorted res = Solution().mergeSort(nums, 0, len(nums)-1) print(res)
If there is any misunderstanding, please leave a message and exchange, if you need to reprint, please indicate the source.
If you don't understand, it must be because I didn't speak well. Please leave a message and I will continue to work hard.
Manually code the code and code the code. If it helps you, please leave a like, thank you.
above.