八大排序之快速排序（java实现）

朱雀 2023-10-01 21:09 35阅读 0赞

## 一、快速排序原理（从小到大） ##

### 1.基本思想 ###

通过一趟排序将待排序列分成两部分，若一部分比另一部分小，则可继续对这两部分继续排序，从而使整个待排序列变得有序。

#### 2.算法描述 ####

1）将数组中的一个数字作为基准数

2）一般将数组中左边第一个数字作为基准数，然后从两边开始遍历，左边找比基准数大的，右边找比基准数小的，都找到后交换两个数的位置，当两指针相遇时，将指针所指向的数于基准数交换，然后数组被分成了两部分。

3）递归地对上一步分出的两数组进行排序。

### 3.图示 ###

这里只展示一轮，后续过程类似。

![watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBAY3JhenlLLg_size_20_color_FFFFFF_t_70_g_se_x_16][]

开始遍历

![watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBAY3JhenlLLg_size_20_color_FFFFFF_t_70_g_se_x_16 1][]

两边都遍历到，交换两数的位置

![watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBAY3JhenlLLg_size_20_color_FFFFFF_t_70_g_se_x_16 2][]

继续遍历

![watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBAY3JhenlLLg_size_20_color_FFFFFF_t_70_g_se_x_16 3][]

同样交换两数位置

![watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBAY3JhenlLLg_size_20_color_FFFFFF_t_70_g_se_x_16 4][]

继续遍历，两指针相遇

![watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBAY3JhenlLLg_size_20_color_FFFFFF_t_70_g_se_x_16 5][]

将两指针共同指向的数与及基准数交换位置

![watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBAY3JhenlLLg_size_20_color_FFFFFF_t_70_g_se_x_16 6][]

第一轮完成，此时基准数6的位置的有序的，数组被分成了两部分，左边的比基准数小，右边的比基准数大，对数组分成的两部分递归运用此方法即可得到有序数组

![watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBAY3JhenlLLg_size_20_color_FFFFFF_t_70_g_se_x_16 7][]

二、代码实现

public static void main(String[] args) {
            int[] nums = new int[]{6,1,2,5,4,3,9,7,10,8};
            quickSort(nums,0, nums.length - 1);
            System.out.println(Arrays.toString(nums));
        }
        public static void quickSort(int[] nums,int left,int right){
            //进行判断 如果左边索引比右边的索引要大 是不合法的 直接使用 return 结束这个方法
            if(left >= right){
                return;
            }
            //基准数
            int base = nums[left];
            //i指向最左边
            int i = left;
            //j指向最右边
            int j = right;
            while (i != j){
                //先由j 从 右向左检索比基准数小的，如果检索到比基准数小的就停下
                while (nums[j] >= base && i < j){
                    j--;
                }
                // i 从左向右检索
                while (nums[i] <= base && i < j){
                    i++;
                }
                //代码走到这里。i 和 j 都停下了，然后交换 i 和 j的位置元素
                int temp = nums[i];
                nums[i] = nums[j];
                nums[j] = temp;
            }
            // 如果while循环条件不成立，这就代表了 i和 j相遇了，就停止检索
            //交换基准数和这个相遇位置的元素进行交换
            nums[left] = nums[i];
            //把基准数赋值给相遇位置的元素
            nums[i] = base;
    
            //递归调用
            quickSort(nums,left,i - 1);
            quickSort(nums,j + 1,right);
        }

![watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBAY3JhenlLLg_size_20_color_FFFFFF_t_70_g_se_x_16 8][]

[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBAY3JhenlLLg_size_20_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/24d1db0706874530bd4e1d873531c3e2.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBAY3JhenlLLg==,size_20,color_FFFFFF,t_70,g_se,x_16
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBAY3JhenlLLg_size_20_color_FFFFFF_t_70_g_se_x_16 1]: https://img-blog.csdnimg.cn/cb618efcb2ad4300ae48ac7c74206f42.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBAY3JhenlLLg==,size_20,color_FFFFFF,t_70,g_se,x_16
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBAY3JhenlLLg_size_20_color_FFFFFF_t_70_g_se_x_16 2]: https://img-blog.csdnimg.cn/328b4067b85a4e8d9fb9421aee9d6ff5.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBAY3JhenlLLg==,size_20,color_FFFFFF,t_70,g_se,x_16
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBAY3JhenlLLg_size_20_color_FFFFFF_t_70_g_se_x_16 3]: https://img-blog.csdnimg.cn/1cae37acd2734f0b8dc1a2523aa48c78.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBAY3JhenlLLg==,size_20,color_FFFFFF,t_70,g_se,x_16
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBAY3JhenlLLg_size_20_color_FFFFFF_t_70_g_se_x_16 4]: https://img-blog.csdnimg.cn/0ccb71f1160c4e209825a9f0c3f0350c.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBAY3JhenlLLg==,size_20,color_FFFFFF,t_70,g_se,x_16
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBAY3JhenlLLg_size_20_color_FFFFFF_t_70_g_se_x_16 5]: https://img-blog.csdnimg.cn/1525ff0936a1443f9b9b028c4d3aeac8.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBAY3JhenlLLg==,size_20,color_FFFFFF,t_70,g_se,x_16
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBAY3JhenlLLg_size_20_color_FFFFFF_t_70_g_se_x_16 6]: https://img-blog.csdnimg.cn/39d8d2e3c3d64939adda9fced70a8a6d.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBAY3JhenlLLg==,size_20,color_FFFFFF,t_70,g_se,x_16
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBAY3JhenlLLg_size_20_color_FFFFFF_t_70_g_se_x_16 7]: https://img-blog.csdnimg.cn/b7858828783349178927061a4cf0cc2c.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBAY3JhenlLLg==,size_20,color_FFFFFF,t_70,g_se,x_16
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBAY3JhenlLLg_size_20_color_FFFFFF_t_70_g_se_x_16 8]: https://img-blog.csdnimg.cn/71d3075af87241cab44d6964ab4b4f8f.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBAY3JhenlLLg==,size_20,color_FFFFFF,t_70,g_se,x_16