聊聊C#歸并排序算法
作者：大姚
歸并排序是一種高效穩(wěn)定的排序算法，時(shí)間復(fù)雜度為O(nlogn)。它的核心思想是將待排序序列分割成更小的子序列，然后逐步合并并排序這些子序列，最終得到一個(gè)有序序列。
前言
歸并排序是一種常見(jiàn)的排序算法，它采用分治法的思想，在排序過(guò)程中不斷將待排序序列分割成更小的子序列，直到每個(gè)子序列中只剩下一個(gè)元素，然后將這些子序列兩兩合并排序，最終得到一個(gè)有序的序列。
歸并排序?qū)崿F(xiàn)原理
- 將待排序序列分割成兩個(gè)子序列，直到每個(gè)子序列中只有一個(gè)元素。
- 將相鄰的兩個(gè)子序列合并，并按照大小順序合并為一個(gè)新的有序序列。
- 不斷重復(fù)第2步，直到所有子序列都合并為一個(gè)有序序列。
歸并排序代碼實(shí)現(xiàn)
public static void MergeSort(int[] arr, int left, int right)
{
if (left < right)
{
// 計(jì)算中間索引
int mid = (left + right) / 2;
// 對(duì)左半部分?jǐn)?shù)組進(jìn)行歸并排序
MergeSort(arr, left, mid);
// 對(duì)右半部分?jǐn)?shù)組進(jìn)行歸并排序
MergeSort(arr, mid + 1, right);
// 合并兩個(gè)有序數(shù)組
Merge(arr, left, mid, right);
}
}
public static void Merge(int[] arr, int left, int mid, int right)
{
int n1 = mid - left + 1; // 左半部分?jǐn)?shù)組的長(zhǎng)度
int n2 = right - mid; // 右半部分?jǐn)?shù)組的長(zhǎng)度
// 創(chuàng)建臨時(shí)數(shù)組
int[] leftArr = new int[n1];
int[] rightArr = new int[n2];
// 將數(shù)據(jù)拷貝到臨時(shí)數(shù)組
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];
}
// 合并兩個(gè)有序數(shù)組
int k = left; // 初始化合并后的數(shù)組索引
int p = 0; // 初始化左半部分?jǐn)?shù)組的索引
int q = 0; // 初始化右半部分?jǐn)?shù)組的索引
while (p < n1 && q < n2)
{
if (leftArr[p] <= rightArr[q])
{
arr[k] = leftArr[p];
p++;
}
else
{
arr[k] = rightArr[q];
q++;
}
k++;
}
// 復(fù)制左半部分?jǐn)?shù)組的剩余元素
while (p < n1)
{
arr[k] = leftArr[p];
p++;
k++;
}
// 復(fù)制右半部分?jǐn)?shù)組的剩余元素
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("排序前數(shù)組：" + string.Join(", ", array));
MergeSort(array, 0, array.Length - 1);
Console.WriteLine("排序后數(shù)組：" + string.Join(", ", array));
}運(yùn)行結(jié)果
圖片
總結(jié)
歸并排序是一種高效穩(wěn)定的排序算法，時(shí)間復(fù)雜度為O(nlogn)。它的核心思想是將待排序序列分割成更小的子序列，然后逐步合并并排序這些子序列，最終得到一個(gè)有序序列。歸并排序需要額外的空間來(lái)存儲(chǔ)臨時(shí)數(shù)組，但由于其分治的特性，適用于對(duì)鏈表和外部存儲(chǔ)的排序。
責(zé)任編輯：武曉燕
來(lái)源：
追逐時(shí)光者
