排序

1. 冒泡排序

// 从后向前冒泡，每次选出一个最小的
private static void bubbleSort(int[] arr) {
    for (int i=0; i<arr.length-1; i++) {
        for (int j=i; j<arr.length-1; j++) {
            if (arr[j] > arr[j+1]) {
                swap(arr, j, j+1);
            }
        }
    }
}

2. 插入排序

// 对于一个已经排好序的数组，先找到插入的位置，然后移动后续的元素，最后插入
private static void insertSort(int[] arr) {
    for (int i=1; i<arr.length; i++) {
        int tmp = arr[i];
        int index = -1;
        for (int j=i-1; j>=0; j--) {
            if (tmp < arr[j]) {
                arr[j+1] = arr[j];
                index = j;
            } else {
                break;
            }
        }
        if (index >= 0) arr[index] = tmp; 
    }
}

3. 选择排序

// 每次扫描数组，找到最小的值，然后交换
private static void selectSort(int[] arr) {
    for (int i=0; i<arr.length-1; i++) {
        int min = arr[i];
        int index = -1;
        for (int j=i+1; j<arr.length; j++) {
            if (arr[j] < min) {
                min = arr[j];
                index = j;
            }
        }
        if (index > 0) swap(arr, i, index);
    }
}

4. 希尔排序

// 相当于拓展了插入排序的步长
public static void shellSort(int[] arr) {
    int length = arr.length;
    int temp;
    for (int step = length / 2; step >= 1; step /= 2) {
        for (int i = step; i < length; i++) {
            temp = arr[i];
            int j = i - step;
            while (j >= 0 && arr[j] > temp) {
                arr[j + step] = arr[j];
                j -= step;
            }
            arr[j + step] = temp;
        }
    }
}

5. 归并排序

// 先拆分，再合并
private static int[] mergeSort(int[] sourceArr) {
    int[] arr = Arrays.copyOf(sourceArr, sourceArr.length);
    if (arr.length < 2) return arr;
    int mid = arr.length / 2;
    int[] left = Arrays.copyOfRange(arr, 0, mid);
    int[] right = Arrays.copyOfRange(arr, mid, arr.length);
    return merge(mergeSort(left), mergeSort(right));
}

// 合并两个有序数组
private static int[] merge(int[] arr1, int[] arr2) {
    int[] res = new int[arr1.length + arr2.length];
    int p1 = 0;
    int p2 = 0;
    int i = 0;

    while (p1 < arr1.length && p2 < arr2.length) {
        if (arr1[p1] < arr2[p2]) {
            res[i++] = arr1[p1++];
        } else if (arr1[p1] > arr2[p2]) {
            res[i++] = arr2[p2++];
        } else {
            res[i++] = arr1[p1++];
            res[i++] = arr2[p2++];
        }
    }

    while (p1 < arr1.length) {
        res[i++] = arr1[p1++];
    }

    while (p2 < arr2.length) {
        res[i++] = arr2[p2++];
    }

    return res;
}

6. 快速排序

private static void quickSort(int[] arr) {
    qsort(arr, 0, arr.length-1);
}

// 分治法，先拆分分区，然后，分别对分区排序
private static void qsort(int[] arr, int left, int right) {
    if (right < left) return;
    int index = partition(arr, left, right);
    qsort(arr, left, index-1);
    qsort(arr, index+1, right);
} 

private static int partition(int[] arr, int left, int right) {
    // 设定基准值（pivot）
    int pivot = left;
    int index = pivot + 1;
    for (int i = index; i <= right; i++) {
        if (arr[i] < arr[pivot]) {
            swap(arr, i, index);
            index++;
        }
    }
    swap(arr, pivot, index - 1);
    return index - 1;
}

7. 堆排序

// 每次堆化后，都能选出一个最大的元素
// 1. 堆化，对所有非叶子节点，做堆化
// 2. 删除头节点
private static void heapSort(int[] arr) {
    for (int n=arr.length; n>1; n--) {
        heapify(arr, n);
        // 把堆顶的元素，移动到末尾，然后重新堆化
        swap(arr, 0, n-1);
    }
}

// 堆化大顶堆
private static void heapify(int[] arr, int n) { 
    for (int i=(n/2)-1; i>=0; i--) {
        // 找到比较小的叶子节点的索引
        int j = i * 2 + 1;
        if (i*2+2 < n && arr[i*2+1] < arr[i*2+2]) {
            j = i * 2 + 2;
        }
        if (arr[j] > arr[i]) {
            swap(arr, i, j);
        }
    }
}

8. 计数排序

// 每个桶只存储单一键值
// 比如按年龄排序

9. 桶排序

// 每个桶存储一定范围的数值

10. 基数排序

// 根据键值的每位数字来分配桶
// 把每个数的值，当作数组索引