归并排序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都可，作用只是把最初的数组分为两个        }
热门搜索

归并排序C++实现
