聊聊C#归并排序算法

前言

归并排序是一种常见的排序算法，它采用分治法的思想，在排序过程中不断将待排序序列分割成更小的子序列，直到每个子序列中只剩下一个元素，然后将这些子序列两两合并排序，最终得到一个有序的序列。

归并排序实现原理

归并排序代码实现

public static void MergeSort(int[] arr, int left, int right)

        {

            if (left < right)

            {

                // 计算中间索引

                int mid = (left + right) / 2;




                // 对左半部分数组进行归并排序

                MergeSort(arr, left, mid);
                // 对右半部分数组进行归并排序

                MergeSort(arr, mid + 1, right);
                // 合并两个有序数组

                Merge(arr, left, mid, right);

            }

        }
        public static void Merge(int[] arr, int left, int mid, int right)

        {

            int n1 = mid - left + 1; // 左半部分数组的长度

            int n2 = right - mid;    // 右半部分数组的长度
            // 创建临时数组

            int[] leftArr = new int[n1];

            int[] rightArr = new int[n2];
            // 将数据拷贝到临时数组

            for (int i = 0; i < n1; ++i)

            {

                leftArr[i] = arr[left + i];

            }
            for (int j = 0; j < n2; ++j)

            {

                rightArr[j] = arr[mid + 1 + j];

            }
            // 合并两个有序数组

            int k = left;   // 初始化合并后的数组索引

            int p = 0;      // 初始化左半部分数组的索引

            int q = 0;      // 初始化右半部分数组的索引
            while (p < n1 && q < n2)

            {

                if (leftArr[p]