百木园-与人分享,
就是让自己快乐。

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

一. 归并排序算法简介

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

二. 算法复杂度 

最理想情况: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,...直到大于原数组长度)开始归并,直到归并排序完成,效率很高,另外只申请了和原数组等长的临时空间用于存储中间归并结果,空间开销小。


来源:https://www.cnblogs.com/seaman9/p/16041206.html
本站部分图文来源于网络,如有侵权请联系删除。

未经允许不得转载:百木园 » go实用编程-算法篇 -归并排序

相关推荐

  • 暂无文章