Untitled

mail@pastecode.io avatar
unknown
java
3 years ago
1.3 kB
3
Indexable
Never

    public static void main(String[] args) {
        SortArrayHeap sa = new SortArrayHeap();
//        System.out.println(Arrays.toString(sa.sortArray(new int[]{5, 2, 3, 1})));
//        System.out.println(Arrays.toString(sa.sortArray(new int[]{1,2,3,4,5})));
//        System.out.println(Arrays.toString(sa.sortArray(new int[]{1,3,5,4,2})));
//        System.out.println(Arrays.toString(sa.sortArray(new int[]{5,1,1,2,0,0})));
    }

    public int[] sortArray(int[] nums) {
        int N = nums.length - 1;

        for (int i = N / 2; i >= 0; i--) {
            sink(nums, i, N);
        }

        while (N > 0) {
            exch(nums, 0, N);
            sink(nums, 0, --N);
        }
        return nums;
    }

    private void exch(int[] nums, int a, int b) {
        int tmp = nums[a];
        nums[a] = nums[b];
        nums[b] = tmp;
    }

    private void sink(int[] nums, int idx, int N) {
        while (idx != N && idx * 2 <= N) {
            int j = idx == 0 ? 1 : idx * 2;
            while (j < N && less(nums, j, j + 1)) {
                j++;
            }

            if (!less(nums, idx, j)) {
                break;
            }
            exch(nums, idx, j);
            idx = j;
        }
    }

    private boolean less(int[] nums, int a, int b) {
        return nums[a] < nums[b];
    }
}