一、C 程序实现
/******************************************************* * Description: 归并排序算法 * Author: shujuxiong * Version: 1.0 * Time: 2018-06-27 *******************************************************/ #include <stdio.h> //函数：打印数组 void PrintDataArray(int a[], int n) { for(int i=0; i<n; i++) printf("%d ",a[i]); printf("\n"); } //merge两个有序数列为一个有序数列 void MergeArr(int a[], int first, int mid, int last, int tmp[]) { int i = first, j = mid+1; int m = mid, n = last; int k=0; //通过比较，归并数列a和b while(i<=m && j<=n) { if(a[i]<a[j]) tmp[k++] = a[i++]; else tmp[k++] = a[j++]; } //将数列a或者b剩余的元素直接插入到新数列后边 while(i<=m) tmp[k++] = a[i++]; while(j<=n) tmp[k++] = a[j++]; for(i=0; i<k; i++) a[first+i] = tmp[i]; //注意是first+i } //归并排序 void MergeSort(int a[], int first, int last, int tmp[]) { if(first<last) { int mid = (first+last)/2; MergeSort(a, first, mid, tmp); MergeSort(a, mid+1, last, tmp); MergeArr(a, first, mid, last, tmp); } } //测试用例 int main() { int a[] = {3,1,7,5,2,4,9,6}; int len = sizeof(a)/sizeof(a[0]); int b[len]; MergeSort(a, 0, len-1, b); PrintDataArray(a, len); return 0; }运行结果：
二、Java 程序实现
/** * @description: 归并排序算法 * @author: shujuxiong * @version: 1.0 * @date： 2018-06-27 */ public class MergeSort { //合并两个有序数组 public static void mergeArr(int[] a, int first, int mid, int last, int[] tmp) { int i = first, j = mid+1; int m = mid, n = last; int k=0; //通过比较，归并数列a和b while(i<=m && j<=n) { if(a[i]<a[j]) tmp[k++] = a[i++]; else tmp[k++] = a[j++]; } //将数列a或者b剩余的元素直接插入到新数列后边 while(i<=m) tmp[k++] = a[i++]; while(j<=n) tmp[k++] = a[j++]; for(i=0; i<k; i++) a[first+i] = tmp[i]; //注意是first+i } //归并排序 public static void mergeSort(int[] a, int first, int last, int[] tmp) { if(first<last) { int mid = (first+last)/2; mergeSort(a, first, mid, tmp); mergeSort(a, mid+1, last, tmp); mergeArr(a, first, mid, last, tmp); } } //方法：打印数组 private static void printDataArray(int[] a) { int N = a.length; for(int i = 0; i < N; i++) System.out.printf("%d ",a[i]); System.out.printf("\n"); } //测试用例 public static void main(String[] args) { int[] arr = {3,1,7,5,2,4,9,6}; int N = arr.length; int[] tmp = new int[N]; mergeSort(arr, 0, N-1, tmp); printDataArray(arr); } }运行结果：
三、Python 程序实现
# -*- coding: utf-8 -*- """ Description: 归并排序算法 Author: shujuxiong Version: 1.0 Date: 2018-06-27 """ import copy ##合并两个有序数列 def mergeArr(left, right): r, l = 0, 0 result = [] while l<len(left) and r<len(right): if left[l] < right[r]: result.append(left[l]) l += 1 else: result.append(right[r]) r += 1 result += left[l:] result += right[r:] return result def mergeSort(relist): if len(relist) <= 1: return relist mid = len(relist)//2 left = mergeSort(relist[:mid]) right = mergeSort(relist[mid:]) return mergeArr(left, right) ##测序用例 def main(): mylist = [3,1,7,5,2,4,9,6] print(mergeSort(copy.copy(mylist))) if __name__=='__main__': main()运行结果：
转载于:https://www.cnblogs.com/shujuxiong/p/9232090.html
相关资源：数据结构—成绩单生成器