算法排序算法之归并排序

拼搏现实的明天。 2022-06-15 12:56 305阅读 0赞

# 归并排序 #

归并排序主要是二路归并排序

## 基本思想 ##

*  设数组a中存放了n个数据元素
 *  初始时把它们看成n个长度为1的有序子数组，然后从第一个子数组开始，把相邻子数组两两合并，得到n/2的整数上界个长度为2的新的有序子数组（当n为奇数时最后一个新的有序子数组的长度为1）
 *  对这些新的有序子数组再两两合并，直到最后长度为n的有序数组位置

## 排序过程 ##

![这里写图片描述][SouthEast]

以数组\{50,10,90,30,70,40,80,60,20\}为例

![这里写图片描述][20160427172905073]

## 代码实现 ##

void Merge(DataType a[], int n, DataType swap[], int k) {
            /*k为有序子数组的长度，一次二路归并排序后的有序子序列放在数组swap中*/
            int m = 0, u1, l2, i, j, u2;
    
            /*第一个有序子数组下界为0*/
            int l1 = 0;
            while (l1 + k <= n - 1) {
                l2 = l1 + k;//计算第二个有序子数组下界
                u1 = l2 - 1;//计算第一个有序子数组上界
                u2 = (l2 + k - 1 <= n - 1) ? l2 + k - 1 : n - 1;//计算第二个有序子数组上界
    
                /*两个有序子数组合并*/
                for (i = l1, j = l2; i <= u1 && j <= u2; m++) {
                    if (a[i] <= a[j]) {
                        swap[m] = a[i];
                        i++;
                    } else {
                        swap[m] = a[j];
                        j++;
                    }
                }
    
                /*子数组2已归并完，将数组1中剩余的元素放到数组swap中*/
                while (i <= u1) {
                    swap[m] = a[i];
                    m++;
                    i++;
                }
    
                 /*子数组1已归并完，将数组2中剩余的元素放到数组swap中*/
                while (j <= u2) {
                    swap[m] = a[j];
                    m++;
                    j++;
                }
                l1 = u2 + 1;
            }
            /*将原始数组中只够一组的元素顺序放到数组swap中*/
            for (i = l1; i < n; i++, m++) {
                swap[m] = a[i];
            }
        }

void MergeSort(DataType a[], int n) {
            int i, k = 1;//归并长度从1开始
            DataType * swap;
    
            swap = (DataType *) malloc(sizeof(DataType) * n);
    
            while (k < n) {
                Merge(a, n, swap, k);
                for (i = 0; i < n; i++) {
                    a[i] = swap[i];
                }
                k = 2 * k;
            }
            free(swap);
        }

java实现

public static void mergeSort(int[] arr) {
            mergeSort(arr, 0, arr.length - 1);
        }
    
    
        private static void mergeSort(int[] arr, int low, int high) {
            int mid = (low + high) / 2;
            if (low < high) {
                //左边
                mergeSort(arr, low, mid);
                //右边
                mergeSort(arr, mid + 1, high);
                //左右归并
                merge(arr, low, mid, high);
            }
        }
    
        private static void merge(int[] arr, int low, int mid, int high) {
            int[] temp = new int[high - low + 1];
            int left = low;//左指针
            int right = mid + 1;//右指针
            int k = 0;
            //把较小的数先移动到新数组中
            while (left <= mid && right <= high) {
                if (arr[left] < arr[right]) {
                    temp[k++] = arr[left++];
                } else {
                    temp[k++] = arr[right++];
                }
            }
            //把左边剩余的数移入数组
            while (left <= mid) {
                temp[k++] = arr[left++];
            }
    
            //把右边剩余的数移入数组
            while (right <= high) {
                temp[k++] = arr[right++];
            }
    
            //把新数组中的数覆盖nums数组
            for (int k2 = 0; k2 < temp.length; k2++) {
                arr[k2 + low] = temp[k2];
            }
        }

## 算法分析 ##

*  时间复杂度  
    
    
     *  一次二路归并排序归并的次数log2n 每次比较次数n-1 故时间复杂度是O(nlog2n)
 *  空间复杂度  
    
    
     *  使用了n个临时内存单元存放数据 空间复杂度O(n)
 *  稳定性  
    
    
     *  归并排序是一种**比较占内存**，但却**效率高且稳定**的算法

--------------------

[SouthEast]: /images/20220615/5c69520134154589ae68f282c143a0f8.png
[20160427172905073]: /images/20220615/f7584ad36a5a4fbfa62491dd9770667e.png