排序算法 --- 快速排序

一、排序思想

  • 将数组中的一个数作为基准,比该数小的放到左边,比该数大的放到右边;
  • 对左右两边再进行上述操作,即把左边当成一个新数组,找新的基准数,右边也一样;
  • 直到不能再分割下去为止。

欢迎大家关注我的公众号 javawebkf,目前正在慢慢地将简书文章搬到公众号,以后简书和公众号文章将同步更新,且简书上的付费文章在公众号上将免费。


案例:

假如待排序列如下:

初始状态

  • 选定6为基准数,然后先从右边开始遍历,找到一个比基准数小的数,如下图:

找到比基准数小的5

  • 右边找到比基准数小的时候,右边先停下,再从左边开始遍历,找到比基准数大的,如下图:

找到比基准数大的7

  • 这个时候,左右两边都先停下,交换57的位置,结果如下:

第一次交换完成

  • 然后继续从右边开始遍历,即从7的位置开始,找到比基准数小的数,如下:

找到比基准数小的4

  • 找到后停下,再从左往右找比基准数大的,即从5开始找,结果如下:

找到比基准数大的9

  • 这个时候,左右两边都停下,交换94的位置,结果如下:

第二次交换完成

  • 再从右边开始找比基准数小的,找到了3,然后从左边找比基准数大的,左边指针移动到3的时候,左右指针重合了,如下:

指针重合

  • 指针重合了,就将基准数和指针重合时所指的数交换位置,即交换63的位置,如图:

第一躺排序完成

  • 此时6左边的都是比它小的,右边的都是比它大的。左边部分和右边部分看成是两个新的待排序列,两个序列都按照上述方式再进行排序,先排左边,再排右边

二、代码实现

结合上面的案例,以及代码中的注释,可以说是思路十分清晰了,完整代码如下:

public static void sort(int[] arr, int left, int right) {
        if (arr == null || arr.length == 1) {
            return;
        }
        if (left > right) {
            return;
        }
        int base = arr[left]; // 最左边的数当作基准数
        int i = left; // 从左往右遍历的指针
        int j = right; // 从右往左遍历的指针
        int temp = 0; // 用来保存临时变量
        // 当左右指针不相遇的时候,就进行检索
        while(i != j) {
            // 先从右往左检索,直到检索到比基准数小的
            while (arr[j] >= base && i < j) {
                j--;
            }
            // 再从左往右检索,直到检索到比基准数大的
            while (arr[i] <= base && i < j) {
                i++;
            }
            // 跳出了上面两个while循环,表示右边找到了基准数小的,左边找到了比基准数大的,交换位置
            temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
        // 跳出了最外层while循环,表示i和j相等,左右指针相遇了,交换基准数和此时指针指的元素
        arr[left] = arr[i];
        arr[i] = base;
        // 此时,第一躺排序完成,左边和右边看成新数组,重复上述步骤
        sort(arr, j+1, right); // 排右边
        sort(arr, left, i-1); // 排左边
}

快速排序之所以成为快速排序,那就是因为它快,经测试,排1千万数据大概是1秒的样子,还真是有两把刷子。

下一篇
举报

扫码关注云+社区

领取腾讯云代金券