MENU

快速排序模板

January 24, 2021 • Read: 102 • 学习·笔记

变量命名及背景

  • 数组为 q
  • 数组 q 左下标为 l
  • 数组 q 右下标为 r
  • i,j 分别为数组 q 的左右两个指针,向中间移动

模板默写思路

  • 递归返回条件:当只有一个元素:即 l==r,什么都不做直接 return。用 l>=r 也可以,个人习惯问题,此处用 l>=r
  • 找到分界值 x ,一般可取的值为:q[l],q[(l+r)/2],q[r],便于解决边界值和方便记忆,x=q[l]
  • 初始化 i,j的值,便于解决边界值问题,i=l--,j=r++,定义为数组第一个和最后一个左边的两侧
  • i 和 j 向中间走,直到相遇为止,因此,第一个循环限制条件是 while(i<j){...}
  • 在第一个while循环的每一次遍历里面,i不断向中间靠近,每走一步,如果元素q[i]小于临界值x则可以继续走,直到不满足这个条件为止。于是可以简写为:while(q[++i]<x)。j同理,只不过从右边往中间,所以简写为:while(q[--j]>x)
  • 当i和j都停下来,则检查是否相交,不相交(i<j)就交换 q[i] 和 q[j];

    • 注:这时候如果i和j都停下来,但是不满足 i<j 表示相交了,什么都不要做,因为接下来就是退出循环,进行快排左边和快排右边。也就是此时肯定是相交,同时不满足第一个循环的条件while(i<j){...},退出循环
  • 递归执行排序左边和右边

模板

public class QuickSort785 {

    public static void main(String[] args) {
        int[] arr = new int[]{3, 5, 3, 9, 8};
        int num = arr.length;
        quickSort(arr, 0, num - 1);
        for (int value : arr) {
            System.out.print(value + " ");
        }
    }

    private static void quickSort(int[] q, int l, int r) {
        if (l >= r) {
            return;
        }
        // 第1步,找x,设定i和j,注意定义i,j为两侧
        int x = q[l], i = l - 1, j = r + 1;
        while (i < j) { // 每一次循环,代表i与j暂停,交换后!i和j继续左走和右走
            // 第2步,以x为标准分隔,走左右两边
            while(q[++i] < x){}
            while(q[--j] > x){}
            // 第3步,两个指针还没有相遇,交换,没有交换,(如果i与j相遇了,就不能交换了,交换就出问题!)
            if (i < j) {
                swap(q,i,j);
            }else {
                // 这里代表相遇,相遇则不会有下个循环,本次结束
            }
        }
        // 第4步,递归排左和右
        quickSort(q, l, j);
        quickSort(q, j + 1, r);
    }
    public static void swap(int[] q, int a, int b) {
        int t = q[a];
        q[a] = q[b];
        q[b] = t;
    }
}

本文由 ONE 创作,采用 知识共享署名4.0 国际许可协议进行许可
本站文章除注明转载/出处外,均为本站原创或翻译,转载前请务必署名
如有版权疑问交流,请给我留言:oneisall8955@gmail.com
本文永久链接:https://liuzhicong.cn/index.php/study/alg-quick-sort_template_acwing785.html

Archives QR Code Tip
QR Code for this page
Tipping QR Code