黑松山资源网 Design By www.paidiu.com
归并排序
思路:将数组不断二分,然后合并为有序数组
C++实现:
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(需要合并的左右片段) 复制给tmp int i = left, j = mid + 1; // i 做为左半部分的指针 j作为右半部分的指针 for (int k = left; k <= right; k++) { if (i > mid) { // 左半部分 已经合入完了,将右半部分剩下的 全部合入 arr[k] = tmp[j - left]; j++; } else if (j > right) { // 右半部分 已经合入完了,将左半部分剩下的 全部合入 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实现:
func mergeSort(arr []int, left, right int) { if left >= right { return } mid := left + (right-left)/2 mergeSort(arr, left, mid) // 递归调用,分别对左右部分进行归并排序 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 { // 左半部分 已经合入完了,将右半部分剩下的 全部合入 arr[k] = tmp[j-left] j++ } else if j > right { // 右半部分 已经合入完了,将左半部分剩下的 全部合入 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实现:
python 的实现方法和上面不一样,上面两种方法都是在原始数组上直接进行修改的
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) # 合并左右部分为有序数组 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)
总结
黑松山资源网 Design By www.paidiu.com
广告合作:本站广告合作请联系QQ:858582 申请时备注:广告合作(否则不回)
免责声明:本站资源来自互联网收集,仅供用于学习和交流,请遵循相关法律法规,本站一切资源不代表本站立场,如有侵权、后门、不妥请联系本站删除!
免责声明:本站资源来自互联网收集,仅供用于学习和交流,请遵循相关法律法规,本站一切资源不代表本站立场,如有侵权、后门、不妥请联系本站删除!
黑松山资源网 Design By www.paidiu.com
暂无评论...
RTX 5090要首发 性能要翻倍!三星展示GDDR7显存
三星在GTC上展示了专为下一代游戏GPU设计的GDDR7内存。
首次推出的GDDR7内存模块密度为16GB,每个模块容量为2GB。其速度预设为32 Gbps(PAM3),但也可以降至28 Gbps,以提高产量和初始阶段的整体性能和成本效益。
据三星表示,GDDR7内存的能效将提高20%,同时工作电压仅为1.1V,低于标准的1.2V。通过采用更新的封装材料和优化的电路设计,使得在高速运行时的发热量降低,GDDR7的热阻比GDDR6降低了70%。
更新日志
2024年10月05日
2024年10月05日
- 群星《前途海量 电影原声专辑》[FLAC/分轨][227.78MB]
- 张信哲.1992-知道新曲与精丫巨石】【WAV+CUE】
- 王翠玲.1995-ANGEL【新艺宝】【WAV+CUE】
- 景冈山.1996-我的眼里只有你【大地唱片】【WAV+CUE】
- 群星《八戒 电影原声带》[320K/MP3][188.97MB]
- 群星《我的阿勒泰 影视原声带》[320K/MP3][139.47MB]
- 纪钧瀚《胎教古典音乐 钢琴与大提琴的沉浸时光》[320K/MP3][148.91MB]
- 刘雅丽.2001-丽花皇后·EMI精选王【EMI百代】【FLAC分轨】
- 齐秦.1994-黄金十年1981-1990CHINA.TOUR.LIVE精丫上华】【WAV+CUE】
- 群星.2008-本色·百代音乐人创作专辑【EMI百代】【WAV+CUE】
- 群星.2001-同步过冬AVCD【环球】【WAV+CUE】
- 群星.2020-同步过冬2020冀待晴空【环球】【WAV+CUE】
- 沈雁.1986-四季(2012梦田复刻版)【白云唱片】【WAV+CUE】
- 纪钧瀚《胎教古典音乐 钢琴与大提琴的沉浸时光》[FLAC/分轨][257.88MB]
- 《国语老歌 怀旧篇 3CD》[WAV/分轨][1.6GB]