冒泡排序:基于比较的排序算法,与相邻的元素不断的比较,依次找出最大的那个数,依次向后排

特点

比较简单,很容易实现,效率低,在比较,交换值的开销非常大

以递增排序为例


C语言实现

Leetcode上917.排序数组中测试超时(效率低

MPsort_1

该实现是返回已排序的原数组

int* sortArray(int* nums, int numsSize, int* returnSize)
{
    *returnSize = numsSize;
    size_t max = numsSize - 1;
    while (max)
    {
        size_t j = 1;
        while(j <= max)
        {
            if (nums[0] < nums[j])
            {
                nums[0] = nums[0] ^ nums[j];
                nums[j] = nums[0] ^ nums[j];
                nums[0] = nums[0] ^ nums[j];
            }
            j++;
        }
        nums[0] = nums[0] ^ nums[--j];
        nums[j] = nums[0] ^ nums[j];
        nums[0] = nums[0] ^ nums[j];
        max--;
    }

    return nums;
}

C++实现

Leetcode上917.排序数组中测试通过(效率低
MPsort_2

vector<int> sortArray(vector<int>& nums)
{
    size_t max = nums.size() - 1;
    while (max)
    {
        size_t j = 1;
        while (j <= max)
        {
            if (nums[0] < nums[j])
            {
                swap(nums[0], nums[j]);
            }
            j++;
        }
        swap(nums[0], nums[j - 1]);
        max--;
    }

    return nums;
}
Last modification:April 15th, 2020 at 09:11 am