排序算法之“歸并算法”介紹

在說這個題目之前先來說說一個排序算法 “歸并算法”

歸并算法采取思想是分治思想，分治思想簡單說就是分而治之，將一個大問題分解為小問題，將小問題解答后合并為大問題的答案。乍一看跟遞歸思想很像，確實如此，分治思想一般就是使用遞歸來實現(xiàn)的。但是需要注意的是：遞歸是代碼實現(xiàn)的方式，分治屬于理論。接下來看一副圖理解下：

說完它的思想：我們再來分析下時間復(fù)雜度。歸并算法采用的是完全二叉樹的形式。所以可以由完全二叉樹的深度可以得知，整個歸并排序需要進(jìn)行l(wèi)og2n次。

然后每一次需要消耗O{n}時間。所以總的時間復(fù)雜度為o{nlog2n}。歸并排序是一種比較占用內(nèi)存，但是效率高且穩(wěn)定的算法

貼上代碼：

static void Main(string[] args)
        {
            int[] arr = new int[] { 14,12,15,13,11,16 ,10};
 
            int[] newArr = Sort(arr, new int[7], 0, arr.Length - 1);
            for (int i = 0; i < newArr.Length - 1; i++)
            {
                Console.WriteLine(newArr[i]);
            }
 
            Console.ReadKey();
        }
 
        public static int[] Sort(int[] arr, int[] result, int start, int end)
        {
            if (start >= end)
                return null;
            int len = end - start, mid = (len >> 1) + start;
            int start1 = start, end1 = mid;
            int start2 = mid + 1, end2 = end;
            Sort(arr, result, start1, end1);
            Sort(arr, result, start2, end2);
            int k = start;
            //進(jìn)行比較。注意這里++是后執(zhí)行的，先取出來數(shù)組中的值然后++
            while (start1 <= end1 && start2 <= end2)
                result[k++] = arr[start1] < arr[start2] ? arr[start1++] : arr[start2++];
            //將每個分組剩余的進(jìn)行復(fù)制
            while (start1 <= end1) 
                result[k++] = arr[start1++];
            //將每個分組剩余的進(jìn)行復(fù)制
            while (start2 <= end2)
                result[k++] = arr[start2++]; 
            for (k = start; k <= end; k++)
                arr[k] = result[k];
            return result;
        }

說完了歸并算法回到題目上來 首先分析下 題目給定的是兩個已經(jīng)排好序的數(shù)組合并，關(guān)鍵字“合并”，“兩個”，正好符合我們的歸并算法，并且已經(jīng)分類好了，只需要去合并就可以了。

來看下幾張圖。

藍(lán)色的箭頭表示最終選擇的位置，而紅色的箭頭表示兩個數(shù)組當(dāng)前要比較的元素，比如當(dāng)前是2與1比較，1比2小，所以1放到藍(lán)色的箭頭中，藍(lán)色的箭頭后移，1的箭頭后移。

然后2與4比較，2比4小那么2到藍(lán)色的箭頭中，藍(lán)色箭頭后移，2后移，繼續(xù)比較.......

歸并思路就是這樣了，最后唯一需要注意的是那個先比較完的話，那么剩下的直接不需要比較，把后面的直接移上去就可以了，這個需要提前判定一下。

貼上代碼：

static void Main(string[] args)
        {
            int[] arr1 = new int[] { 2, 3, 6, 8 };
            int[] arr2 = new int[] { 1, 4, 5, 7 };
            int[] newArr = Sort(arr1, arr2);
            for (int i = 0; i < newArr.Length - 1; i++)
            {
                Console.WriteLine(newArr[i]);
            }
 
            Console.ReadKey();
        }
 
        public static int[] Sort(int[] arr1,int[] arr2)
        {
            int[] newArr = new int[arr1.Length + arr2.Length];
            int i = 0, j = 0, k = 0;
            while (i < arr1.Length && j < arr2.Length)
            {
                if (arr1[i] < arr2[j])
                {
                   
                    newArr[k] = arr1[i];
                    i++;
                    k++;
                }
                else
                {
                    
                    newArr[k] = arr2[j];
                    j++;
                    k++;
                }
            }
 
            while (i < arr1.Length)
                newArr[k++] = arr1[i++];
            while (j < arr2.Length)
                newArr[j++] = arr2[j++];
            return newArr;
        }
    }