您好,登錄后才能下訂單哦!
歸并排序——如何使用golang和python實現(xiàn)?針對這個問題,這篇文章詳細介紹了相對應(yīng)的分析和解答,希望可以幫助更多想解決這個問題的小伙伴找到更簡單易行的方法。
歸并排序
思路:將數(shù)組不斷二分,然后合并為有序數(shù)組
C++實現(xiàn):
void mergeSort(T arr[], int left,int right) { //對arr[left,right]的范圍進行排序 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] 兩部分進行歸并 T *tmp=new T[right-left+1]; for (int i = left; i <= right; i++) tmp[i - left] = arr[i]; //先把arr(需要合并的左右片段) 復(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實現(xiàn):
func mergeSort(arr []int, left, right int) { if left >= right { return } mid := left + (right-left)/2 mergeSort(arr, left, mid) // 遞歸調(diào)用,分別對左右部分進行歸并排序 mergeSort(arr, mid+1, right) merge(arr, left, mid, right) // 將左右部分進行合并 } func merge(arr []int, left, mid, right int) { // 將要合并的部分做個拷貝 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實現(xiàn):
python 的實現(xiàn)方法和上面不一樣,上面兩種方法都是在原始數(shù)組上直接進行修改的
def mergeSort(arr): if len(arr) <= 1: return arr mid = len(arr) // 2 left = mergeSort(arr[:mid]) # 分別對左右部分排序 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個元素 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)
關(guān)于歸并排序——如何使用golang和python實現(xiàn)問題的解答就分享到這里了,希望以上內(nèi)容可以對大家有一定的幫助,如果你還有很多疑惑沒有解開,可以關(guān)注億速云行業(yè)資訊頻道了解更多相關(guān)知識。
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點不代表本網(wǎng)站立場,如果涉及侵權(quán)請聯(lián)系站長郵箱:is@yisu.com進行舉報,并提供相關(guān)證據(jù),一經(jīng)查實,將立刻刪除涉嫌侵權(quán)內(nèi)容。