leetcode 数组排序

leetcode: 排序数组

排序算法包括基础的选择排序、插入排序、交换排序；也包括快速排序，堆排序，归并排序等。其中快速排序是交换排序的升级版；堆排序是选择排序的升级版。那插入排序有没有升级版呢，也是有的，是希尔排序，但是希尔排序的思想不好理解，所以本文中不涉及希尔排序。

选择排序，插入排序，交换排序属于基础排序算法，时间复杂度是O(n * n)。快速排序和堆排序的时间复杂度是 O(nlogn)。O(logn) 这种时间复杂度跟类二分法的思想关联是很紧密的，也就是说对数据集进行处理的时候每一次都是将上一次的数据集划分成两份，然后分别对这两份做计算，快速排序和堆排序否符合这样的规律。

讨论排序算法的时候，还常常要考虑算法的稳定性。比如有一个数据序列是 {5, 10, 100, 90, 80， 100}，其中第 3 个数和第 6 个数都是 100，排序之后的序列是 {5, 10, 80, 90, 100, 100}，如果排序之后的两个 100，没有改变原来的先后顺序，也就是原来第三个位置的 100 排序后成为了第 5 个位置的 100，原来第 6 个位置的 100 保持位置不变，这样就是稳定的；否则，不是稳定的。

1 选择排序

如下是选择排序的代码，典型的两层循环，时间复杂度是 O(n * n)。选择排序、插入排序、交换排序，都是两层循环，区别在于循环中的处理逻辑。 选择排序是选择一个最小的或者选择一个最大的数，然后将这个最值放到一定的位置。

class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
      int n = nums.size();
      for (int i = 0; i < n - 1; i++) {
        int min_index = i;
        for (int j = i + 1; j < n; j++) {
          if (nums[j] < nums[min_index]) {
            min_index = j;
          }
        }
        int tmp = nums[i];
        nums[i] = nums[min_index];
        nums[min_index] = tmp;
      }
      return nums;
    }
};

选择排序是不稳定的，如下边的数据序列：

{100, 100, 50, 20, 10}

在第一次选择的时候，最小值是 10,10 和第 1 个位置的 100 进行交换。这样原来第一个位置的 100 和第二个位置的 100 就改变了先后顺序，所以是不稳定的。

2 交换排序

交换排序又称为冒泡排序，就像下雨的时候河面上冒起的水泡一样。从前向后两两对比，如果前者较后者大，那么就进行交换，否则不交换。算法也是两层循环，和选择排序相比，除了循环中的逻辑不一样之外，两个循环的起始索引也是不一样的。内层循环的起始索引或者结束索引受外层循环的 i 影响；外层循环的起止索引往往也不是从 0 到 n - 1，而是差一个。

class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
      int n = nums.size();
      for (int i = 1; i < n; i++) {
        for (int j = 0; j < n - i; j++) {
          int tmp1 = nums[j];
          int tmp2 = nums[j + 1];
          if (tmp1 > tmp2) {
            nums[j] = tmp2;
            nums[j + 1] = tmp1;
          } 
        }
      }
      return nums;
    }
};

冒泡排序是稳定的。如下数据序列，相邻的两个数据进行比较的时候，只有前者比后者大的时候才会交换；否则不交换。所以对于两个相等的数值，排序前后的先后顺序是保持不变的。

{100, 100, 50, 20, 10}

3 插入排序

插入排序是不是稳定的，关键看代码中注释的地方使用 <= 进行比较还是实用 < 进行比较，前者是稳定的；后者是不稳定的。如果可以稳定，也可以不稳定，那么我们优先选择稳定的算法。所以，插入排序是稳定的。

class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
      int n = nums.size();
      for (int i = 1; i < n; i++) {
        int data = nums[i];
        for (int j = 0; j < i; j++) {
            // 这里使用 <= 进行比较，则是稳定的
            // 这里使用 < 进行比较，则不是稳定的
            if (data <= nums[j]) {
                for (int k = i; k > j; k--) {
                    nums[k] = nums[k - 1];
                }
                nums[j] = data;
                break; // 找到了插入的位置，则内存循环需要 break
            }
        }
      }
      return nums;
    }
};

插入排序也可以实现成下边的代码。插入排序就是选择一个数据向已经排序好的队列中插入数据，那么具体把这个数据插入到队列的哪个位置呢，查找位置的过程可以从前向后进行查找，也可以从后向前查找。

class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
      int n = nums.size();
      for (int i = 1; i < n; i++) {
        int data = nums[i];
        int j;
        for (j = i - 1; j >= 0; j--) {
          if (nums[j] > data) {
            nums[j + 1] = nums[j];
          } else {
            break;
          }
        }
        nums[j + 1] = data;
      }
      return nums;
    }
};

插入排序是稳定的。如下的数据序列，当将一个选择数值插入到已经排好序的队列时，这个选择的数值本来在后边，如果选择插入点的时候，只要选择的值小于当前这个值，就将选择的值插入到这个位置，这样就可以保证稳定性。

{100, 100, 50, 20, 10}

选择排序、交换排序、插入排序，都有两层循环，时间复杂度均是 O(n * n)，区别在于算法的侧重点是不一样的。其实选择排序中也有交换的思想，选择一个最大值或者最小值之后，将这个最值与排好序的位置进行交换；交换排序也有选择的思想，在一遍冒泡的过程中，最终选择出来剩余数据的最大值或者最小值，这就是选择；插入排序中也有交换的思想，给选择的数据找到一个合适的位置之后，与此位置的数据进行交换。

4 快速排序

快速排序是不稳定的。如下的数据序列，首先选择第一个数 100，然后进行比较。右半段的数值比 100 小的时候进行交换，那么从右向左遍历到 1 的时候，就要交换，那么 1 会换到最左边。那么此时第 2 个位置的 1 就在第 8 个位置的 1 的后边了，所以是不稳定的。

{100, 1, 2, 10, 50, 100, 100, 1, 100, 200, 300, 500}

class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
      QuickSort(nums, 0, nums.size() - 1);
      return nums;
    }
    
    // 快速排序是递归算法
    void QuickSort(vector<int>& nums, int start, int end) {
      // 递归退出条件
      // start >= end 的时候，不需要进行排序了
      if (start >= end) {
        return;
      }

      // 选择 start 位置的数，作为比较和交换的对象
      int select_data = nums[start];
      int select_index = start;

      int start_tmp = start;
      int end_tmp = end;
      // 给选的数找到一个合适的位置，需要通过 1 次或多次循环才能找到合适的位置
      while(start_tmp < end_tmp) {
        // 从小到大排序，并且选择的是最左边的数值，那么先从右边来遍历
        // 如果数值比选择的数值大，那么停止遍历循环遍历
        // 如果数值不比选择的数值大，那么
        while (start_tmp < end_tmp && nums[end_tmp] > select_data) {
            end_tmp--;
        }
        // end_tmp 处的数值 <= 选择的数值，所以把这个数放到左边
        if (start_tmp < end_tmp) {
            nums[start_tmp] = nums[end_tmp];
            start_tmp++;
        }

        while (start_tmp < end_tmp && nums[start_tmp] < select_data) {
            start_tmp++;
        }
        if (start_tmp < end_tmp) {
            nums[end_tmp] = nums[start_tmp];
            end_tmp--;
        }
      }
      // 遍历完毕，start_tmp < end_tmp 不成立了
      // 项一个极端的情况就是，以此循环就没有执行
      // 那么还是把选择的数值放到 start_tmp 位置就可以了
      nums[start_tmp] = select_data;
      
      // 这次选择的数据的位置已经确定了
      // 所以下次递归计算的时候，这个位置不再参与计算了
      // 所以左区间的右边界是 start_tmp - 1
      // 右区间的左边界是 start_tmp + 1
      QuickSort(nums, start, start_tmp - 1);
      QuickSort(nums, start_tmp + 1, end);
      return;
    }
};

5 堆排序

堆排序是不稳定的。

堆排序算法-CSDN博客

6 归并排序

归并排序参考如下博客的第 2 节 链表排序。

链表算法题总结-CSDN博客