【Java】递归实现快速排序

傷城~ 2022-10-02 00:57 153阅读 0赞

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNDE2MjI2_size_16_color_FFFFFF_t_70]  
图转自：[http://developer.51cto.com/art/201403/430986.htm][http_developer.51cto.com_art_201403_430986.htm]

package edu.xlead;
    
    import java.util.Arrays;
    
    public class QuickSort {
        
        /**
         *
         * @param arr 需要排序的数组
         * @param left The leftmost index at the beginning
         * @param right The rightmost index at the beginning =arr.length-1
         */
        public static  void quickSort(int []arr,int left,int right){
        
            if(left>right){
        
                return;
            }
            int tmp,tem;//Temporary variables
            int i=left;
            int j=right;
            int temp=arr[left];//benchmark start with the leftmost index
            while (i<j){
        
                //From right to left
                while (temp<=arr[j]&&i<j){
        
                    j--;
                }
                //From left to right
                while (temp>=arr[i]&&i<j){
        
                    i++;
                }
                //SWAP
                if (i<j){
        
                    tmp=arr[i];
                    tem=arr[j];
                    arr[i]=tem;
                    arr[j]=tmp;
                }
            }
            //The loop is broken:i=j
            //Put the reference point at the point of i
            arr[left]=arr[i];
            arr[i]=temp;
            //Recurse to the left half arr
            quickSort(arr,left,j-1);
            //Recurse to the right half arr
            quickSort(arr,j+1,right);
        }
    
        public static void main(String[] args) {
        
            int []a={
        112,115,633,2578,268,225,245};
            quickSort(a,0,a.length-1);
            System.out.print(Arrays.toString(a));
        }
    }

![在这里插入图片描述][20190616211021504.png]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNDE2MjI2_size_16_color_FFFFFF_t_70]: /images/20220113/04cf069e9bb84481b20e9627eac8d356.png
[http_developer.51cto.com_art_201403_430986.htm]: http://developer.51cto.com/art/201403/430986.htm
[20190616211021504.png]: /images/20220113/3f438b8539d842f88542805d201f9767.png