专栏首页Jed的技术阶梯[图解] 快速排序

[图解] 快速排序

1. 经典快速排序图示过程

(1) 经典快速排序的总体流程

(2) 根据基准值分区的过程

[算法题] 荷兰国旗问题中有详细的介绍。

2. 随机快速排序

经典快速排序总是指定数组或者某部分的最后一个元素作为基准值,随机快速排序指定数组或者某一部分中的随机值作为基准值。

3. 动图展示

quickSort.gif

4. 随机快速排序Java代码实现

/**
 * 快速排序,使得整数数组 arr 有序
 */
public static void quickSort(int[] arr) {
    if (arr == null || arr.length < 2) {
        return;
    }
    quickSort(arr, 0, arr.length - 1);
}

/**
 * 快速排序,使得整数数组 arr 的 [L, R] 部分有序
 */
public static void quickSort(int[] arr, int L, int R) {
    if(L < R) {
        // 把数组中随机的一个元素与最后一个元素交换,这样以最后一个元素作为基准值实际上就是以数组中随机的一个元素作为基准值
        swap(arr, new Random().nextInt(R - L + 1) + L, R);
        int[] p = partition(arr, L, R);
        quickSort(arr, L, p[0] - 1);
        quickSort(arr, p[1] + 1, R);
    }
}

/**
 * 分区的过程,整数数组 arr 的[L, R]部分上,使得:
 *   大于 arr[R] 的元素位于[L, R]部分的右边,但这部分数据不一定有序
 *   小于 arr[R] 的元素位于[L, R]部分的左边,但这部分数据不一定有序
 *   等于 arr[R] 的元素位于[L, R]部分的中间
 * 返回等于部分的第一个元素的下标和最后一个下标组成的整数数组
 */
public static int[] partition(int[] arr, int L, int R) {

    int basic = arr[R];
    int less = L - 1;
    int more = R + 1;
    while(L < more) {
        if(arr[L] < basic) {
            swap(arr, ++less, L++);
        } else if (arr[L] > basic) {
            swap(arr, --more, L);
        } else {
            L++;
        }
    }

    return new int[] { less + 1, more - 1 };

}

/*
 * 交换数组 arr 中下标为 i 和下标为 j 位置的元素
 */
public static void swap(int[] arr, int i, int j) {
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

5. 复杂度

  • 时间复杂度:O(nlogn)
  • 空间复杂度:快速排序使用递归,递归使用栈,因此它的空间复杂度为O(logn)
  • 稳定性:快速排序无法保证相等的元素的相对位置不变,因此它是不稳定的排序算法

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • [图解] 堆排序

    大根堆与数组的关系:计算机中是没有堆或者树这种概念的,堆或者树需要使用基本的数据结构来实现,用数组表示一个大根堆的规律如下:

    CoderJed
  • [算法题] 荷兰国旗问题

    假设这样的条纹有多条,且各种颜色的数量不一,并且随机组成了一个新的图形,新的图形可能如下图所示,但是绝非只有这一种情况:

    CoderJed
  • 图解归并排序

    CoderJed
  • Sort Algorithm排序算法

    第一次迭代,寻找0到6个下标的数字哪个是最小的,找到最小的就和第一个交换,也就是2。第一次遍历所有

    西红柿炒鸡蛋
  • 常用算法比较,js实现

    <!DOCTYPE html> <html> <head> <meta charset="utf-8"> <title></title> <style>...

    前朝楚水
  • JavaScript数组排序总结

    将数组中的相邻两个元素进行比较,将比较大(较小)的数通过两两比较移动到数组末尾(开始),执行一遍内层循环,确定一个最大(最小)的数,外层循环从数组末尾(开始)遍...

    用户4831957
  • 选择排序

    选择排序的思想,每次从剩余元素中最小的元素与当前元素交换,第一次从arr[0]arr[n-1]中选取最小值,与arr[0]交换;第二次从arr[1]arr[n-...

    桑鱼
  • php关于数组n个随机数分成x组,使每组值相近的算法

    主要原理是,将数组从大到小排序,数组1先取数取第一个,数组2第2取第2个,以此类推

    仙士可
  • 快速排序

    用户6404053
  • [PHP] 算法-把数组排成最小的数的PHP实现

    陶士涵

扫码关注云+社区

领取腾讯云代金券