排序

排序算法 #

快速排序 #

1、快速排序的基本过程？ #

  1. 用分治的思想。
  2. 选一个基准元素。把比这个元素小的放左边，大的放右边。这时候基准元素所处的即为最终的位置。
  3. 递归对左右两边都采取一样的方法，直到没有元素或只有一个元素。
void quickSort(vector<int>& nums, intleft, intright) {
    if (left >= right) {
        return;
    }
    int index = partition(nums, left, right);
    quickSort(nums, left, index - 1);
    quickSort(nums, index + 1, right);
}
void quickSort(vector<int>& nums) {
    quickSort(nums, 0, nums.size() - 1);
}

2、分割的过程是什么样的？ #

  1. 假设 pivot 作为基准元素。
  2. 从数组的右端向左扫描找到第一个小于它的元素。
  3. 再从数组的左端向右扫描直到找到第一个大于它的元素。
  4. 交换这两个元素。

不断进行这个过程，就可以保证左指针 i 的左侧元素都不大于切分元素，右指针 j 的右侧元素都不小于切分元素。当两个指针相遇时，把基准元素和相遇的这个位置交换。

int partition(vector<int>& nums, intleft, intright) {
    int pivotIndex = left;
    int pivot = nums[left];
    while (left < right) {
        while (left < right && nums[right] >= pivot) {
            right--;
        }
        while (left < right && nums[left] <= pivot) {
            left++;
        }
        if (left >= right) {
            break;
        }
        swap(nums, left, right);
    }
    swap(nums, pivotIndex, left);
    return left;
}

3、快排的复杂度是多少？ #

  • 平均复杂度：O(NlgN)
  • 最坏复杂度：O(N方)
    • 即每次分割时，O(N)，要分割N次
  • 好处：不需要辅助空间，原地排序。

4、有改进的方法吗？ #

  1. 切换到插入排序
  2. 三数取中
  3. 三向切分

5、怎么找出数组第 K 个元素 #

partition() 方法，会返回一个整数 j 使得 a[l..j-1] 小于等于 a[j]，且 a[j+1..h] 大于等于 a[j]，此时 a[j] 就是数组的第 j 大元素。可以利用这个特性找出数组的第 k 个元素。

int selectK(vector<int>& nums, int k) {

    int left = 0, right = nums.size() - 1;
    while (left <= right) {
        int index = partition(nums, left, right);
        if (k == index) {
            return nums[k];
        } elseif (k < index) {
            right = index - 1;
        }
        elseif (k > index) {
            left = index + 1;
        }
    }
    return nums[k];
}

冒泡排序 #

1. 基本算法 #

从左到右不断交换相邻逆序的元素，在一轮的循环之后，可以让未排序的最大元素上浮到右侧。

void bubbleSort(vector<int>& nums) {
    int n = nums.size();
    bool isSorted = false;
    for (int i = 0; i < n && !isSorted; i++) {
        isSorted = true;
        for (int j = 0; j < n - i -1; j++) {
            if (nums[j] > nums[j + 1]) {
                isSorted = false;
                swap(nums, j, j + 1);
            }
        }
    }
}

2. 算法改进 #

在一轮循环中，如果没有发生交换，那么说明数组已经是有序的，此时可以直接退出。

3. 性能分析 #

平均和最坏都是 O(n^2)

稳定排序。

O(n2) #

  1. 冒泡排序

  2. 选择排序 - 不稳！

    1. 两层for循环每次选最小

  3. 插入排序

O(n*log2n) #

  1. 快排

  2. 堆排 - 不稳！

  3. 归并排序

    1. 第一步：创建一个额外大集合用于存储归并结果，长度则为那两个小集合的和，
    2. 第二步：我们从左自右比较两个指针指向的值，将较小的那个存入大集合中，存入之后指针移动，并继续比较，直到某一小集合的元素全部都存到大集合中
      1. 第三步：当某一小集合元素全部放入大集合中，则需将另一小集合中剩余的所有元素存到大集合中。

  4. 希尔排序 - 不稳！

    1. 希尔增量分组，组内排序

计数排序：O(n+m) - O(n+m)

桶排序：O(n) - O(m)

基数排序：O(k*n)