写在最前
昨天总结了快速排序作为一名自律的“撰笔人”(误),昨天说今天写总结归并排序的文章绝对不鸽(狗头)。
归并排序(Mergesort)
归并排序,跟昨天介绍的快速排序同样都是基于分治(divide and conquer)的思想创建在归并操作(merge)上的一种排序方法。所谓归并操作,是指将两个已经排序好的序列合并成一个序列的操作。因此,基于分治法的思想和归并操作,归并排序的具体步骤如下。
递归法步骤:
- 将 待排序序列分成两个子序列,申请两个大小为两个子序列大小的空间,用来存储两个子序列。
- 分配两个指针
L
和R
,最初位置分别指向两个已经排序好的序列的起始位置。再分配一个指针list
,指向待排序序列的起始位置。 - 比较两指针指向位置的元素大小,将较小的元素放置待排序序列起始位置,相应指针位置加一(若
L
指向元素小,则L
和list
加一,否则R
和list
加一)。 - 重复步骤3直到子序列的两指针之一到达序列尾。
- 将未到尾部序列剩下的元素直接从
list
当前位置起全部赋给待排序序列。
排序步骤的图示如下:
假设待排序序列为
[
3
,
5
,
9
,
6
,
2
,
8
,
2
,
6
]
[3,5,9,6,2,8,2,6]
[3,5,9,6,2,8,2,6]
过程如下:
完整的代码如下:
C语言版:
#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};
mergeSort(nums, 0, 8-1);
for(int i=0; i<8; i++)
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;
n_R = high - mid;
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++)
nums_L[i] = nums[low+i];
for(j=0; j<n_R; j++)
nums_R[j] = nums[mid+1+j];
i = 0, j = 0, k = low;
while(i < n_L && j < n_R)
nums[k++] = nums_L[i] <= nums_R[j] ? nums_L[i++] : nums_R[j++];
while(i < n_L)
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;
mergeSort(nums, low, mid);
mergeSort(nums, mid+1, high);
merge(nums, low, mid, high);
}
}
Python3版:
class Solution:
def merge(self, nums, low, mid, high):
n_L = mid - low + 1
n_R = high - mid
nums_L = [0] * n_L
nums_R = [0] * n_R
for i in range(n_L):
nums_L[i] = nums[low+i]
for j in range(n_R):
nums_R[j] = nums[mid+1+j]
i, j, k = 0, 0, low
while i < n_L and j < n_R:
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:
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
self.mergeSort(nums, low, mid)
self.mergeSort(nums, mid+1, high)
self.merge(nums, low, mid, high)
return nums
nums = [1,4,7,2,5,1,4,3,8,6]
res = Solution().mergeSort(nums, 0, len(nums)-1)
print(res)
如果有哪里理解错的地方欢迎大家留言交流,如需转载请标明出处。
如果你没看懂一定是我讲的不好,欢迎留言,我继续努力。
手工码字码图码代码,如果有帮助到你的话留个赞吧,谢谢。
以上。
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)