真的用不上，排序算法

冒泡排序（稳定）

思想：每一遍将最大的数下沉

复杂度：n^2

 public void bubbleSort(int[] arr,int n){
        boolean flag;
        for (int i = 1; i < n; i++) {
            flag = false;
            for (int j = 0; j < n-i; j++) {
                if(arr[j]<arr[j+1]){
                    int temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                    flag =true;
                }
            }
            if(!flag)break;
        }
    }

选择排序（不稳定）

思想：每一遍选出最小的数和前面的交换（注意：这里会改变相对位置）

复杂度：n^2

public void selectSort(int arr[], int n) {
        for (int i = 0; i < n - 1; i++) {
            int minIndex = i;
            for (int j = i + 1; j < n; j++) {
                if (arr[j] < arr[minIndex]) {
                    minIndex = j;
                }
            }
            if (minIndex != i) {
                int temp = arr[minIndex];
                arr[minIndex] = arr[i];
                arr[i] = temp;
            }
        }
    }

插入排序（稳定）

思想：每一个数和比自己之前大的数交换

复杂度：n^2

 public void insertSort(int[] arr, int n) {
        for (int i = 0; i < n - 1; i++) {
            for (int j = i + 1; j > 0; j--) {
                if (arr[j] < arr[j - 1]) {
                    int temp = arr[j];
                    arr[j] = arr[j - 1];
                    arr[j - 1] = temp;
                } else {
                    break;
                }
            }
        }
    }

希尔排序（不稳定）

思想：每次根据incre（初始为数组商都）/2，进行插入排序

复杂度：n^1.5

public void shellSort(int arr[],int length){
        int temp = 0;
        int incre = length;

        while(true){
            incre = incre /2;
            //对分组进行遍历
            for (int i=0;i<incre;i++){
                //插入排序
                for (int j=i+incre;j<length;j+=incre){
                    for (int k=j;k>i;k-=incre){
                        if(arr[k]<arr[k-incre]){
                            temp = arr[k];
                            arr[k] = arr[k-incre];
                            arr[k-incre] = temp;
                        }else{
                            break;
                        }
                    }
                }
            }
            //无法分组，表示排序结束
            if(incre == 1){
                break;
            }
        }
    }

堆排序（不稳定）

思想：构建小顶堆，取出最大值之后再构建小顶堆，循环

复杂度：nlogn

public static void MinHeap_Sort(int a[], int n) {
        int temp = 0;
        MakeMinHeap(a, n);

        for (int i = n - 1; i > 0; i--) {
            temp = a[0];
            a[0] = a[i];
            a[i] = temp;
            MinHeapFixdown(a, 0, i);
        }
    }

    //构建最小堆
    public static void MakeMinHeap(int a[], int n) {
        //从倒数第二层开始排序，取自己的孩子进行排序，这样所有的节点都排序到了
        for (int i = (n - 1) / 2; i >= 0; i--) {
            MinHeapFixdown(a, i, n);
        }
    }

    /**
     * 整理小顶堆，从i节点开始调整，从0开始计算，i节点的子节点为 2*i+1, 2*i+2
     *
     * @param a 所有节点
     * @param i 第i个节点
     * @param n 节点总数
     */
    public static void MinHeapFixdown(int a[], int i, int n) {

        int j = 2 * i + 1; //左节点
        int temp = 0;

        //j<n：如果左节点小于节点总数，表示该节点有节点，否则该节点是叶子节点是不需要调整的
        while (j < n) {
            //j+1<n：存在右节点，a[j+1]<a[j]：左右子节点中寻找最小的
            if (j + 1 < n && a[j + 1] < a[j]) {
                //将节点移到右节点
                j++;
            }

            //较大节点在下面
            if (a[i] <= a[j])
                break;

            //较大节点在上面，则将大节点下移
            temp = a[i];
            a[i] = a[j];
            a[j] = temp;

            //复位
            i = j;
            j = 2 * i + 1;
        }
    }

快速排序（不稳定）

思想：分治法，根据基数把左右部分分为有序的部分

复杂度：nlogn

public static void quicksort(int a[], int left, int right) {
        int i, j, t, temp;

        if (left > right)
            return;

        temp = a[left]; //存基准数
        i = left;
        j = right;

        while (i != j) {
            //先从右边开始找
            while (a[j] >= temp && i < j)
                j--;
            //再从左边开始找
            while (a[i] <= temp && i < j)
                i++;
            //交换两个数在数组中的位置
            if (i < j) {
                t = a[i];
                a[i] = a[j];
                a[j] = t;
            }
        }
        //基准数归位
        a[left] = a[i];
        a[i] = temp;

        quicksort(a, left, i - 1);//继续处理左边的
        quicksort(a, i + 1, right);//继续处理右边的
    }

归并排序（稳定）

思想：分治法，排好序然后合并，主要就是合并方法

复杂度：nlogn

 /**
     * 归并排序
     *
     * @param a
     * @param first
     * @param last
     * @param temp
     */
    public void merge_sort(int a[], int first, int last, int temp[]) {
        if (first < last) {
            int middle = (first + last) / 2;
            merge_sort(a, first, middle, temp);//左半部分排好序
            merge_sort(a, middle + 1, last, temp);//右半部分排好序
            mergeArray(a, first, middle, last, temp); //合并左右部分
        }
    }

    /**
     * 合并数组
     *
     * @param a
     * @param first
     * @param middle
     * @param end
     * @param temp
     */
    public void mergeArray(int a[], int first, int middle, int end, int temp[]) {
        int i = first;
        int m = middle;
        int j = middle + 1;
        int n = end;
        int k = 0;
        while (i <= m && j <= n) {
            //比较两个组的数
            if (a[i] <= a[j]) {
                temp[k] = a[i];
                k++;
                i++;
            } else {
                temp[k] = a[j];
                k++;
                j++;
            }
        }
        //左边一组中，当左边分组被取完时，该把右边分组全部取出来
        while (i <= m) {
            temp[k] = a[i];
            k++;
            i++;
        }

        //右边一组中，当左边分组被取完时，该把右边分组全部取出来
        while (j <= n) {
            temp[k] = a[j];
            k++;
            j++;
        }

        //在temp中取出所有排序好的数
        for (int ii = 0; ii < k; ii++) {
            a[first + ii] = temp[ii];
        }
    }

基数排序（稳定）

思想：桶排序的拓展排序

复杂度：d(n+r)

 /**
     * @param arr  原数组
     * @param temp 临时数组
     * @param n    序列的数字个数
     * @param k    最大的位数3
     * @param r    基数10
     * @param bin  桶中i位置存储的个数
     */
    public void radixSort(int arr[], int temp[], int n, int k, int r, int bin[]) {
        //digit:位数，个位、十位、百位等
        for (int i = 0, digit = 1; i < k; i++, digit = digit * r) {
            //初始化
            for (int j = 0; j < r; j++) {
                bin[j] = 0;
            }
            //计算每个箱子的数字个数
            for (int j = 0; j < n; j++) {
                bin[(arr[j] / digit) % r]++;
            }
            //bin[j]的个数修改为前j个箱子一共有几个数字
            for (int j = 1; j < r; j++) {
                bin[j] = bin[j - 1] + bin[j];
            }
            //取出每个
            for (int j = n - 1; j >= 0; j--) {      //重点理解
                bin[(arr[j] / digit) % r]--;
                temp[bin[(arr[j] / digit) % r]] = arr[j];
            }
            //将临时数组赋值给我们的数组
            for (int j = 0; j < n; j++) {
                arr[j] = temp[j];
            }
        }
    }

本文地址：https://blog.csdn.net/qq_35928566/article/details/111998129