首页 > 代码库 > 归并排序实现

归并排序实现

public void Merge(int[] a, int start, int mid, int end)
        {
            int[] tmp = new int[end - start + 1];    // tmp是汇总2个有序区的临时区域
            int i = start;            // 第1个有序区的索引
            int j = mid + 1;        // 第2个有序区的索引
            int k = 0;                // 临时区域的索引

            while (i <= mid && j <= end)
            {
                if (a[i] <= a[j])
                {
                    tmp[k++] = a[i++];
                }
                else
                {
                    tmp[k++] = a[j++];
                }
            }

            while (i <= mid)
            {
                tmp[k++] = a[i++];
            }

            while (j <= end)
            {
                tmp[k++] = a[j++];
            }

            // 将排序后的元素,全部都整合到数组a中。
            for (i = 0; i < k; i++)
            {
                a[start + i] = tmp[i];
            }

            tmp = null;
        }

        public void MergeSort(int[] a, int start, int end)
        {
            if (a == null || start >= end)
                return;

            int mid = (end + start) / 2;
            MergeSort(a, start, mid); // 递归排序a[start...mid]
            MergeSort(a, mid + 1, end); // 递归排序a[mid+1...end]

            // a[start...mid] 和 a[mid...end]是两个有序空间,
            // 将它们排序成一个有序空间a[start...end]
            Merge(a, start, mid, end);
        }

归并排序(合并排序)的实现。使用分治法用递归来实现排序。

归并排序实现