[数据结构与算法]【数据结构】八大排序算法Java实现

1、插入排序

基本思想——把n个待排序的元素看成为一个有序表和一个无序表，开始时有序表中只包含一个元素，无序表中包含有n-1个元素，排序过程中每次从无序表中取出第一个元素，把它的排序码依次与有序表元素的排序码进行比较，将它插入到有序表中的适当位置，使之成为新的有序表。

public static void insertSort(int[] arr) {
    if (null == arr || arr.length < 2) {
        return;
    }
    for (int i = 1; i < arr.length; i++) {
        int insertVal = arr[i];
        int insertIndex = i - 1;
        // 1、insertIndex >= 0 保证数组不越界
        // 2、insertVal < arr[insertIndex] 说明没找到合适的位置,应该后移
        // 3、往前继续比较
        while (insertIndex >= 0 && insertVal < arr[insertIndex]) {
            arr[insertIndex + 1] = arr[insertIndex];
            insertIndex--;
        }
        // 此时插入的位置已找到 即 insertVal >= arr[insertIndex]
        arr[insertIndex + 1] = insertVal;
    }
}

2、希尔排序

基本原理——把记录按下标的一定增量分组，对每组使用直接插入排序算法排序;随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止

//交换法
public static void shellSortSwap(int[] arr) {
    int temp = 0;
    for (int step = arr.length / 2; step > 0; step /= 2) {
        for (int i = step; i < arr.length; i++) {
            for (int j = i - step; j >= 0; j -= step) {
                if (arr[j] > arr[j + step]) {
                    temp = arr[j];
                    arr[j] = arr[j + step];
                    arr[j + step] = temp;
                }
            }
        }
    }
}

优化

public static void shellSortMove(int[] arr) {
    for (int step = arr.length / 2; step > 0; step /= 2) {
        System.out.println("步长为" + step);
        for (int i = step; i < arr.length; i++) {
            int insertVal = arr[i];
            int insertIndex = i - step;
            while (insertIndex >= 0 && insertVal < arr[insertIndex]) {
                arr[insertIndex + step] = arr[insertIndex];
                insertIndex -= step;
            }
            arr[insertIndex + step] = insertVal;
            System.out.println(Arrays.toString(arr));
        }
    }
}

3、选择排序

基本思想——从数组中找到最小的，和第一个交换，然后从剩下的元素中，找到最小的和第二个交换，以此类推完成排序

public static void selectSort(int[] arr) {
    if (null == arr || arr.length < 2) {
        return;
    }
    for (int i = 0; i < arr.length - 1; i++) {
        int min = arr[i];
        int minIndex = i;
        for (int j = i + 1; j < arr.length; j++) {
            if (arr[j] < min) {
                min = arr[j];
                minIndex = j;
            }
        }
        if (minIndex != i) {
            arr[minIndex] = arr[i];
            arr[i] = min;
        }
    }
}

优化，每次选择最小值的同时，也可以将最大值选择并交换，减少选择次数

4、堆排序

基本思想——构建初始堆，将待排序列构成一个大顶堆(或者小顶堆)，升序大顶堆，降序小顶堆；将堆顶元素与堆尾元素交换，并断开(从待排序列中移除)堆尾元素。重新构建堆。重复元素交换和构建堆，直到待排序列中只剩下一个元素(堆顶元素)。

public static void heapSort(int[] arr) {
    // 构建大顶堆
    for (int i = arr.length / 2 - 1; i >= 0; i--) {
        // 从第一个非叶子结点,从下至上，从左至右
        adjustHeap(arr, i, arr.length);
    }
    // 调整结构+交换堆顶元素与末尾元素
    int temp = 0;
    for (int i = arr.length - 1; i > 0; i--) {
        // 交换
        temp = arr[i];
        arr[i] = arr[0];
        arr[0] = temp;
        adjustHeap(arr, 0, i);
    }

}


/**
     * 将一个数组(二叉树),调整成一个大顶堆
     * 完成将以i对应的的非叶子节点的树调整成大顶堆
     *
     * @param arr    待调整数组
     * @param i      表示非叶子结点在数组中的索引
     * @param length 表示对多少个元素进行调整
     */
private static void adjustHeap(int arr[], int i, int length) {
    // 保存当前变量
    int temp = arr[i];
    // 开始调整 k是i结点的左子节点
    for (int k = i * 2 + 1; k < length; k = k * 2 + 1) {
        // 如果左子节点的值小于右子节点
        if (k + 1 < length && arr[k] < arr[k + 1]) {
            // 让k指向右节点
            k++;
        }
        // 如果子节点大于父节点
        if (arr[k] > temp) {
            arr[i] = arr[k];// 把较大的值赋给当前节点
            i = k;// 让i指向k,继续比较
        } else {
            break;
        }
    }
    // 当for循环结束,已经将i为父节点的树的最大值调整上去了
    arr[i] = temp;//将temp值放到调整后的位置
}

5、冒泡排序

基本思想——通过对待排序序列从前向后，依次比较相邻的元素的值，所发现逆序则交换，使较大的元素从前向后移动，完成排序

public static void bubbleSort(int[] arr) {
    if (null == arr || arr.length < 2) {
        return;
    }
    int temp;
    int count = 0;
    for (int i = 0; i < arr.length - 1; i++) {
        for (int j = 0; j < arr.length - 1 - i; j++) {
            count++;
            if (arr[j] > arr[j + 1]) {
                temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
    System.out.println("比较了" + count + "次");
}

优化：如果一趟比较下来，没有发生元素交换说明序列已经有序，应该结束循环

public static void bubbleSort1(int[] arr) {
    if (null == arr || arr.length < 2) {
        return;
    }
    int temp;
    int count = 0;
    boolean flag = false;
    for (int i = 0; i < arr.length - 1; i++) {
        for (int j = 0; j < arr.length - 1 - i; j++) {
            count++;
            if (arr[j] > arr[j + 1]) {
                flag = true;
                temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
        if (flag) {
            flag = false;
        } else {
            break;
        }
    }
    System.out.println("比较了" + count + "次");
}

6、快速排序

基本思想——是对冒泡排序的一种改进。基本思想是:通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列

public static void quickSort(int[] arr, int left, int right) {
    int l = left;
    int r = right;
    int pivot = arr[(left + right) / 2];
    int temp = 0;
    while (l < r) {
        // 找到左边大于等于中轴值的元素
        while (arr[l] < pivot) {
            l++;
        }
        // 找到右边小于等于中轴值的元素
        while (arr[r] > pivot) {
            r--;
        }
        // 说明左边小于等于中轴值 右边大于等于中轴值
        if (l >= r) {
            break;
        }
        // 交换
        temp = arr[l];
        arr[l] = arr[r];
        arr[r] = temp;
        // 如果交换后 arr[l] == pivot 让r--
        if (arr[l] == pivot) {
            r--;
        }
        // 如果交换后 arr[r] == pivot 让l++
        if (arr[r] == pivot) {
            l++;
        }
    }
    if (l == r) {
        l++;
        r--;
    }
    // 向左递归
    if (left < r) {
        quickSort(arr, left, r);
    }
    // 向右递归
    if (l < right) {
        quickSort(arr, l, right);
    }
}

7、归并排序

基本思想——归并排序(MERGE-SORT）是利用归并的思想实现的排序方法，该算法采用经典的分治(divide-and-conquer）策略（分治法将问题分(divide)成一些小的问题然后递归求解，而治(conquer)的阶段则将分的阶段得到的各答案"修补"在一起，即分而治之)。

// 分 + 合
public static void mergeSort(int[] arr, int left, int right, int[] temp) {
    if (left < right) {
        int mid = (left + right) / 2;
        // 向左递归
        mergeSort(arr, left, mid, temp);
        // 向右递归
        mergeSort(arr, mid + 1, right, temp);
        merge(arr, left, mid, right, temp);
    }
}

/**
     * 合并
     *
     * @param arr   待排序数组
     * @param left  左边有序序列初始索引
     * @param mid   中间索引
     * @param right 右边索引
     * @param temp  中转数组
     */
public static void merge(int[] arr, int left, int mid, int right, int[] temp) {
    // 初始化i,左边有序序列的初始索引
    int i = left;
    // 初始化j,右边有序序列初始索引
    int j = mid + 1;
    // 指向temp数组的当前索引
    int t = 0;
    // 1、先把左右两边（有序）的数据,按规则填充到temp中,知道左右两边的有序数列
    // 有一边处理完毕为止
    while (i <= mid && j <= right) {
        // 如果左边的有序序列的当前元素，小于右边的有序序列的元素
        // 即将左边的当前元素拷贝到temp数组
        // 后移
        if (arr[i] < arr[j]) {
            temp[t] = arr[i];
            t++;
            i++;
        } else {
            temp[t] = arr[j];
            t++;
            j++;
        }
    }

    // 2、把有剩余数据的一边全部填充到temp
    while (i <= mid) {
        temp[t] = arr[i];
        i++;
        t++;
    }

    while (j <= right) {
        temp[t] = arr[j];
        j++;
        t++;
    }

    // 3、将temp中的所有元素拷贝到arr中
    // 并不是每次都拷贝所有元素
    t = 0;
    int tempLeft = left;
    while (tempLeft <= right) {
        arr[tempLeft] = temp[t];
        t++;
        tempLeft++;
    }

}

8、基数排序（桶排序）

基本思想——将所有待比较数值统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后,数列就变成一个有序序列。

public static void radixSort(int[] arr) {
    // 得到数组中最大数的位数
    int max = arr[0];
    for (int i = 0; i < arr.length; i++) {
        if (arr[i] > max) {
            max = arr[i];
        }
    }
    int maxLength = (max + "").length();

    // 定义一个二维数组，表示10个桶,每个桶就是一维数组
    int[][] bucket = new int[10][arr.length];

    // 定义一个一维数组，用于记录对应桶中放了多少个数据
    int[] bucketElementCounts = new int[10];

    for (int i = 0, n = 1; i < maxLength; i++, n *= 10) {
        for (int j = 0; j < arr.length; j++) {
            // 取出每个元素对应的位值进行排序
            int digitOfElement = arr[j] / n % 10;
            // 放入到对应的桶中
            bucket[digitOfElement][bucketElementCounts[digitOfElement]] = arr[j];
            bucketElementCounts[digitOfElement]++;
        }

        // 遍历每一个桶,将桶中的元素放入原数组
        int index = 0;
        for (int k = 0; k < 10; k++) {
            // 如果桶中有数据放入原数组
            if (bucketElementCounts[k] > 0) {
                for (int l = 0; l < bucketElementCounts[k]; l++) {
                    arr[index++] = bucket[k][l];
                }
            }
            // 将计数数组对应位置置0
            bucketElementCounts[k] = 0;
        }
    }
}