草庐IT

go实用编程-算法篇 -归并排序

seaman9 2023-03-28 原文

一. 归并排序算法简介

归并排序算法是一种采用了分治策略的排序算法。它通过递归地先使每个子序列有序，再将两个有序的序列进行合并成一个有序的序列（也可以采用非递归的方式实现，效率更高一些）。归并算法是稳定和高效的排序算法（适用于复杂对象（结构体）数列的稳定排序）

二. 算法复杂度 

最理想情况：O(nlogn)
最坏情况：   O(nlogn)

三. 算法分治思路

  • 将数组切片为相同长度的两部分，长度为LEN的数组，分解为：两个子数组，一个是 nums[0...LEN/2] 另一个是 nums[LEN/2+1...LEN]
  • 递归的对两个部分进行相同的切片操作，直到数组长度为1
  • 对已经排好序的两个切片进行合并操作
四. 算法原理示意图

 

 五. 算法实现

5.1 递归实现

package main
import (
    "fmt"
)

func mergeSort1(array []int) []int {
    arrLen := len(array);
    if arrLen < 2 {
        return array;
    }
    i := arrLen >>1;
    leftSub  := mergeSort1(array[0:i]);
    rightSub := mergeSort1(array[i:]);
    result :=  merge1(leftSub, rightSub);
    return result;
}

func merge1(left []int, right []int) []int {
    m := len(left);
    n := len(right);
    result := make([]int, m+n, m+n);
    i, j, k := 0, 0, 0;
    for i < m && j < n {
        if left[i] <= right[j] {
            result[k] = left[i];
            k++;
            i++;
        } else {
            result[k] = right[j];
            k++;
            j++;
        }
    }
    if i == m {
        for j < n {
            result[k] = right[j];
            k++;
            j++;
        }
    } 
    if j == n {
        for i < m {
            result[k] = left[i];
            k++;
            i++; 
        }
    }   
    
    return result;
}
 
5.2 非递归实现
//merge sort using no recursion
/****
    // i: the begin index of old sub-array, j: the begin index of even sub-array

                  |<- k ->|  |<- k ->|     //case: k = 4
        array [0,1,2,3] [4,5,6,7][8,9]
                  ^            ^                   ^
                  i             j                    arrLen
****/

//merge sort using no recursion
func mergeSort2(array []int){
    arrLen := len(array);
    if arrLen <= 0 {
        return;
    }

    list := make([]int, arrLen, arrLen);
    source := &array;
    target := &list;
    flag := 0;

    // k is the arrLength of sub-array,k=1,2,4,...
    for k:= 1; k < arrLen; k <<=1 {
        if flag == 1{
            source = &list;
            target = &array;
        } else {
            source = &array;
            target = &list;
        }   
        flag = 1 - flag;
        //i, j is the begin index of sub-array 
        i, j := 0, k;
        for n:= 0 ; n < arrLen; {
            p, q:= i, j;        
            pEnd := i + k;
            if pEnd > arrLen {
                pEnd = arrLen;
            }   
            qEnd := j + k;
            if qEnd > arrLen {
                qEnd = arrLen;
            }
            for (p < pEnd) && (q < qEnd) {
                if (*source)[p] <= (*source)[q] {
                    (*target)[n] = (*source)[p];
                    n++; 
                    p++;
                } else {
                    (*target)[n] = (*source)[q];
                    n++;
                    q++;
                }
            }
            //copy the left data of sub_array indexed by q
            if p >= pEnd {
                for q < qEnd {
                    (*target)[n] = (*source)[q];
                    n++;
                    q++;
                }
            }
            //copy the left data of sub_array indexed by p
            if q >= qEnd {
                for p < pEnd {
                    (*target)[n] = (*source)[p];
                    n++;
                    p++;       
                }
            }

            i += k << 1;
            j += k << 1;
        }
    }
    if flag == 1 {
        for r:=0; r < arrLen; r++ {
            array[r] = list[r];           
        }
    } 
}

func main() {
    arr := []int{9,4, 6, 8, 6, 30, 28, 2, 3, 50};
    fmt.Println(arr);

    sortArr := mergeSort1(arr);
    fmt.Println(sortArr);

    mergeSort2(arr);
    fmt.Println(arr);
    
}
 
说明，递归算法容易理解，因为涉及到嵌套递归和临时空间开销，效率不高，在项目实践中不建议使用；非递归算法，采用自下向上从最小长度为1的子数组（子数组长度分别为：1,2,4,8，...直到大于原数组长度）开始归并，直到归并排序完成，效率很高，另外只申请了和原数组等长的临时空间用于存储中间归并结果，空间开销小。
实用编程nbspdivarrayGo

有关go实用编程-算法篇 -归并排序的更多相关文章

  1. ruby - 在 Ruby 中编写命令行实用程序 - 2

    我想用ruby​​编写一个小的命令行实用程序并将其作为gem分发。我知道安装后，Guard、Sass和Thor等某些gem可以从命令行自行运行。为了让gem像二进制文件一样可用，我需要在我的gemspec中指定什么。 最佳答案 Gem::Specification.newdo|s|...s.executable='name_of_executable'...endhttp://docs.rubygems.org/read/chapter/20 关于ruby-在Ruby中编写命令行实用程序

  2. ruby - 寻找通过阅读代码确定编程语言的ruby gem？ - 2

    几个月前，我读了一篇关于ruby​​gem的博客文章，它可以通过阅读代码本身来确定编程语言。对于我的生活，我不记得博客或gem的名称。谷歌搜索“ruby编程语言猜测”及其变体也无济于事。有人碰巧知道相关gem的名称吗？ 最佳答案 是这个吗:http://github.com/chrislo/sourceclassifier/tree/master 关于ruby-寻找通过阅读代码确定编程语言的rubygem？，我们在StackOverflow上找到一个类似的问题：

  3. 区块链之加解密算法&数字证书 - 2

    目录一.加解密算法数字签名对称加密DES(DataEncryptionStandard)3DES(TripleDES)AES(AdvancedEncryptionStandard)RSA加密法DSA(DigitalSignatureAlgorithm)ECC(EllipticCurvesCryptography)非对称加密签名与加密过程非对称加密的应用对称加密与非对称加密的结合二.数字证书图解一.加解密算法加密简单而言就是通过一种算法将明文信息转换成密文信息，信息的的接收方能够通过密钥对密文信息进行解密获得明文信息的过程。根据加解密的密钥是否相同，算法可以分为对称加密、非对称加密、对称加密和非

  4. 网络编程套接字 - 2

    网络编程套接字网络编程基础知识理解源`IP`地址和目的`IP`地址理解源MAC地址和目的MAC地址认识端口号理解端口号和进程ID理解源端口号和目的端口号认识`TCP`协议认识`UDP`协议网络字节序socket编程接口`sockaddr``UDP`网络程序服务器端代码逻辑：需要用到的接口服务器端代码`udp`客户端代码逻辑`udp`客户端代码`TCP`网络程序服务器代码逻辑多个版本服务器单进程版本多进程版本多线程版本线程池版本服务器端代码客户端代码逻辑客户端代码TCP协议通讯流程TCP协议的客户端/服务器程序流程三次握手（建立连接）数据传输四次挥手（断开连接）TCP和UDP对比网络编程基础知识

  5. ruby - 我正在学习编程并选择了 Ruby。我应该升级到 Ruby 1.9 吗？ - 2

    我完全不是程序员，正在学习使用Ruby和Rails框架进行编程。我目前正在使用Ruby1.8.7和Rails3.0.3，但我想知道我是否应该升级到Ruby1.9，因为我真的没有任何升级的“遗留”成本。缺点是什么？我是否会遇到与普通gem的兼容性问题，或者甚至其他我不太了解甚至无法预料的问题？ 最佳答案 你应该升级。不要坚持从1.8.7开始。如果您发现不支持1.9.2的gem，请避免使用它们(因为它们很可能不被维护)。如果您对gem是否兼容1.9.2有任何疑问，您可以在以下位置查看:http://www.railsplugins.or

  6. ruby-on-rails - 需要帮助最大化多个相似对象中的 3 个因素并适当排序 - 2

    我需要用任何语言编写一个算法，根据3个因素对数组进行排序。我以度假村为例(如Hipmunk)。假设我想去度假。我想要最便宜的地方、最好的评论和最多的景点。但是，显然我找不到在所有3个中都排名第一的方法。Example(assumingthereare20importantattractions):ResortA:$150/night...98/100infavorablereviews...18of20attractionsResortB:$99/night...85/100infavorablereviews...12of20attractionsResortC:$120/night

  7. ruby-on-rails - 在具有 ActiveRecord 条件的相关模型中按字段排序 - 2

    我正在尝试按Rails相关模型中的字段进行排序。我研究的所有解决方案都没有解决如果相关模型被另一个参数过滤？元素模型classItem相关模型:classPriority我正在使用where子句检索项目:@items=Item.where('company_id=?andapproved=?',@company.id,true).all我需要按相关表格中的“位置”列进行排序。问题在于，在优先级模型中，一个项目可能会被多家公司列出。因此，这些职位取决于他们拥有的company_id。当我显示项目时，它是针对一个公司的，按公司内的职位排序。完成此任务的正确方法是什么？感谢您的帮助。PS-我

  8. ruby - 如何以编程方式删除实例上的 "singleton information"以使其编码(marshal)？ - 2

    我创建了一个由于“在运行时执行的单例元类定义”而无法编码的对象(这段代码的描述是否正确？)。这是通过以下代码执行的:#defineclassXthatmyusesingletonclassmetaprogrammingfeatures#throughcallofmethod:break_marshalling!classXdefbreak_marshalling!meta_class=class我该怎么做才能使对象编码正确？是否可以从对象instance_of_x的classX中“移除”单例组件？我真的需要一个建议，因为我们的一些对象需要通过Marshal.dump序列化机制进行缓存。

  9. Ruby 元编程问题 - 2

    我正在查看Ruby日志记录库Logging.logger方法并从sourceatgithub提出问题与这段代码有关:logger=::Logging::Logger.new(name)logger.add_appendersappenderlogger.additive=falseclass我知道类 最佳答案 这实际上删除了方法(当它实际被执行时)。这是确保close不会被调用两次的保障措施。看起来好像有嵌套的“class 关于Ruby元编程问题，我们在StackOverflow上找到一

  10. ruby - 按数字(从大到大)然后按字母(字母顺序)对对象集合进行排序 - 2

    我正在构建一个小部件来显示奥运会的奖牌数。我有一个“国家”对象的集合，其中每个对象都有一个“名称”属性，以及奖牌计数的“金”、“银”、“铜”。列表应该排序:1.首先是奖牌总数2.如果奖牌相同，按类型分割(金>银>铜，即2金>1金+1银)3.如果奖牌和类型相同，则按字母顺序子排序我正在用ruby​​做这件事，但我想语言并不重要。我确实找到了一个解决方案，但如果感觉必须有更优雅的方法来实现它。这是我做的:使用加权奖牌总数创建一个虚拟属性。因此，如果他们有2个金牌和1个银牌，加权总数将为“3.020100”。1金1银1铜为“3.010101”由于我们希望将奖牌数排序为最高的，因此列表按降序排

随机推荐