欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

真的用不上,排序算法

程序员文章站 2022-03-19 15:59:20
真的用不上,排序算法冒泡排序(稳定)思想:每一遍将最大的数下沉复杂度: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]

真的用不上,排序算法

冒泡排序(稳定)

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

复杂度: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