C#中自顶向下的归并排序是一种常见的排序算法,它通过将待排序的数组递归地分割成较小的子数组,然后将这些子数组进行合并,最终得到一个有序的数组。
具体实现如下:
using System;
class MergeSort
{
// 归并排序入口函数
public static void Sort(int[] arr)
{
int[] temp = new int[arr.Length];
Sort(arr, temp, 0, arr.Length - 1);
}
// 递归地对数组进行分割和合并
private static void Sort(int[] arr, int[] temp, int left, int right)
{
if (left >= right)
return;
int mid = (left + right) / 2;
Sort(arr, temp, left, mid); // 对左半部分进行排序
Sort(arr, temp, mid + 1, right); // 对右半部分进行排序
Merge(arr, temp, left, mid, right); // 合并左右两部分
}
// 合并两个有序数组
private static void Merge(int[] arr, int[] temp, int left, int mid, int right)
{
int i = left; // 左半部分起始索引
int j = mid + 1; // 右半部分起始索引
int k = left; // 合并后数组的起始索引
// 将两个有序数组合并到临时数组中
while (i <= mid && j <= right)
{
if (arr[i] <= arr[j])
{
temp[k++] = arr[i++];
}
else
{
temp[k++] = arr[j++];
}
}
// 将剩余的元素复制到临时数组中
while (i <= mid)
{
temp[k++] = arr[i++];
}
while (j <= right)
{
temp[k++] = arr[j++];
}
// 将临时数组中的元素复制回原数组
for (int m = left; m <= right; m++)
{
arr[m] = temp[m];
}
}
}
class Program
{
static void Main(string[] args)
{
int[] arr = { 9, 5, 7, 2, 4, 1, 6, 8, 3 };
MergeSort.Sort(arr);
Console.WriteLine("排序结果:");
foreach (int num in arr)
{
Console.Write(num + " ");
}
}
}
这段代码实现了C#中自顶向下的归并排序算法。首先定义了一个MergeSort
类,其中包含了排序的入口函数Sort
、递归地对数组进行分割和合并的私有函数Sort
,以及合并两个有序数组的私有函数Merge
。在Main
函数中,我们可以看到如何使用归并排序对一个数组进行排序。
归并排序的优势在于其稳定性和可靠性,时间复杂度为O(nlogn),适用于各种规模的数据集。它常被用于对大规模数据进行排序,例如对日志数据、数据库查询结果等进行排序。
腾讯云提供了多种云计算相关产品,其中包括云服务器、云数据库、云存储等。您可以通过访问腾讯云官方网站(https://cloud.tencent.com/)了解更多关于腾讯云的产品和服务。
领取专属 10元无门槛券
手把手带您无忧上云