基本算法——快速排序

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了基本算法——快速排序，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1314字，纯文字阅读大概需要2分钟。

内容图文

目标：掌握快排和java中的快排函数

• AcWing P785 快速排序
• AcWing P786 第k个数

目录

• 1. 快排
• 2. Arrays.sort

1. 快排

快排的核心思想：

• 确定分界点，可以是q[l],q[(l+r)/2]或q[r],我们选用q[l]
  • 调整区间，就是将就是把所有比分界点大的放到右边，所有比分界点小的放到左边
• 如何调整？双指针，一个从左往右走知道找到比分界点大的，一个从右往左…
  • 找到后，交换，再继续走，直到两指针相遇
• 递归处理 步骤2结束后，再次递归分界点两边的区间

// 参数解释：
// 1. int[] arr 需要排序的数组
// 2. int l  排序的左端点
// 3. int r	 排序的右端点
// 举例： 你要排序一个 int[] arr = {1,5,3,2,6} 数组内全部要排序，l=0，r=arr.length-1
public static void quickSort(int[] arr, int l, int r)
{
    //递归结束 条件
    if(l>=r) return;
    
    //1. 确定分界点
    int p = arr[l]; //我们取左端点
    //确定边界 +1-1是应为我们使用的do-while，开始前就会i++和j--
    int i = l-1;
    int j = r+1;
    
    //2. 调整区间
    while(i < j){
        do{
            i++;
        }while(arr[i] < p); //记得分号;
        
        do{
            j--;
        }while(arr[j] > p); 
        
        //找到两个不符合定义的点，即左边找到一个比分界点大的，右边找到一个比分界点小的
        //交换
        if(i < j){ //别忘了，很关键，两个指针还没有重合或穿过
            int tmp = arr[i];
            arr[i] = arr[j];
            arr[j] = tmp;
        }          
    }
    
    //3. 递归处理
    quickSort(arr, l, j);
    quickSort(arr, j+1, r);
    //此处为了边界不出问题，我们边界点一开始取q[l],那么递归的时候就l~j 和 j+1~r
    //这样就不会出现边界问题
}

2. Arrays.sort

事实上、在java的api中就有写好的快排，手写快排主要运用在面试中

内容总结

以上是互联网集市为您收集整理的基本算法——快速排序全部内容，希望文章能够帮你解决基本算法——快速排序所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---