归并排序C++实现

    #include<iostream>  
    #include<functional>  
    #include<memory>  
    #include<array>  
      
      
    using namespace std;  
      
    const int CNT = 10;  
      
    void merge_sort(array<int, CNT>&, int);  
      
      
    int main()  
    {  
        array<int, CNT> arr = { 1, 5, 2, 4, 3, 7, 9, 8, 6, 0};  
      
        merge_sort(arr, CNT);  
        for (int i = 0; i < 10; i++)  
            cout << arr[i] << endl;  
      
      
        cin.get();  
        return 0;  
    }  
      
      
    void merge_sort(array<int, CNT>& arr, int cont)  
    {  
        function<void(array<int, CNT>&, int, int, int)> Merge = [&](array<int, CNT>& arr_, int first, int mid, int last)  
        {  
            if (first >= last) //除非第一个和最后一个重合的时候才停止，因为只有两个的时候也需要排序  
            {  
                return;  
            }  
      
      
            Merge(arr_, first, (mid+first) / 2, mid); //递归使左半部分有序  
            Merge(arr_, mid + 1, (mid + 1 + last) / 2, last); //递归使右半部分有序  
      
            //必须把下面的代码放在下面，为了使最后能够处理原先整数组  
            unique_ptr<int[]> temp(new int[last + 1]); //这里的last是实际下标，所以要加1  
            int f = first; //要把first保存一下，最后合并到原数组中时使用  
            int t = mid + 1;  
            int k = 0;  
      
      
      
      
            //直到有一部分全部比较完 注意：要包括最后一个元素  
            while (first <= mid && t <= last)  
            {  
                if (arr[first] < arr[t])  
                {  
                    temp[k++] = arr[first++];  
                }  
                else  
                {  
                    temp[k++] = arr[t++];  
                }  
            }  
      
            //把剩余部分的东西处理完成  
            while (t <= last)  
            {  
                temp[k++] = arr[t++];  
            }  
      
            while (first <= mid)  
            {  
                temp[k++] = arr[first++];  
            }  
      
            //把比较完成的两部分合起来放在原数组中  
            for (int i = 0; i < k; i++)  
            {  
                arr[f + i] = temp[i];  
            }  
        };  
      
        Merge(arr, 0, cont / 2, cont - 1); //中间用cont和cont-1都可，作用只是把最初的数组分为两个  
    }  

标签： 代码

版权申明：本站文章部分自网络，如有侵权，请联系：west999com@outlook.com
特别注意：本站所有转载文章言论不代表本站观点！
本站所提供的图片等素材，版权归原作者所有，如需使用，请与原作者联系。