手撕快速排序

内容导读

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

内容图文

手撕快速排序

• 一. 快速排序动态图
• 二. 快速排序流程
• 三. Java代码实现

一. 快速排序动态图

时间复杂度为 O(NlogN) 不稳定

二. 快速排序流程

主要思想就是分治

1. 确定分界点，去左边界 pivot=arr[left]。
2. 调整区间 使小于等于pivot的值在左边，使大于等于pivot的值在右边。
3. 当i==j两个指针相遇的时候，说明arr数组已经分为左右两个区间了。
4. 再递归处理左右两个区间，重复上面三个步骤
5. 递归出来的条件是区间只剩下一个元素

三. Java代码实现

注释给的非常详细了，自己debug领悟一下

package com.xizi.sort;

import java.io.BufferedInputStream;
import java.util.Arrays;
import java.util.Scanner;

public class QuickSort {

    public static void main(String[] args) {
        int[] arr=new int[]{5,4,3,2,1};
        int n=arr.length;
        quickSort(arr,0,n-1);
        for(int a:arr) {
            System.out.print(a+" ");
        }
        //底层使用双轴快速排序
        Arrays.sort(arr);
    }

    //时间复杂度 O(NlogN)
    //1. 选取pivot
    //2. 划分，根据选取的pivot将数组划分成小于pivot的部分和大于pivot的部分
    //3. 递归求解小于pivot和大于pivot的部分
    public static void quickSort(int[] arr,int left,int right) {
        //边界判断 区间只剩下一个元素时直接返回
        if(left>=right) {
            return;
        }
        //取左边界为分界点
        int pivot=arr[left];
        //下面使用do while循环 i先减1 j加1
        int i=left-1,j=right+1;
        // 调整区间 使小于pivot的值在左边  大于pivot的值在右边
        // 当i==j相遇 arr[]就会被划分为两个区域
        while(i<j) {
            //从前往后找到第一次小于pivot的值
            do {i++;}while(arr[i]<pivot);
            //从后往前找到第一次大于pivot的值
            do {j--;}while(arr[j]>pivot);
            //然后进行交换
            if(i<j) {
                int temp=arr[i];
                arr[i]=arr[j];
                arr[j]=temp;
            }
        }
        //递归处理 左右区间
        quickSort(arr,left,j);
        quickSort(arr,j+1,right);

    }

}

内容总结

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

内容备注

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

内容手机端

---