快速手写快排

问题描述

[[1,2],[2,3],[4,5],[7,9],[0,3],[0,1],[1,1]]

这是坐标输入，请按照离原点的距离对坐标进行排序，要求使用手写的快速排序算法

划分

划分业务：distance()计算距离，swap()负责交换位置，sort()负责对应区间的快速排序的调度(递归)

代码

/**
 * [[1,2],[2,3],[4,5],[7,9],[0,3],[0,1],[1,1]]
 */
public class QuickSort {
    public static void main(String[] args) {
        int[][] data = {{1, 2}, {2, 3}, {4, 5}, {7, 9}, {0, 3}, {0, 1}, {1, 1}};
        //int[][] data = {{1, 1}, {0, 3}, {4, 1}, {3, 2}, {5, 2}, {8, 1}, {1, 7}};

        sort(0, data.length - 1, data);
        for (int i = 0; i < data.length; i++) {
            int[] tt = data[i];
            for (int i1 = 0; i1 < tt.length; i1++) {
                System.out.print(tt[i1] + " ");
            }
            System.out.println();
        }
    }

    public static void sort(int start, int end, int[][] arr) {
        if (start >= end) {
            return;
        }
        int i, j;
        for (i = start + 1, j = end; i <= j; ) {
            if (distance(arr[start]) >= distance(arr[i])) {
                i++;
            } else {
                swap(i, j, arr);
                j--;
            }
        }
        swap(start, j, arr);
        sort(start, j - 1, arr);
        sort(j + 1, end, arr);
    }

    public static void swap(int i, int j, int[][] arr) {
        int[] temp = arr[j];
        arr[j] = arr[i];
        arr[i] = temp;
    }

    public static int distance(int[] point) {
        return point[0] * point[0] + point[1] * point[1];
    }
}

代码快速理解和记忆（抽象化）

一次快排能够确定一个元素的固定位置，分治的思想使得排序的效率较高，多数情况下规模一次次一半一半地缩小