十大排序算法

//冒泡排序,将最大数沉到底部
private static void bubbleSort(int[] arr) {
    for (int i = 0; i < arr.length - 1; i++) {
        for (int j = 0; j < arr.length - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

//选择排序，将最小数放到顶部
private static void selectionSort(int[] arr) {
    for (int i = 0; i < arr.length - 1; i++) {
        int minIndex = i;
        for (int j = i + 1; j < arr.length; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }
        int temp = arr[i];
        arr[i] = arr[minIndex];
        arr[minIndex] = temp;
    }
}

//插入排序，对已排序数组进行插入
private static void insertionSort(int[] arr) {
    for (int i = 1; i < arr.length; i++) {
        int preIndex = i - 1;
        int current = arr[i];
        while (preIndex >= 0 && arr[preIndex] > current) {
            arr[preIndex + 1] = arr[preIndex];
            preIndex--;
        }
        arr[preIndex + 1] = current;
    }
}

//希尔排序（缩小增量排序），插入排序的升级版，通过增量分段，不断缩小增量直至1，进行插入排序
private static void shellSort(int[] arr) {
    for (int gap = (int) Math.floor(arr.length / 2); gap > 0; gap = (int) Math.floor(gap / 2)) { //增量不断缩小
        for (int i = gap; i < arr.length; i++) {
            int preIndex = i - gap;
            int current = arr[i];
            while (preIndex >= 0 && arr[preIndex] > current) {
                arr[preIndex + gap] = arr[preIndex];
                preIndex -= gap;
            }
            arr[preIndex + gap] = current;
        }
    }
}

//归并排序，从最小的两个有序数组不断合成有序数组，最终得到一个有序数组
private static int[] mergeSort(int[] arr) {
    if (arr.length < 2) {
        return arr;
    }
    int middle = (int) Math.floor(arr.length / 2);
    int[] left = new int[middle];
    int[] right = new int[arr.length - middle];
    for (int i = 0; i < arr.length; i++) {
        if (i < middle) {
            left[i] = arr[i];
        } else {
            right[i - middle] = arr[i];
        }
    }
    return merge(mergeSort(left), mergeSort(right));
}

private static int[] merge(int[] left, int[] right) {
    int[] newArr = new int[left.length + right.length];
    int leftIndex = 0;
    int rightIndex = 0;
    int newIndex = 0;
    while (left.length > leftIndex && right.length > rightIndex) {
        if (left[leftIndex] > right[rightIndex]) {
            newArr[newIndex++] = right[rightIndex++];
        } else {
            newArr[newIndex++] = left[leftIndex++];
        }
    }
    while (left.length > leftIndex) {
        newArr[newIndex++] = left[leftIndex++];
    }
    while (right.length > rightIndex) {
        newArr[newIndex++] = right[rightIndex++];
    }
    return newArr;
}

//快速排序，先分区（找到一个基准，所有小于该基准的数，都在其前面，大于的在其后面),递归排序
private static void quickSort(int[] arr, int left, int right) {
    if (left < right) {
        int pivot = partion(arr, left, right);
        quickSort(arr, left, pivot - 1);
        quickSort(arr, pivot + 1, right);
    }
}

private static int partion(int[] arr, int left, int right) {
    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;
}

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

//堆排序，构造大顶堆(父节点比子节点大)，将第一个元素和最后一个元素交换，再调整第一个到倒数第二个元素成新的大顶堆，再交换，依次进行
private static void heapSort(int[] arr) {
    for (int i = (int) Math.floor(arr.length / 2); i >= 0; i--) {
        herivy(arr, i, arr.length);
    }
    int len = arr.length;
    for (int i = arr.length - 1; i >= 0; i--) {
        swap(arr, 0, i);
        len--;
        herivy(arr, 0, len);
    }
}

private static void herivy(int[] arr, int i, int len) {
    int left = 2 * i + 1;
    int right = 2 * i + 2;
    int bigest = i;
    if (left < len && arr[left] > arr[bigest]) {
        bigest = left;
    }
    if (right < len && arr[right] > arr[bigest]) {
        bigest = right;
    }
    if (i != bigest) {
        swap(arr, i, bigest);
        herivy(arr, bigest, len);
    }
}

//计数排序，找到数组中的最大数，构造最大数数量的桶，填充对应的桶，按桶的顺序依次拿出数（好像不支持负数参与排序，需要把数组改为LinkHashMap存储）
private static void countingSort(int[] arr) {
    int max = findMax(arr);
    int[] buddleArr = new int[max + 1];
    for (int i = 0; i < arr.length; i++) {
        buddleArr[arr[i]]++;
    }
    int index = 0;
    for (int i = 0; i < buddleArr.length; i++) {
        while (buddleArr[i] > 0) {
            arr[index] = i;
            index++;
            buddleArr[i]--;
        }
    }
}

private static int findMax(int[] arr) {
    if (arr.length < 0) {
        return 0;
    }
    int max = arr[0];
    for (int i = 0; i < arr.length; i++) {
        if (arr[i] > max) {
            max = arr[i];
        }
    }
    return max;
}

//桶排序(需要满足均匀分布，不然桶的数量会暴增)，计数排序的升级版，通过数组里的最大最小值和桶大小，构造一定数量的桶，按照均匀分布将数放到桶里，然后对桶里数组排序，最后拿出数组
private static void bucketSort(int[] arr) {
    if (arr.length < 0) {
        return;
    }
    int bucketSize = 5;
    int min = arr[0];
    int max = arr[0];
    for (int i = 0; i < arr.length; i++) {
        if (arr[i] > max) {
            max = arr[i];
        } else if (arr[i] < min) {
            min = arr[i];
        }
    }
    int bucketCount = (max - min) / bucketSize + 1;
    ArrayList<Integer>[] bucketArr = new ArrayList[bucketCount];
    for (int i = 0; i < arr.length; i++) {
        int count = (arr[i] - min) / bucketSize;
        if (bucketArr[count] == null) {
            bucketArr[count] = new ArrayList<>();
        }
        bucketArr[count].add(arr[i]);
    }
    int index = 0;
    for (int i = 0; i < bucketCount; i++) {
        if (bucketArr[i] != null) {
            if (bucketArr[i].size() > 1) {
                Collections.sort(bucketArr[i]);
            }
            for (int j = 0; j < bucketArr[i].size(); j++) {
                arr[index] = bucketArr[i].get(j);
                index++;
            }
        }
    }
}

//基数排序，获取最大位数，然后优先排序低位，再排序高位，利用的思想是桶排序（好像不支持负数参与排序，需要把数组改为LinkHashMap存储）
private static void radixSort(int[] arr) {
    int maxDigit = findMaxDigit(arr);
    int dev = 1;
    int mod = 10;
    for (int i = 0; i < maxDigit; i++) {
        int maxCurrentDigit = arr[0] % mod / dev;
        for (int j = 0; j < arr.length; j++) {
            int currentDigit = arr[j] % mod / dev;
            if (currentDigit > maxCurrentDigit) {
                maxCurrentDigit = currentDigit;
            }
        }
        ArrayList<Integer>[] bucketArr = new ArrayList[maxCurrentDigit + 1];
        for (int j = 0; j < arr.length; j++) {
            int currentDigit = arr[j] % mod / dev;
            if (bucketArr[currentDigit] == null) {
                bucketArr[currentDigit] = new ArrayList<>();
            }
            bucketArr[currentDigit].add(arr[j]);
        }
        int index = 0;
        for (int j = 0; j < bucketArr.length; j++) {
            if (bucketArr[j] != null) {
                for (int d = 0; d < bucketArr[j].size(); d++) {
                    arr[index] = bucketArr[j].get(d);
                    index++;
                }
            }
        }
        dev *= 10;
        mod *= 10;
    }
}

private static int findMaxDigit(int[] arr) {
    if (arr.length < 0) {
        return 0;
    }
    int absMax = arr[0];
    for (int i = 0; i < arr.length; i++) {
        if (Math.abs(arr[i]) > absMax) {
            absMax = Math.abs(arr[i]);
        }
    }
    int digit = 0;
    while (absMax > 0) {
        absMax /= 10;
        digit++;
    }
    return digit;
}