C#归并排序算法

举报
追逐时光者 发表于 2023/11/25 10:16:29 2023/11/25
【摘要】 前言归并排序是一种常见的排序算法,它采用分治法的思想,在排序过程中不断将待排序序列分割成更小的子序列,直到每个子序列中只剩下一个元素,然后将这些子序列两两合并排序,最终得到一个有序的序列。归并排序实现原理将待排序序列分割成两个子序列,直到每个子序列中只有一个元素。将相邻的两个子序列合并,并按照大小顺序合并为一个新的有序序列。不断重复第2步,直到所有子序列都合并为一个有序序列。归并排序代码实现...

学算法.png

前言

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

归并排序实现原理

  1. 将待排序序列分割成两个子序列,直到每个子序列中只有一个元素。
  2. 将相邻的两个子序列合并,并按照大小顺序合并为一个新的有序序列。
  3. 不断重复第2步,直到所有子序列都合并为一个有序序列。

归并排序代码实现

        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] <= rightArr[q])
                {
                    arr[k] = leftArr[p];
                    p++;
                }
                else
                {
                    arr[k] = rightArr[q];
                    q++;
                }
                k++;
            }

            // 复制左半部分数组的剩余元素
            while (p < n1)
            {
                arr[k] = leftArr[p];
                p++;
                k++;
            }

            // 复制右半部分数组的剩余元素
            while (q < n2)
            {
                arr[k] = rightArr[q];
                q++;
                k++;
            }
        }

        public static void MergeSortRun()
        {
            int[] array = { 19, 27, 46, 48, 50, 2, 4, 44, 47, 36, 38, 15, 26, 5, 3 };
            Console.WriteLine("排序前数组:" + string.Join(", ", array));

            MergeSort(array, 0, array.Length - 1);

            Console.WriteLine("排序后数组:" + string.Join(", ", array));
        }   

运行结果

总结

归并排序是一种高效稳定的排序算法,时间复杂度为O(nlogn)。它的核心思想是将待排序序列分割成更小的子序列,然后逐步合并并排序这些子序列,最终得到一个有序序列。归并排序需要额外的空间来存储临时数组,但由于其分治的特性,适用于对链表和外部存储的排序。

【版权声明】本文为华为云社区用户原创内容,转载时必须标注文章的来源(华为云社区)、文章链接、文章作者等基本信息, 否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。