排序

排序算法 #

快速排序 #

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)