美文网首页
2_5归并排序

2_5归并排序

作者: X_Y | 来源:发表于2017-09-06 16:47 被阅读13次

    C++实现

    class MergeSort {
    public:
        void merge(int* A, int l, int mid, int r)
        {
            // start merger
            int tmp[r-l+1];
            int idx = 0;
            int idx_l = l;
            int idx_r = mid;
            while(idx_l < mid && idx_r < r+1){
                if(A[idx_l] < A[idx_r]){
                    tmp[idx++] = A[idx_l++];
                }else{
                    tmp[idx++] = A[idx_r++];
                }
            }
            
            if(idx_l==mid){
                while(idx_r < r+1){
                    tmp[idx++] = A[idx_r++];
                }
            }else{
                while(idx_l < mid){
                    tmp[idx++] = A[idx_l++];
                }
            }
            
            idx = 0;
            while(idx < r-l+1){
                A[l+idx] = tmp[idx];
                idx++;
            }
        }
        void process(int* A, int l, int r)
        {
            if(l==r){
                return;
            }
            int mid = (r+l)/2;
            process(A, l, mid);
            process(A, mid+1, r);
            merge(A, l, mid+1, r);
        }
        int* mergeSort(int* A, int n) {
            // write code here
            // if(1==n){
            //     return A;
            // }
            process(A, 0, n-1);
            return A;
        }
    };
    

    python 实现

    # -*- coding:utf-8 -*-
    
    class MergeSort:
        def mergeSort(self, A, n):
            # write code here
            if 1==n:
                return A
            else:
                mid = n / 2
                A1 = self.mergeSort(A[:mid], mid)
                A2 = self.mergeSort(A[mid:], n-mid)
                result = [0]*(n)
                for i in xrange(n):
                    if A1 and A2:
                        if A1[0] < A2[0]:
                            result[i] = A1.pop(0)
                        else:
                            result[i] = A2.pop(0)
                    elif not A1:
                        result[i] = A2.pop(0)
                    else:
                        result[i] = A1.pop(0)
                return result
    

    相关文章

      网友评论

          本文标题:2_5归并排序

          本文链接:https://www.haomeiwen.com/subject/amdvjxtx.html