排序算法合集

package com.company;
import java.util.Arrays;
public class Main {
    public static void main(String[] args) {
        int n = 8000000;
        int[] array = new int[n];
        for (int i = 0; i < n; i++) {
            array[i] = (int) (Math.random() * n);
        }
        System.out.println(Arrays.toString(array));
        long l = System.currentTimeMillis();
        radixSort(array);
        long l2 = System.currentTimeMillis();
        System.out.println((l2 - l) / 1000);
    }
    public static void radixSort(int[] array){
        //1. 得到数组中最大的数的位数
        int max = array[0];//假设第一数就是最大数
        for (int i = 1; i < array.length; i++) {
            if (array[i] > max){
                max = array[i];
            }
        }
        //得到最大数是几位数
        int maxLength = (max + "").length();
        //定义一个二维数组，表示 10 个桶, 每个桶就是一个一维数组
        //说明
        //1. 二维数组包含 10 个一维数组
        //2. 为了防止在放入数的时候，数据溢出，则每个一维数组(桶)，大小定为 arr.length
        //3. 名明确，基数排序是使用空间换时间的经典算法
        int[][] bucket = new int[10][array.length];
        int[] bucketElementCounts = new int[10];
        for (int i = 0 , n = 1; i < maxLength; i++, n *= 10) {
            //(针对每个元素的对应位进行排序处理)， 第一次是个位，第二次是十位，第三次是百位.
            for (int j = 0; j < array.length; j++) {
                //取出每个元素的对应位的值
                int digitofElement = array[j] / n % 10;
                //放入到对应的桶中
                bucket[digitofElement][bucketElementCounts[digitofElement]] = array[j];
                bucketElementCounts[digitofElement]++;
            }
            int index = 0;
            for (int j = 0; j < bucketElementCounts.length; j++) {
                    if (bucketElementCounts[j] != 0){
                        for (int k = 0; k < bucketElementCounts[j]; k++) {
                            array[index++] = bucket[j][k];
                        }
                        bucketElementCounts[j] = 0;
                    }
            }
        }
    }
    public static void mergeSort(int[] array, int left, int right, int[] temp){
        if (left < right){
            int mid = (left + right) / 2;
            mergeSort(array, left, mid, temp);
            mergeSort(array, mid + 1, right, temp);
            merge(array, left, mid, right, temp);
        }
    }
    public static void merge(int[] array, int left, int mid, int right, int[] temp){
        System.out.println("=============");
        int i = left;
        int j = mid + 1;
        int t = 0;
        while (i <= mid && j <= right){
            if (array[i] <= array[j]){
                temp[t] = array[i];
                t++;
                i++;
            }else {
                temp[t] = array[j];
                t++;
                j++;
            }
        }
        while (i <= mid){
            temp[t] = array[i];
            t++;
            i++;
        }
        while (j <= right){
            temp[t] = array[j];
            t++;
            j++;
        }
        t = 0;
        int tempLeft = left;
        System.out.println("tempLeft=" + tempLeft + "\tright=" + right);
        while (tempLeft <= right){
            array[tempLeft] = temp[t];
            tempLeft++;
            t++;
        }

    }
    public static void quickSort(int[] array,int left,int right){
        int l = left;
        int r = right;
        int temp = 0;
        int pivot = array[(l + r) / 2];
        while (l < r){
            //在 pivot 的左边一直找,找到大于等于 pivot 值,才退出
            while (array[l] < pivot){
                l++;
            }
            //在 pivot 的右边一直找,找到小于等于 pivot 值,才退出
            while (array[r] > pivot){
                r--;
            }
            //如果 l >= r 说明 pivot 的左右两的值，已经按照左边全部是
            //小于等于 pivot 值，右边全部是大于等于 pivot 值
            if (l >= r){
                break;
            }
            temp = array[l];
            array[l] = array[r];
            array[r] = temp;
            if (array[l] == pivot){
                r--;
            }
            if (array[r] == pivot){
                l++;
            }
        }
        if (l == r){
            l++;
            r--;
        }
        if (left < r) {
            quickSort(array, left, r);
        }
        if (right > l) {
            quickSort(array, l, right);
        }
    }
    public static void shellSort(int[] array){
        int temp = 0;
        for (int gap = array.length / 2;gap > 0;gap /= 2){
            // 根据前面的逐步分析，使用循环处理
            for (int i = gap; i < array.length; i++) {
                // 遍历各组中所有的元素(共 gap 组，每组有个元素), 步长 gap
                for (int j = i - gap; j >= 0; j -= gap) {
                    // 如果当前元素大于加上步长后的那个元素，说明交换
                    if (array[j] > array[j + gap]){
                        temp = array[j];
                        array[j] = array[j + gap];
                        array[j + gap] = temp;
                    }
                }

            }
        }
    }
    public static void shellSort2(int[] array){
        for (int gap = array.length / 2; gap > 0; gap /= 2) {
            // 增量 gap, 并逐步的缩小增量
            for (int i = gap; i < array.length; i++) {
                // 从第 gap 个元素，逐个对其所在的组进行直接插入排序
                int j = i;
                int temp = array[i];
                if (array[j] < array[j - gap]){
                    while (j - gap >= 0 && temp < array[j - gap]){
                        array[j] = array[j - gap];
                        j -= gap;
                    }
                    array[j] = temp;
                }

            }
        }

    }

    public static void insertSort(int[] array) {
        for (int i = 1; i < array.length; i++) {
            int insertVal = array[i];
            int insertIndex = i - 1;
            while (insertIndex >= 0 && insertVal < array[insertIndex]) {
                array[insertIndex + 1] = array[insertIndex];
                insertIndex--;
            }
            if (insertIndex + 1 != i){
                array[insertIndex + 1] = insertVal;
            }
        }
    }

    public static void selectSort(int[] array) {
        //第 1 轮
        for (int i = 0; i < array.length - 1; i++) {
            int minIndex = i;
            int min = array[i];
            for (int j = i + 1; j < array.length; j++) {
                if (min > array[j]) { //说明假定的最小值，并不是最小
                    min = array[j]; //重置 min
                    minIndex = j;
                }
            }
            //将最小值，放在 arr[0], 即交换
            if (minIndex != i) {
                array[minIndex] = array[i];
                array[i] = min;
            }
        }

    }

    public static void bubbleSort(int[] arr) {
        int temp = 0;
        boolean flag = false;// 标识变量，表示是否进行过交换
//        冒泡排序 的时间复杂度 O(n^2)
        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]) {
                    flag = true;
                    temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
            if (!flag) { // 在一趟排序中，一次交换都没有发生过
                break;
            } else {
                flag = false; // 重置 flag!!!, 进行下次判断
            }
        }
    }
}