快捷導(dǎo)航

golang/python實(shí)現(xiàn)歸并排序?qū)嵗a

更新時(shí)間：2020年08月30日 10:24:43 作者：NothingLeft了

這篇文章主要給大家介紹了關(guān)于golang/python實(shí)現(xiàn)歸并排序的相關(guān)資料，文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧

歸并排序

思路：將數(shù)組不斷二分，然后合并為有序數(shù)組

C++實(shí)現(xiàn):

void mergeSort(T arr[], int left,int right) { //對(duì)arr[left,right]的范圍進(jìn)行排序
 if (left >= right)
  return;
 int mid = (left + right) / 2;
 mergeSort(arr, left, mid);
 mergeSort(arr, mid + 1, right); 
 merge(arr, left, mid, right); //合并兩部分
}

template<typename T>
void __merge(T arr[], int left, int mid, int right) { //將arr[left,mid] 和 arr[mid+1,right] 兩部分進(jìn)行歸并

 T *tmp=new T[right-left+1];
 for (int i = left; i <= right; i++)
  tmp[i - left] = arr[i]; //先把a(bǔ)rr（需要合并的左右片段） 復(fù)制給tmp

 int i = left, j = mid + 1; // i 做為左半部分的指針 j作為右半部分的指針
 for (int k = left; k <= right; k++) {
  if (i > mid) { // 左半部分 已經(jīng)合入完了，將右半部分剩下的 全部合入
   arr[k] = tmp[j - left];
   j++;
  }
  else if (j > right) { // 右半部分 已經(jīng)合入完了，將左半部分剩下的 全部合入
   arr[k] = tmp[i - left];
   i++;
  }
  else if (tmp[i - left] < tmp[j - left]) {
   arr[k] = tmp[i - left];
   i++;
  }
  else {
   arr[k] = tmp[j - left];
   j++;
  }
 }
 delete[] tmp;
}

GoLang實(shí)現(xiàn):

func mergeSort(arr []int, left, right int) {
 if left >= right {
  return
 }
 mid := left + (right-left)/2
 mergeSort(arr, left, mid) // 遞歸調(diào)用，分別對(duì)左右部分進(jìn)行歸并排序
 mergeSort(arr, mid+1, right)
 merge(arr, left, mid, right) // 將左右部分進(jìn)行合并
}

func merge(arr []int, left, mid, right int) {
 // 將要合并的部分做個(gè)拷貝
 var tmp []int = make([]int, right-left+1)
 for i, j := left, 0; i <= right; i++ {
  tmp[j] = arr[i]
  j++
 }
 // i做為左半部分的指針 j作為右半部分的指針
 var i, j int = left, mid+1
 for k := left; k <= right; k++ {
  if i > mid { // 左半部分 已經(jīng)合入完了，將右半部分剩下的 全部合入
   arr[k] = tmp[j-left]
   j++
  } else if j > right { // 右半部分 已經(jīng)合入完了，將左半部分剩下的 全部合入
   arr[k] = tmp[i-left]
   i++
  } else if tmp[i-left] > tmp[j-left] {
   arr[k] = tmp[j-left]
   j++
  } else {
   arr[k] = tmp[i-left]
   i++
  }
 }
}

python實(shí)現(xiàn):

python 的實(shí)現(xiàn)方法和上面不一樣，上面兩種方法都是在原始數(shù)組上直接進(jìn)行修改的

def mergeSort(arr):
 if len(arr) <= 1:
  return arr
 mid = len(arr) // 2
 left = mergeSort(arr[:mid]) # 分別對(duì)左右部分排序
 right = mergeSort(arr[mid:])
 return merge(left, right) # 合并左右部分為有序數(shù)組


def merge(left, right):
 result = []
 num_left, num_right = left.pop(0), right.pop(0) # 分別取出左右部分的第0個(gè)元素
 while True:
  if num_left < num_right:
   result.append(num_left)
   try:
    num_left = left.pop(0)
   except IndexError:
    result.append(num_right)
    result.extend(right)
    break
  else:
   result.append(num_right)
   try:
    num_right = right.pop(0)
   except IndexError:
    result.append(num_left)
    result.extend(left)
    break
 return result


if __name__ == '__main__':
 from random import shuffle

 arr = list(range(30))
 shuffle(arr)
 arr = mergeSort(arr)
 print(arr)

總結(jié)

到此這篇關(guān)于golang/python實(shí)現(xiàn)歸并排序的文章就介紹到這了,更多相關(guān)golang python歸并排序內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: