java实现快速排序（简洁模板）

港控/mmm° 2023-07-12 12:00 0阅读 0赞

#### 快速排序的算法思想 ####

> 基于分治的思想，是冒泡排序的改进型。首先在数组中选择一个基准点（该基准点的选取可能影响快速排序的效率，后面讲解选取的方法），然后分别从数组的两端扫描数组，设两个指示标志（low指向起始位置，high指向末尾)，首先从后半部分开始，如果发现有元素比该基准点的值小，就交换low和high位置的值，然后从前半部分开始扫秒，发现有元素大于基准点的值，就交换low和high位置的值，如此往复循环，直到low>=high,然后把基准点的值放到high这个位置。一次排序就完成了。以后采用递归的方式分别对前半部分和后半部分排序，当前半部分和后半部分均有序时该数组就自然有序了。  
> 平均时间复杂度为O(n logn)，是一种不稳定的排序。

动图原理显示：  
![在这里插入图片描述][20200308175216109.gif]  
java代码实现：

package com.qcby.demo;
    
    import java.util.Arrays;
    
    public class Qsort { 
    
        private static void quick_sort(int[] arr, int l, int r){ 
    
            if(l >= r){ 
                return ;
            }
    
            int x = arr[l];
                int i = l - 1 ;
                int j = r + 1 ;
                while(i < j){ 
                do{ 
                    i++;
                }while(arr[i] < x);
                do{ 
                    j--;
                }while(arr[j] > x);
    
                if(i < j){ 
                    int temp = arr[i];
                    arr[i] = arr[j];
                    arr[j] = temp;
                }
            }
    
            quick_sort(arr, l , j);
            quick_sort(arr, j+1, r);
        }
    
        public static void main(String[] args) { 
    
            int[] a = new int[]{ 12,10,23,5,3,9,16,11,8};
            int len = a.length;
    
            quick_sort(a,0,len-1);
    
            System.out.println(Arrays.toString(a));
        }
    }

结果演示：  
![在这里插入图片描述][20200308180008715.png]  
参考博客：[https://www.cnblogs.com/BaoZiY/p/10931305.html][https_www.cnblogs.com_BaoZiY_p_10931305.html]

[20200308175216109.gif]: https://img-blog.csdnimg.cn/20200308175216109.gif
[20200308180008715.png]: https://img-blog.csdnimg.cn/20200308180008715.png
[https_www.cnblogs.com_BaoZiY_p_10931305.html]: https://www.cnblogs.com/BaoZiY/p/10931305.html