程式師世界 >> 編程語言 >> C語言 >> 關於C語言 >> C#兩路歸並排序

C#兩路歸並排序

編輯：關於C語言

/// <summary>
　/// 對目標數組進行歸並排序
　/// 與QuickSort的分治比較，感受遞歸
　/// </summary>
　/// <param name="dest">目標數組</param>
　/// <param name="tempDest">暫存數組</param>
　/// <param name="left">當前部分左位置 </param>
　/// <param name="right">當前部分右位置 </param>
　/// <param name="swapTimes">當前部分中間位置 </param>
　public static void TwoWayMergeSort(int[] dest, int[] tempDest, int left, int right, ref int swapTimes)
　{
　if(left < right)
　{
　　int mid = (left + right) / 2;
　　//分割通過遞歸實現
　　TwoWayMergeSort(dest, tempDest, left, mid, ref swapTimes);//左一半
　　TwoWayMergeSort(dest, tempDest, mid + 1, right, ref swapTimes);// 右一半
　　Merge(dest, tempDest, left, right, mid, ref swapTimes);//對左右各半進行歸並
　}
　}

　/// <summary>
　/// 對當前部分進行歸並
　/// </summary>
　/// <param name="dest"></param>
　/// <param name="tempDest"></param>
　/// <param name="left"></param>
　/// <param name="right"></param>
　/// <param name="mid"></param>
　/// <param name="swapTimes">逆置位置 </param>
　private static void Merge(int[] dest, int[] tempDest, int left, int right, int mid, ref int swapTimes)
　{
　for(int i = left; i <= right; i ++)
　　tempDest = dest;
　int index1 = left;
　int index2 = mid + 1;
　int index = left;//用left很重要，如若是0則會對dest的位置重復賦值
　//|-------|--------|
　// ^index1 ^index2,體現了歸並的妙
　while(index1 <= mid && index2 <= right)
　{
　　if(tempDest[index1] <= tempDest[index2])
　　{
　　dest[index ++] = tempDest[index1 ++];
　　}
　　else
　　{
　　dest[index ++] = tempDest[index2 ++];
　　swapTimes ++;
　　}
　}
　while(index2 <= right)
　{
　　dest[index ++] = tempDest[index2 ++];
　}
　while(index1 <= mid)
　{
　　dest[index ++] = tempDest[index1 ++];
　}
　}