Leetcode - 排序

  1. 排序算法总结
    1. 算法分类
    2. 冒泡排序
    3. 选择排序
    4. 插入排序
    5. 快速排序
    6. 归并排序
    7. Some Problems of Leetcode
      1. 区间

leetcode 算法题解法

排序部分

题目连接

排序算法总结

算法分类

算法总结

冒泡排序

  • 稳定
  • 对相邻的元素进行两两比较,顺序相反则进行交换,这样,每一趟会将最小或最大的元素“浮”到顶端,最终达到完全有序。就好像一串气泡一样,最终从小到大或从大到小依次排下来。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    vector<int> bubble(vector<int> nums) {
    // 第一层循环从最后一个数字开始
    // 每经历一次最外层循环,i位上的数确定下来
    for (int i = nums.size()-1; i > 0; --i) {
    // 用于从0开始依次冒泡,将较大的数往后推
    for (int j = 0; j < i; ++j){
    if (nums[j] > nums[j+1]) {
    int temp = nums[j+1];
    nums[j+1] = nums[j];
    nums[j] = temp;
    }
    }
    }
    return nums;
    }

选择排序

  • 不稳定
  • 每一次从待排序的数据元素中选出最小(或最大)的一个元素,存放在序列的起始位置,直到全部待排序的数据元素排完。
  • 比如序列[5, 5, 3]第一次就将第一个[5]与[3]交换,导致第一个5挪动到第二个5后面
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    vector<int> choose(vector<int> nums) {
    // 第一层循环从第一个数字开始
    // 每经历一次最外层循环,i位上的数确定下来
    for (int i = 0; i < nums.size()-1; ++i) {
    // 依次将nums[i]和后面的数进行比较,将最小的数放到i位
    for (int j = i+1; j < nums.size(); ++j){
    if (nums[j] < nums[i]) {
    int temp = nums[i];
    nums[i] = nums[j];
    nums[j] = temp;
    }
    }
    }
    return nums;
    }

插入排序

  • 稳定
  • 把一个新的元素插入已排好序的数组形成一个新的已排好序的数组 从第一个元素开始,取下一个元素比较后实现排序,形成新的数组, 再取第三个元素与该数组比较, 比较时从该数组的最后一位开始比较, 若新元素比与其比较的元素小,则将该比较的元素后移以为, 直到新元素比该数组左边找到其应该插入的位置。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    vector<int> insert(vector<int> nums) {
    // 插入排序默认从第二个数开始
    for (int i = 1; i < nums.size(); ++i) {
    // 记录下这个值
    int temp = nums[i];
    // 开始值前一个位置
    int j = i-1;
    while (j >= 0) {
    // 找到被排序数的位置
    if (temp >= nums[j]) {
    break;
    }
    // 被排序位置比nums[j]小,将nums[j]往后移动,继续和前面的比较
    nums[j+1] = nums[j];
    j--;
    }
    nums[j+1] = temp;
    }
    return nums;
    }

快速排序

  • 思路详情请见连接
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    class Solution {
    public:
    vector<int> quickSort(vector<int>& nums) {
    quick(nums, 0, nums.size()-1);
    return nums;
    }

    private:
    void quick(vector<int>& nums, int originLeft, int originRight) {
    if (originLeft > originRight) {
    return;
    }

    int left = originLeft, right = originRight, baseValue = nums[originLeft];

    while (left < right) {
    // 移动右边
    while (left < right && nums[right] >= baseValue) {
    right--;
    }
    // 移动左边
    while (left < right && nums[left] <= baseValue) {
    left++;
    }

    if (left < right) {
    int temp = nums[left];
    nums[left] = nums[right];
    nums[right] = temp;
    }
    }

    // 调换base
    nums[originLeft] = nums[left];
    nums[left] = baseValue;

    // 递归
    quick(nums, originLeft, left-1);
    quick(nums, left+1, originRight);
    }
    };

归并排序

  • 归并排序具体工作原理如下(假设序列共有n个元素):

    • 将序列中每相邻的两个数字进行归并操作(merge), 形成 floor(n/2)个序列排序之后每个序列包含两个元素
    • 将上述序列在此进行归并,形成 floor(n/4)个序列,每个序列包含四个元素
    • 重复步骤二,知道所有的元素排序完毕
  • 归并排序是稳定的排序算法,时间复杂度为O(nlogn),如果是使用链表实现的话,空间复杂度可以达到O(1)

  • 但是如果是使用数组来存储的话,在归并的过程中,需要临时的空间来储存归并好的数据,所以空间复杂度为O(n)

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    class Solution {
    public:
    bool mergeSort(vector<int>& nums) {
    int base = 1, size = nums.size();

    while (base < size) {
    for (int i = 0; i < size; i = i + base*2) {
    merge(nums, i, i+base, i + base*2);
    }
    base = base * 2;
    }
    }

    private:
    // for example
    // startIndex = 0
    // middleIndex = 4
    // endIndex = 8
    void merge(vector<int>& nums, int startIndex, int middleIndex, int endIndex) {

    int size = nums.size();
    if (middleIndex >= size) {
    middleIndex = size;
    endIndex = size;
    } else if (endIndex >= size) {
    endIndex = size;
    }

    int i = startIndex, j = middleIndex;
    vector<int> temp;

    while (i < middleIndex && j < endIndex) {
    if (nums[j] < nums[i]) {
    temp.push_back(nums[j]);
    j++;
    } else {
    temp.push_back(nums[i]);
    i++;
    }
    }

    if (i == middleIndex) {
    while (j < endIndex) {
    temp.push_back(nums[j]);
    j++;
    }
    } else {
    while (i < middleIndex) {
    temp.push_back(nums[i]);
    i++;
    }
    }

    for (int i = 0; i < temp.size(); ++i) {
    nums[startIndex+i] = temp[i];
    }
    }
    };

Some Problems of Leetcode

区间

  • 开始刷leetcode的排序相关的题目,首先遇到两题就是有关于区间合并的问题

  • 第一题就是给你若干个区间,他们中可以合并的进行合并

  • 第二题是给若干个排序了的区间,和一个单独的区间,将其合并

  • 第二题可以看作是第一题的一个特例子,第二题中,将所有的区间放到数组中,然后在调用第一题的解法即可

  • 这个主要说说第一题的解法

    1
    按照区间的左边界限将区间进行排序,让后从左到右进行遍历,依次合并可以合并的即可。

欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论,也可以邮件至 qinhan_shu@163.com

文章标题:Leetcode - 排序

本文作者:QinHan

发布时间:2019-10-30, 03:24:34

最后更新:2020-02-20, 05:42:12

原始链接:https://qinhan.site/2019/10/30/leetcode-sort/

版权声明: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。

目录
×

喜欢就点赞,疼爱就打赏