排序

一、二分类目

1. 快速排序

选定某值，保证两侧的值分别小于和大于该值。

public static void sort(int[] arr, int left, int right) {
    if (left + 1 > right) {
        return;
    }
    int leftbak = left;
    int rightbak = right;
    int key = arr[left];
    while (left < right) {
        while (left < right && arr[right] >= key) {
            right--;
        }
        arr[left] = arr[right];
        while (left < right && arr[left] <= key) {
            left++;
        }
        arr[right] = arr[left];
    }
    arr[right] = key;

    sort(arr, leftbak, left - 1);
    sort(arr, left + 1, rightbak);
}

含重复元素的快排-三相切分快排

//TODO

2. 归并排序

分治思路，把一个整体进行二分到最小单元，然后进行归并。归并时可视为两个有序集的合并。

public static void sort(int[] arr, int left, int right, int[] tmp) {
    if (left == right) {
        return;
    }
    int mid = (left + right) / 2;
    // divde [left, right]
    sort(arr, left, mid, tmp);
    sort(arr, mid + 1, right, tmp);

    // merge
    int leftCur = left;
    int rightCur = mid + 1;
    int i = 0;
    while (leftCur <= mid || rightCur <= right) {
        if (leftCur > mid || (rightCur <= right && arr[leftCur] > arr[rightCur])) {
            tmp[i++] = arr[rightCur++];
        } else {
            tmp[i++] = arr[leftCur++];
        }
    }
    while (--i >= 0) {
        arr[right--] = tmp[i];
    }
}

二、比较类目

1. 选择排序

每次选取第i小的元素，进行交换排序，目标是已排序的子集是最终有序集合的前缀。

public static void sort(int[] arr) {
    for (int i = 0; i < arr.length - 1; i++) {
        int min = i;
        for (int j = i + 1; j < arr.length - 1; j++) {
            if (arr[j] < arr[min]) {
                 min = j;
            }
        }
        swap(arr, i, min);
    }
}

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

2. 插入排序

把当前元素插入已部分排好序的相应位置，目标是只关注当前元素放置合适的位置

public static void sort(int[] arr) {
    for (int i = 1; i < arr.length; i++) {
        for (int index = i; index > 0 && arr[index - 1] > arr[index]; index--) {
            swap(arr, index, index - 1);
        }
    }
}

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

3. 冒泡排序

n个元素的集合，最多遍历n轮，目标是在每轮把错位的最大元素进行归位

public static void sort(int[] arr) {
    // 外层循环为轮次，最多循环n次  
    for (int i = 0; i < arr.length - 1; i++) {
        boolean hasSwap = false;
        for (int j = 0; j < arr.length - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                swap(arr, j, j + 1);
                hasSwap = true;
            }
        }
        if (!hasSwap) {
            break;
        }
    }
}

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

三、堆排序

public class HeapSort {

    public void sort(int[] arr) {
        if (arr == null || arr.length <= 1) {
            return;
        }
        // 1. 构建大顶堆
        for (int i = 1; i < arr.length; i++) {
            shiftUp(arr, i);
        }

        System.out.println("over" + Arrays.toString(arr));

        // 2. 取顶元素-排序
        for (int end = arr.length - 1; end > 0; end--) {
            swap(arr, 0, end);
            shiftDown(arr, end - 1);
            System.out.println("heap" + Arrays.toString(arr));
        }
    }

    void shiftDown(int[] arr, int end) {
        int cur = 0;
        int parentL;
        int parentR;
        while (true) {
            parentL = (cur + 1) * 2 - 1;
            if (parentL > end) {
                break;
            }
            parentR = parentL + 1;

            int max;
            if (parentR > end) {
                max = parentL;
            } else {
                if (arr[parentL] > arr[parentR]) {
                    max = parentL;
                } else {
                    max = parentR;
                }
            }
            if (arr[max] > arr[cur]) {
                swap(arr, cur, max);
                cur = max;
            } else {
                break;
            }
        }
    }

    void shiftUp(int[] arr, int i) {
        int parentIndex = -1;
        do {
            if (parentIndex != -1) {
                i = parentIndex;
            }
            parentIndex = (i + 1) / 2 - 1;
            if (parentIndex < 0) {
                break;
            }
        } while (arr[i] > arr[parentIndex] && swap(arr, i, parentIndex));
    }

    boolean swap(int[] arr, int left, int right) {
        Util.swap(arr, left, right);
        return true;
    }
}