快速排序的两种实现（java）

ゞ浴缸里的玫瑰 2022-05-16 03:35 168阅读 0赞

用**递归方式**去做，这个比较明确，下面针对具体的方法分两种情况

## （1）第一种 ##

做两个游标，找！从前面找到比标准值大的数，从后面找到比标准值小的数，然后交换位置。以此重复。。。  
![这里写图片描述][70]  
具体步骤：  
1，定义i=0，j=A.lenght-1，i为第一个数的下标，j为最后一个数下标  
2，从数组的最后一个数Aj从右往左找，找到第一小于key的数，记为Aj；  
3，从数组的第一个数Ai 从左往右找，找到第一个大于key的数，记为Ai；  
4，交换Ai 和Aj  
5，重复这个过程，直到 i=j  
6，调整key的位置，把A\[i\] 和key交换

代码：

public class QuickSort {
        public static void main(String[] args) {
            int[] arrays = {
       5,7,2,9,4,6,8};
            sort(arrays, 0, arrays.length-1);
            System.out.println(Arrays.toString(arrays));
        }
        //做递归
        private static void sort(int[] arrays, int left, int right) {
            if(left < right){
       //递归算法的跳出条件
                int mid = partition(arrays, left , right);
                sort(arrays, left, mid - 1);//递归对低子表递归排序
                sort(arrays, mid + 1, right);//递归对高子表递归排序
            }
        }
    
        private static int partition(int[] arrays, int low, int high) {
            int key = arrays[low];//基准元素 
            int start = low;
            while(low < high){
                //从high开始找比基准小的
                while(low < high && arrays[high] > key){
                    high--;
                }
                //从low开始找比基准大的
                while(low < high && arrays[low] <= key){
                    low++;
                }
                //将两个数交换位置
                if(low < high){             
                    int tem = arrays[low];
                    arrays[low] = arrays[high];
                    arrays[high] = tem;
                }
            }
            //调整key的位置，将key与low交换位置 
            int p = arrays[low];
            arrays[low] = arrays[start];
            arrays[start] = p;
            return low;
        }
    }

## （2）第二种 ##

选择一个基准元素,通常选择第一个元素或者最后一个元素,通过一趟扫描，将待排序列分成两部分,一部分比基准元素小,一部分大于等于基准元素,此时基准元素在其排好序后的正确位置,然后再用同样的方法递归地排序划分的两部分。

/*快速排序： 选择一个基准，将数组分成两部分；比基准大的一部分，比基准小的一部分； 然后重复此过程*/
    public class QuickSort {
    
        public static void main(String[] args) {
            int[] a = {
       2,8,4,5,3,5,4,8,14,54,23};
            sort(a,0,a.length-1);
            System.out.println(Arrays.toString(a));
        }
        //做递归
        public static void sort(int[] a, int left, int right){
            if(left < right){
       //如果不加这个判断递归会无法退出导致堆栈溢出异常 
                int mid = partion(a, left, right);
                sort(a, left, mid - 1);//递归对低子表递归排序
                sort(a, mid + 1, right); //递归对高子表递归排序
            }
        }
        private static int partion(int[] a, int low, int high) {
            int key = a[low];//基准元素，排序中会空出来一个位置 
            while(low<high){  
                while(low<high && a[high]>=key){
       //从high开始找比基准小的，与low换位置 
                    high--;  
                }  
                a[low]=a[high];  
                while(low<high && a[low]<=key){
       //从low开始找比基准大,放到之前high空出来的位置上 
                    low++;  
                }  
                a[high]=a[low];  
            }  
            a[low]=key;//此时low=high 是基准元素的位置，也是空出来的那个位置 
            return low; 
        }
    }

[70]: /images/20220516/c9ebc3aea0b1467e8fbaa212afc84fa3.png