欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

c#代码实现排序算法之归并排序

程序员文章站 2022-03-24 13:53:22
...

归并排序的平均时间复杂度为O(nlogn),最好时间复杂度为O(nlogn),最坏时间复杂度为O(nlogn),空间复杂度为O(n),是一种稳定的算法。

1.将待排序序列r(1),r(2),…,r(n)划分为两个长度相等的子序列r(1),…r(n/2)和r(n/2+1),…,r(n)。
2.求解子问题:分别对这两个子序列进行排序,得到两个有序子序列
3.合并:将这两个有序子序列合并成一个有序序列

归并排序采用分治法

public static void merger(int[] list, int low, int mid, int high)
        {
            int[] L = new int[mid - low + 2];
            int[] R = new int[high - mid + 1];
            L[mid - low + 1] = int.MaxValue;
            R[high - mid] = int.MaxValue;

            for (int i = 0; i < mid - low + 1; i++)
            {
                L[i] = list[low + i];
            }

            for (int i = 0; i < high - mid; i++)
            {
                R[i] = list[mid + 1 + i];
            }

            int j = 0;
            int k = 0;
            for (int i = 0; i < high - low + 1; i++)
            {
                if (L[j] <= R[k])
                {
                    list[low + i] = L[j];
                    j++;
                }
                else
                {
                    list[low + i] = R[k];
                    k++;
                }
            }
        }
        public static void cutSortArray(int[] list, int low, int high)
        {
            if (low < high)
            {
                int mid = (low + high) / 2;
                cutSortArray(list, low, mid);
                cutSortArray(list, mid + 1, high);
                merger(list, low, mid, high);
            }
        }