归并排序:使用分而治之的思想,将待排序数组不断均分,直到拆分为单个元素,然后进行排序,在与相邻的拆分的元素合并直到合并完成,即排序完成

特点

一般来将,需要大量内存来存放拆分的元素,对于以拆分的有序数组的合并排序在Leetcode上88. 合并两个有序数组,最主要的过程是合并排序的过程。通过递归来实现该算法比较简单

在本例中的Demo是修改后的归并排序(对内存消耗少),但大体的思想是一致的,将原数组看作是已拆分的,滑动窗口,双指针,每次取2的倍数个元素进行合并排序,不足的取剩下的元素个数,或者跳出

以递增排序为例


C语言实现

Leetcode上917.排序数组中测试通过(效率还行
GBsort_1

该实现会修改原数组,并且是返回有序的原数组

int* sortArray(int* nums, int numsSize, int* returnSize)
{
    *returnSize = numsSize;
    //基本逻辑
    //2-4-8-16-32-64...依次分割数组,
    for (size_t i = 1; i < numsSize; i *= 2)
    {
        //滑动指针
        for (size_t j = 0; j < numsSize; j += (2 * i))
        {
            //排序
            if (j + i >= numsSize)
            {
                break;
            }
            
            int* p1 = &nums[j];
            int* p2 = &nums[j + i];
            //size_t p1Size = i + i;
            size_t p2Size = i;
            if (j + i + i >= numsSize && j + i <= numsSize)
            {
                p2Size = numsSize - j - i;
            }
            
            //合并两个有序数组并排序
            int* _p1 = (int*)calloc(i, 4);
            memcpy(_p1, p1, i*4);

            size_t _i = 0, _j = 0;
            while (true)
            {
                if (_p1[_i] < p2[_j])
                {
                    p1[_i + _j] = _p1[_i];
                    _i++;
                    if (_i >= i)
                    {
                        while (_j < p2Size)
                        {
                            p1[_i + _j] = p2[_j];
                            _j++;
                        }
                        free(_p1);
                        break;
                    }
                }
                else
                {
                    p1[_i + _j] = p2[_j];
                    _j++;
                    if (_j >= p2Size)
                    {
                        while (_i < i)
                        {
                            p1[_i + _j] = _p1[_i];
                            _i++;
                        }
                        free(_p1);
                        break;
                    }
                }
            }
            
        }    
    }
    
    return nums;
}

C++实现

Leetcode上917.排序数组中测试通过(效率还行
GBsort_2

注意:该实现依旧会修改原数组,并且是返回有序的原数组

vector<int> sortArray(vector<int>& nums)
{
    for (size_t i = 1; i < nums.size(); i *= 2)
    {
        //滑动指针
        for (size_t j = 0; j < nums.size(); j += (2 * i))
        {
            //排序
            if (j + i >= nums.size())
            {
                break;
            }
            
            int* p1 = &nums[j];
            int* p2 = &nums[j + i];
    
            size_t p2Size = i;
            if (j + i + i >= nums.size() && j + i <= nums.size())
            {
                p2Size = nums.size() - j - i;
            }
            
            //合并两个有序数组并排序
            int* _p1 = new int[i];
            memcpy(_p1, p1, i*4);

            size_t _i = 0, _j = 0;
            while (true)
            {
                if (_p1[_i] < p2[_j])
                {
                    p1[_i + _j] = _p1[_i];
                    _i++;
                    if (_i >= i)
                    {
                        while (_j < p2Size)
                        {
                            p1[_i + _j] = p2[_j];
                            _j++;
                        }
                        delete[] _p1;
                        break;
                    }
                }
                else
                {
                    p1[_i + _j] = p2[_j];
                    _j++;
                    if (_j >= p2Size)
                    {
                        while (_i < i)
                        {
                            p1[_i + _j] = _p1[_i];
                            _i++;
                        }
                        delete[] _p1;
                        break;
                    }
                }
            }
            
        }    
    }
    
    return nums;
}
Last modification:April 15th, 2020 at 09:12 am