归并排序算法实现归并排序算法|数据结构

本文概述

复杂
例
算法
C程序
Java程序
C＃程序

合并排序是遵循分而治之的算法。考虑一个n个元素的数组A。该算法分3个步骤处理元素。

如果A包含0或1个元素, 则它已经被排序, 否则, 将A分为元素数量相等的两个子数组。
征服意味着使用合并排序对两个子数组进行递归排序。
合并子数组以形成单个最终排序的数组, 以保持数组的顺序。

合并排序的主要思想是, 简短列表的排序时间更少。
复杂

复杂	最好的情况	平均情况	最差的情况
时间复杂度	O（n log n）	O（n log n）	O（n log n）
Space Complexity			O(n)

例考虑以下由7个元素组成的数组。使用合并排序对数组进行排序。

A = {10, 5, 2, 23, 45, 21, 7}

算法

步骤1：[INITIALIZE] SET I = BEG, J = MID + 1, INDEX = 0
步骤2：如果ARR [I] < ARR [J] SET TEMP [INDEX] = ARR [I] SET I = I + 1 ELSE SET TEMP [INDEX], 则重复（I < = MID）和（J < = END） = ARR [J] SET J = J + 1 [IF结束] SET INDEX = INDEX + 1 [LOOP结束]步骤3：[复制右侧子阵列的其余元素（如果有）] IF I> MID J < =结束SET TEMP [INDEX] = ARR [J] SET INDEX = INDEX + 1, SET J = J +1 [END OF LOOP] [复制左子数组的剩余元素, 如果有的话] ELSE < = MID SET TEMP [INDEX] = ARR [I] SET INDEX = INDEX + 1, SET I = I + 1 [LOOP结束] [IF结束]
步骤4：[将TEMP的内容复制回ARR] SET K = 0
步骤5：在K < INDEX SET ARR [K] = TEMP [K] SET K = K + 1 [LOOP LOOP]时重复
步骤6：退出

MERGE_SORT（ARR, BEG, END）

步骤1：如果BEG < END SET MID =（BEG + END）/ 2呼叫MERGE_SORT（ARR, BEG, MID）呼叫MERGE_SORT（ARR, MID + 1, END）合并（ARR, BEG, MID, END）[END OF如果]
步骤2：结束

C程序

#include< stdio.h> void mergeSort(int[], int, int); void merge(int[], int, int, int); void main () { int a[10]= {10, 9, 7, 101, 23, 44, 12, 78, 34, 23}; int i; mergeSort(a, 0, 9); printf("printing the sorted elements"); for(i=0; i< 10; i++) { printf("\n%d\n", a[i]); } } void mergeSort(int a[], int beg, int end) { int mid; if(beg< end) { mid = (beg+end)/2; mergeSort(a, beg, mid); mergeSort(a, mid+1, end); merge(a, beg, mid, end); } } void merge(int a[], int beg, int mid, int end) { int i=beg, j=mid+1, k, index = beg; int temp[10]; while(i< =mid & & j< =end) { if(a[i]< a[j]) { temp[index] = a[i]; i = i+1; } else { temp[index] = a[j]; j = j+1; } index++; } if(i> mid) { while(j< =end) { temp[index] = a[j]; index++; j++; } } else { while(i< =mid) { temp[index] = a[i]; index++; i++; } } k = beg; while(k< index) { a[k]=temp[k]; k++; } }

输出：

printing the sorted elements 7 9 10 12 23 23 34 44 78 101

Java程序

public class MyMergeSort { void merge(int arr[], int beg, int mid, int end) {int l = mid - beg + 1; int r = end - mid; intLeftArray[] = new int [l]; intRightArray[] = new int [r]; for (int i=0; i< l; ++i) LeftArray[i] = arr[beg + i]; for (int j=0; j< r; ++j) RightArray[j] = arr[mid + 1+ j]; int i = 0, j = 0; int k = beg; while (i< l& & j< r) { if (LeftArray[i] < = RightArray[j]) { arr[k] = LeftArray[i]; i++; } else { arr[k] = RightArray[j]; j++; } k++; } while (i< l) { arr[k] = LeftArray[i]; i++; k++; }while (j< r) { arr[k] = RightArray[j]; j++; k++; } }void sort(int arr[], int beg, int end) { if (beg< end) { int mid = (beg+end)/2; sort(arr, beg, mid); sort(arr , mid+1, end); merge(arr, beg, mid, end); } } public static void main(String args[]) { intarr[] = {90, 23, 101, 45, 65, 23, 67, 89, 34, 23}; MyMergeSort ob = new MyMergeSort(); ob.sort(arr, 0, arr.length-1); System.out.println("\nSorted array"); for(int i =0; i< arr.length; i++) { System.out.println(arr[i]+""); } } }

输出：

Sorted array 23 23 23 34 45 65 67 89 90 101

C＃程序

using System; public class MyMergeSort { void merge(int[] arr, int beg, int mid, int end) {int l = mid - beg + 1; int r = end - mid; int i, j; int[] LeftArray = new int [l]; int[] RightArray = new int [r]; for (i=0; i< l; ++i) LeftArray[i] = arr[beg + i]; for (j=0; j< r; ++j) RightArray[j] = arr[mid + 1+ j]; i = 0; j = 0; int k = beg; while (i < l & & j < r) { if (LeftArray[i] < = RightArray[j]) { arr[k] = LeftArray[i]; i++; } else { arr[k] = RightArray[j]; j++; } k++; } while (i < l) { arr[k] = LeftArray[i]; i++; k++; }while (j < r) { arr[k] = RightArray[j]; j++; k++; } }void sort(int[] arr, int beg, int end) { if (beg < end) { int mid = (beg+end)/2; sort(arr, beg, mid); sort(arr , mid+1, end); merge(arr, beg, mid, end); } } public static void Main() { int[] arr = {90, 23, 101, 45, 65, 23, 67, 89, 34, 23}; MyMergeSort ob = new MyMergeSort(); ob.sort(arr, 0, 9); Console.WriteLine("\nSorted array"); for(int i =0; i< 10; i++) { Console.WriteLine(arr[i]+""); } } }

【归并排序算法实现】输出：