歸并排序的實(shí)現(xiàn)思路
? ? ? ?核心思想是分治法嘁扼，將一個(gè)大的集合分成單個(gè)的元素拷肌，之后對相鄰的單個(gè)元素進(jìn)行排序，然后逐步合并简逮；分的階段：可以理解為是使用遞歸的方式拆分序列的過程球散；治的階段：就是把兩個(gè)有序子序列合并成一個(gè)有序序列的過程，因?yàn)樾枰褂眠f歸散庶，所以需要有一個(gè)取值范圍即定義最大值和最小值蕉堰，創(chuàng)建一個(gè)臨時(shí)數(shù)值，定義左邊的子序列的第一個(gè)數(shù)為i悲龟，右邊的子序列第一個(gè)數(shù)為j屋讶，判斷兩個(gè)數(shù)的大小，小的添加到臨時(shí)數(shù)組中
歸并排序的代碼實(shí)現(xiàn)
static void MergeSort(int[] array, int min, int max)
? ? ? ? {
? ? ? ? ? ? if (min < max)
? ? ? ? ? ? {
? ? ? ? ? ? ? ? int mid = (min + max) / 2;
? ? ? ? ? ? ? ? //對左邊進(jìn)行歸并排序
? ? ? ? ? ? ? ? MergeSort(array, min, mid);
? ? ? ? ? ? ? ? //對右邊進(jìn)行歸并排序
? ? ? ? ? ? ? ? MergeSort(array, mid + 1, max);
? ? ? ? ? ? ? ? //合并
? ? ? ? ? ? ? ? Merge(array, min, mid, max);
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? static void Merge(int[] array, int min, int mid, int max)//合并函數(shù)
? ? ? ? {
? ? ? ? ? ? //創(chuàng)建一個(gè)臨時(shí)數(shù)組
? ? ? ? ? ? int[] temp = new int[array.Length];
? ? ? ? ? ? //創(chuàng)建左邊的開頭i和右邊的開頭j
? ? ? ? ? ? int i = min;
? ? ? ? ? ? int j = mid + 1;
? ? ? ? ? ? int k = 0;//臨時(shí)數(shù)組的下標(biāo)
? ? ? ? ? ? while (i <= mid && j < max)
? ? ? ? ? ? {
? ? ? ? ? ? ? ? if (array[i] < array[j])
? ? ? ? ? ? ? ? {
? ? ? ? ? ? ? ? ? ? temp[k++] = array[i++];
? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? else
? ? ? ? ? ? ? ? {
? ? ? ? ? ? ? ? ? ? temp[k++] = array[j++];
? ? ? ? ? ? ? ? }
? ? ? ? ? ? }
? ? ? ? ? ? //左邊有剩余
? ? ? ? ? ? while (i <= mid)
? ? ? ? ? ? {
? ? ? ? ? ? ? ? temp[k++] = array[i++];
? ? ? ? ? ? }
? ? ? ? ? ? //右邊有剩余
? ? ? ? ? ? while (j <= max)
? ? ? ? ? ? {
? ? ? ? ? ? ? ? temp[k++] = array[j++];
? ? ? ? ? ? }
? ? ? ? ? ? k = 0;
? ? ? ? ? ? while (min <= max)
? ? ? ? ? ? {
? ? ? ? ? ? ? ? array[min++] = temp[k++];
? ? ? ? ? ? }
? ? ? ? }
