JAVAクイックソート

クイックソート思想:配列の最後の要素を基準とし、最後の要素の左側からrightとし、調整が必要な区間の最初の要素をleftとする.調整アルゴリズム:leftから基準値より大きい最初の下付き文字を右に探し始め、rightから基準値より小さい最初の下付き文字を左に探します.leftとrightが出会っていなければ、leftとrightの位置の要素を交換し、leftとrightが出会うまで、基準値と出会った位置の値を交換します.出会ったときの下付き文字を返します.再帰は、返される位置の下付きの左と右から、配列全体を再帰的に調整します.再帰コード:

 public void quickSort(int[] arr){
        Help(arr,0,arr.length-1);
    }

    public void Help(int[] arr,int left,int right){
        if(left>=right){
            return;
        }
        int index = patition(arr,left,right);
        Help(arr,left,index-1);
        Help(arr,index+1,right);
    }

    public Integer patition(int[] arr,int left,int right){
        int tmp = right;
        while(left<right){
            while(left<right && arr[right]>arr[tmp]){
                right--;
            }
            while(left<right && arr[left]<arr[tmp]){
                left++;
            }
            int t =arr[left];
            arr[left]=arr[right];
            arr[right]=t;
        }
        if(left>=right) {
            int t = arr[left];
            arr[left] = arr[tmp];
            arr[tmp] = t;
        }
        return left;
    }

非再帰コード:

 public void QuickSortLoop(int[] arr){
        Stack<Integer> stack = new Stack<>();
        stack.push(arr.length-1);
        stack.push(0);
        while(!stack.isEmpty()){
            int left =stack.pop();
            int right= stack.pop();
            if(left>=right){
                continue;
            }
            int index = patition(arr,left,right);
            stack.push(index-1);
            stack.push(0);
            stack.push(right);
            stack.push(index+1);
        }
    }
    public Integer patition(int[] arr,int left,int right){
        int tmp = right;
        while(left<right){
            while(left<right && arr[right]>arr[tmp]){
                right--;
            }
            while(left<right && arr[left]<arr[tmp]){
                left++;
            }
            int t =arr[left];
            arr[left]=arr[right];
            arr[right]=t;
        }
        if(left>=right) {
            int t = arr[left];
            arr[left] = arr[tmp];
            arr[tmp] = t;
        }
        return left;
    }