Javaは高速ソート再帰と非再帰を実現

1730 ワード

//        
    public static void QuickSort(long[] numbers, int l, int h) {
        int i;
        if (l < h) {
            i = Hoare(numbers, l, h);
            QuickSort(numbers, 1, i - 1);
            QuickSort(numbers, i + 1, h);
        }
    }

    static class Part {
        int low;
        int high;

        public Part(int low, int high) {
            this.low = low;
            this.high = high;
        }
    }

    //       
    public static void QuickSort2(long[] numbers) {
        int size = numbers.length;
        int low = 0, high = size - 1;
        int i;
        Stack stact = new Stack<>();
        int tag = 1;
        do {
            while (low < high) {
                i = Hoare(numbers, low, high);
                Part part = new Part(i + 1, high);
                stact.push(part);
                high = i - 1;
            }
            if (stact.isEmpty()) {
                tag = 0;
            } else {
                Part part = stact.pop();
                low = part.low;
                high = part.high;
            }
        } while (tag == 1);
    }

    public static int Hoare(long[] numbers, int low, int high) {
        long x = numbers[low];
        while (low < high) {
            while (low == x) {
                high--;
            }
            if (low < high) {
                numbers[low] = numbers[high];
                low++;
            }
            while (low < high && numbers[low] <= x) {
                low++;
            }
            if (low < high) {
                numbers[high] = numbers[low];
                high--;
            }
        }
        numbers[low] = x;
        return low;
    }