常见的数据结构

排序算法

选择排序

private static void selectSort(int[] num) {
    // 找到最小的
    for (int i = 0; i < num.length; i++) {
        for (int j = i; j < num.length; j++) {
            if (num[i] > num[j]) {
                int temp = num[j];
                num[j] = num[i];
                num[i] = temp;
            }
        }
    }
}

冒泡排序

private static void bubbleSort2(int[] num) {
    // 比较的趟次
    for (int i = 0; i < num.length - 1; i++) {
        // 临近排序
        for (int j = 0; j < num.length - 1 - i; j++) {
            if (num[j] > num[j + 1]) {
                int temp = num[j];
                num[j] = num[j + 1];
                num[j + 1] = temp;
            }
        }
    }
}

快速排序

private static void quickSort(int[] num, int left, int right) {
    int start = left;
    int end = right;
    if (left > right) {
        return;
    }
    // 定义一个基准值
    int base = num[left];
    while (left < right) {
        // 找到比他小的
        while (num[right] >= base && left < right) {
            right--;
        }
        num[left] = num[right];
        while (num[left] <= base && left < right) {
            left++;
        }
        num[right] = num[left];
    }
    num[left] = base;
    quickSort(num, start, end - 1);
    quickSort(num, start + 1, end);
}

插入排序

//核心代码---开始
public static void insertionSort(int[] arr) {
    for (int i = 0; i < arr.length; i++) {
        // 寻找元素 arr[i] 合适的插入位置，其实局部有点像冒泡排序
        for (int j = i; j > 0; j--) {
            if (arr[j] < arr[j - 1]) {
                swap(arr, j, j - 1);
            } else {
                break;
            }
        }
    }
}
//核心代码---结束

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

希尔排序

分组的插入排序

//核心代码---开始
public static void shellSort(int[] arr) {
    int step = arr.length / 2;
    // 分组步数
    while (step > 0) {
        // 每组
        for (int i = step; i < arr.length; i++) {
            // 组内排序
            for (int j = i; j >= step; j = j - step) {
                if (arr[j] < arr[j - step]) {
                    swap(arr, j, j - step);
                } else {
                    break;
                }
            }
        }

        step /= 2;
    }


}
//核心代码---结束

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

基数排序

private static void radixSort(int[] arr) {
    if (arr.length == 0) {
        return;
    }
    int[][] bucket = new int[10][arr.length];
    // 对应桶中的个数
    int[] bucketElementCounts = new int[10];

    //得到最大数的长度
    int maxNumLength = ("" + Arrays.stream(arr).max().getAsInt()).length();
    //循环遍历,进行排序
    int n = 1;
    for (int i = 0; i < maxNumLength; i++) {
        //装桶
        for (int value : arr) {
            int digitOfElement = value / n % 10;

            bucket[digitOfElement][bucketElementCounts[digitOfElement]] = value;
            bucketElementCounts[digitOfElement] += 1;
        }
        n = n * 10;

        //从桶中取出数据
        int index = 0;
        for (int j = 0; j < bucket.length; j++) {
            for (int k = 0; k < bucketElementCounts[j]; k++) {
                // 有数据,取出
                if (bucketElementCounts[j] > 0) {
                    arr[index] = bucket[j][k];
                    index++;
                }
            }
            bucketElementCounts[j] = 0;
        }
        System.out.printf("第%d次排序完的结果为:\n", (i + 1));
        System.out.println(Arrays.toString(arr));
    }
}

归并排序

private static int[] mergeSort(int[] arr) {
    // 若待排序数组长度<2，则直接返回
    if (arr.length < 2) {
        return arr;
    }
    int mid = arr.length / 2;
    return process(
        mergeSort(Arrays.copyOfRange(arr, 0, mid)),
        mergeSort(Arrays.copyOfRange(arr, mid, arr.length)));
}

// 合并两个有序数组
private static int[] process(int[] arr1, int[] arr2) {
    int[] rs = new int[arr1.length + arr2.length];
    // i为arr1的index,j为arr2的index,k为re的index
    int arr1Index = 0;
    int arr2Index = 0;
    int rsIndex = 0;
    // 获取两个数组较小元素，填入rs内
    while (arr1Index < arr1.length && arr2Index < arr2.length) {
        rs[rsIndex++] = (arr1[arr1Index] < arr2[arr2Index]) ? arr1[arr1Index++] : arr2[arr2Index++];
    }
    // 若arr1有元素剩余，全部填入rs内
    if (arr1Index != arr1.length) {
        for (int p = arr1Index; p < arr1.length; p++) {
            rs[rsIndex++] = arr1[p];
        }
    }
    // 若arr2内有元素剩余，全部填入rs内
    if (arr2Index != arr2.length) {
        for (int p = arr2Index; p < arr2.length; p++) {
            rs[rsIndex++] = arr2[p];
        }
    }
    return rs;
}

堆排序（待定）

这里我们用到两种堆，其实也算是一种。
大顶堆：每个节点的值都大于或者等于它的左右子节点的值。
小顶堆：每个节点的值都小于或者等于它的左右子节点的值。

如果我们把这种逻辑结构映射到数组中，就是下边这样

从这里我们可以得出以下性质（重点）
对于大顶堆：arr[i] >= arr[2i + 1] && arr[i] >= arr[2i + 2]
对于小顶堆：arr[i] <= arr[2i + 1] && arr[i] <= arr[2i + 2]

arr[2i + 1] 是左子树的根节点， arr[2i + 2] 是右子树的根节点

数据结构与算法