Riguz：Riguz移动页面归并排序至Merge sort，不留重定向

2024-01-18T09:18:28Z

Riguz移动页面归并排序至Merge sort，不留重定向

←上一版本		2024年1月18日 (四) 09:18的版本
（没有差异）

imported>Soleverlee：以“对一个随机点的链表进行排序归并排序（Merge sort）是建立在归并操作上的一种有效的排...”为内容创建页面

2015-03-27T08:58:31Z

以“right|frame|对一个随机点的链表进行排序归并排序（Merge sort）是建立在归并操作上的一种有效的排...”为内容创建页面

新页面

[[Image:Merge_sort_animation2.gif|right|frame|对一个随机点的链表进行排序]]
归并排序（Merge sort）是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。
=算法描述=
#申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
#设定两个指针，最初位置分别为两个已经排序序列的起始位置
#比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
#重复步骤3直到某一指针到达序列尾
#将另一序列剩下的所有元素直接复制到合并序列尾
=示例代码=
==Python==
<source lang="python">
def merge_sort(lst):
if len(lst) <= 1:
return lst

def merge(left, right):
merged = []
while left and right:
merged.append(left.pop(0) if left[0] <= right[0] else right.pop(0))
while left:
merged.append(left.pop(0))
while right:
merged.append(right.pop(0))
return merged

middle = int(len(lst) / 2)
left = merge_sort(lst[:middle])
right = merge_sort(lst[middle:])
return merge(left, right)
</source>
==Java==
<source lang="java">
public static int[] mergeSort(int[] arr){//归并排序 --递归
if(arr.length==1){
return arr;
}
int half = arr.length/2;
int[] arr1 = new int[half];
int[] arr2 = new int[arr.length-half];
System.arraycopy(arr, 0, arr1, 0, arr1.length);
System.arraycopy(arr, half, arr2, 0, arr2.length);
arr1 = mergeSort(arr1);
arr2 = mergeSort(arr2);
return mergeSortSub(arr1,arr2);
}

private static int[] mergeSortSub(int[] arr1,int[] arr2){//归并排序子程序
int[] result = new int[arr1.length+arr2.length];
int i = 0;
int j = 0;
int k = 0;
while(true){
if(arr1[i] < arr2[j]){
result[k] = arr1[i];
if(++i>arr1.length-1){
break;
}
}else{
result[k] = arr2[j];
if(++j>arr2.length-1){
break;
}
}
k++;
}
for(;i<arr1.length;i++){
result[++k] = arr1[i];
}
for(;j<arr2.length;j++){
result[++k] = arr2[j];
}
return result;
}
</source>

[[Category:Algorithm]]

Merge sort - 版本历史

Riguz：​Riguz移动页面归并排序至Merge sort，不留重定向

imported>Soleverlee：​以“对一个随机点的链表进行排序 归并排序（Merge sort）是建立在归并操作上的一种有效的排...”为内容创建页面

Riguz：Riguz移动页面归并排序至Merge sort，不留重定向

imported>Soleverlee：以“对一个随机点的链表进行排序归并排序（Merge sort）是建立在归并操作上的一种有效的排...”为内容创建页面