常见的排序方法及其java实现

╰半夏微凉° 2023-02-20 10:57 20阅读 0赞

## 常见排序方法及其时间复杂度 ##

1. 冒泡排序     n^2
    2. 选择排序     n^2        （寻找局部最小数）
    3. 直接插入排序  n^2  （有序数组）
    4. 希尔排序   nlogn       （二分+直接插入+递归）
    5. 快速排序   nlogn        （最右基准，大放右，小左）
    6. 归并排序   nlogn     （拆分+合并）
    7. 基数排序    n+r,r为最大数最高位的位数   （按位数比较）
    8. 堆排序       nlogn   （平衡二叉树）
    9. 桶排序       n+r,(这里的r受桶的数量影响)  （范围+拆分比较）
    10. 计数排序    n+r，r为桶的数量   （范围+个数）

1、2、3、4、5、6、8属于比较排序，不受数据影响。（即数据可以是小数）  
7、9、10属于非比较排序，对数据规模和数据分布有一定的要求。

**场景分析**  
1.当输入规模比较小，推荐使用直接插入排序  
3.当输入规模比较大时  
对性能要求严苛：快速排序  
对空间有要求：堆排序  
对稳定性有要求（有大量重复的数）：归并排序  
如果数据都是范围类整形：计数排序

稳定，指的是一个序列中的相同值，它排序后，它的相同值的顺序不会改变。

常见排序的java代码实现

import java.util.ArrayList;
    import java.util.ListIterator;
    
    public class SortedUtils { 
    
    
        /** * 001冒泡排序 * 1000万的数据排序需要55小时 * 时间复杂度为 n^2 * @param arr * @return */
        public static int[] bubbleSort(int[] arr){ 
            int temp = 0;
            boolean flag = false; //表示是否已经按顺序排列好了
            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]){ 
                        temp = arr[j];
                        arr[j] = arr[j+1];
                        arr[j+1] = temp;
                        flag = true;
                    }
                }
                if (!flag){ 
                    break;
                }else { 
                    flag = false;
                }
            }
            return arr;
        }
    
        /** * 002选择排序 * 1000万的数据排序需要12个小时 * 时间复杂度为 n^2 * 原数组： 4 1 2 5 9 3 * 第一步：将最小的数放在位置1 * 第二步：将剩下最小的放位置2 * 依次类推 * * @param arr * @return */
        public static int[] selectSort(int[] arr){ 
            for (int i = 0; i < arr.length-1; i++) { 
                int minIndex = i; // 初始最小值下表（假定每一轮的第一个值为最小值）
                int min = arr[i]; // 初始最小值
                for (int j = i; j < arr.length-1; j++) { 
                    if (min > arr[j+1]){ 
                        minIndex = j+1; // 改变最小值索引
                        min = arr[j+1];
                    }
                }
                if (minIndex != i){  // 最小值已经改变，将最小值与第一个位置进行交换
                    arr[minIndex] = arr[i];
                    arr[i] = min;
                }
            }
            return arr;
        }
    
        /*** * 003直接插入排序 * 1000万的数据排序需要3.2个小时 * 时间复杂度为 n^2 * * 通过一个有序数组来存放 4 1 2 5 9 3 * 第一步：4 * 第二步：1 4 * 第三步：1 2 4 * .... * 第六步：1 2 3 3 5 9 * @param arr * @return */
        public static int[] insertSort(int[] arr){ 
            for (int i = 1; i < arr.length; i++) {  // 从一开始，前面的第一个数为有序数，后面的数与前面的有序数进行比较
                int insertValue = arr[i]; // 待插入的数
                int insertIndex = i - 1; // 待插入数前面一个数的索引
                while (insertIndex >= 0 && insertValue < arr[insertIndex]){ 
                    arr[insertIndex+1] = arr[insertIndex]; // 将比要插入数大的向后移动
                    insertIndex--; // 索引向前移动
                }
                arr[insertIndex+1] = insertValue; // 将要插入的数放在找到的位置
            }
            return arr;
        }
    
        /*** * 004 希尔排序 （是对直接插入排序的一种改进） * 1000万的数据排序需要3.067秒 * 时间复杂度为 nlogn (涉及二分法) * 第一步：将数据一分二 （0 2 4 一组 1 3 5 一组 间隔），分别对其进行直接排序 6/2=3 * 第二步：再次一分为二，在分别直接排序 3/2=1 * 第三步：进行微调 * * @param arr * @return */
        public int[] shellSort2(int[] arr){ 
            for (int gap = arr.length/2; gap >0 ; gap /= 2) {  // 每次步长减半
                for (int i = gap; i < arr.length; i++) {  // 从第gap个元素，逐个对其所在的组进行直接插入排序
                    int insertIndex = i;
                    int insertValue = arr[insertIndex];
                    while (insertIndex - gap >= 0 && insertValue < arr[insertIndex - gap]){ 
                        arr[insertIndex] = arr[insertIndex - gap];
                        insertIndex -= gap;
                    }
                    arr[insertIndex] = insertValue;
                }
            }
            return arr;
        }
    
        /*** * 005 快速排序 * 1000万的数据排序需要1.55秒 * 时间复杂度为 nlogn (涉及二分法) * 第一步：选择最右的数 作为基准 比它的放右边，比它小的放左边 * 第二步：左右两组数据 ，再次选择最右数为基准，进行比较 * 依次类推，知道左右两边的数组长度都为1 * * @param arr * @param left * @param right */
        public void quickSort(int[] arr, int left, int right){ 
            if (left >= right){ 
                return ;
            }
            int l = left;
            int r = right;
            int temp = arr[right];
            int t = 0;// 作为交换变量
            while (l < r){ 
                while (arr[l] <= temp && l < r){  // 从左边向右寻找大于等于temp的数
                    l++;
                }
                while (arr[r] >= temp && l < r){  // 从右向左寻找小于等于temp的数
                    r--;
                }
                if (l < r){  //交换
                    t = arr[l];
                    arr[l] = arr[r];
                    arr[r] = t;
                }
            }
            arr[right] = arr[l];
            arr[l] = temp;
            quickSort(arr, left, r-1);//向左递归
            quickSort(arr, l+1, right);// 向右递归
        }
    
    
        /*** * 006 归并排序 * 1000万的数据排序需要1.75秒 * 时间复杂度为 nlogn (涉及二分法) * 第一步：将数组不断拆分，知道每个数组大小都为2,比较大小 * 第二步：将拆分后的数组两两合并并比较大小 * 依次类推，直到所有的数组都合并 * * @param arr * @param left * @param right */
        public void mergeSort(int[] arr, int[] temp, int left, int right){ 
            if (left < right){ 
                int mid = (left + right) / 2;
                // 向左递归分解
                mergeSort(arr, temp, left, mid);
                // 向右递归分解
                mergeSort(arr, temp, mid + 1, right);
                merge(arr, temp, left, right, mid);
            }
        }
    
        public void merge(int[] arr, int[] temp, int left, int right, int mid){ 
            int i = left;
            int j = mid + 1;
            int t = 0;
            // 1.比较两个两部分每一个的大小，知道有一部分数据全部加入temp
            while (i <= mid && j <= right){ 
                if (arr[i] < arr[j]){ 
                    temp[t] = arr[i];
                    i++;
                }else { 
                    temp[t] = arr[j];
                    j++;
                }
                t++;
            }
            // 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++;
            }
        }
    
        /** * 007 基数排序 * 1000万的数据排序需要0.695秒 * 时间复杂度为 n+r (r为是最高位的位数) * 第一步：根据个位排序 * 第二步：根据十位排序 * 依次类推，直到根据最大位进行排序 * * @param arr */
        public 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();//最大值的长度
            // 初始化一个二维数据，二维数组的没一个数组都是一个桶，因为无法确定每一个桶会装多少个数据，所以设置为arr.lenth
            int[][] bucket = new int[10][arr.length];
            // 初始化一个一维数组用于保存桶保存的数的个数
            int [] bucketElementCounts = new int[10];
            for (int i = 0, n = 1; i < maxLength; i++, n *= 10) {  // i控制循环次数，n控制每次取得的位数
                for (int j = 0; j < arr.length; j++) {  // 循环每个数，按照规则放入桶内
                    int digitalOfElement = arr[j] / n % 10; // 每次取模得到相应位数的值
                    bucket[digitalOfElement][bucketElementCounts[digitalOfElement]] = arr[j];
                    bucketElementCounts[digitalOfElement]++;
                }
                int index = 0;//存放数据的索引
                for (int k = 0; k < bucket.length; k++) {  // 循环所有桶
                    if (bucketElementCounts[k] != 0){  // 不为空的桶
                        for (int m = 0; m < bucketElementCounts[k]; m++) {  // 将桶的元素放入数组
                            arr[index++] = bucket[k][m];
                        }
                    }
                    bucketElementCounts[k] = 0;//清空桶
                }
            }
        }
    
    
        /** * 008 堆排序 * 1000万的数据排序需要2.695秒 * 时间复杂度为 nlogn * * @param arr */
        public void heapSort(int[] arr){ 
            int temp = 0;
            // 第一次调整：将最大是数调整为根节点
            // arr.length/2 - 1 :为第一个非叶子节点
            for (int i = arr.length/2 - 1; i >= 0; i--) { 
                adjustHeap(arr, i, arr.length);
            }
    
            for (int i = arr.length-1 ; i > 0; i--) { 
                temp = arr[i];
                arr[i] = arr[0];
                arr[0] = temp;
                // 为什么这里的的第二个参数写死是0 ？
                // 因为经过第一次调整之后，再经过交换，就只有很根节点不是一个大顶堆，
                // 所以只需要进行简单的与根节点交换就好，而不需要在进行整体的一个大顶堆的构造
                adjustHeap(arr, 0, i);
            }
        }
        public void adjustHeap(int[] arr, int i, int length){ 
            int temp = arr[i];
            // k = i * 2 + 1：表示i这个节点的左子树
            for (int k = i * 2 + 1; k < arr.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指向调整后的子节点，用于循环结束后交换数据
                }else { 
                    break;
                }
            }
            arr[i] = temp;//交换数据第二步
        }
    
    
    
        /** * 009 桶排序 * 1000万的数据排序需要16小时 * 时间复杂度为 O(N+N*logN-N*logM) 桶范围越大时间复杂度越大 * 假设数据是均匀分布的 把0—100放在数组A 把 100-200放数组B 分别对其排序 * @param arr */
        public void bucketSort(int[] arr){ 
            int min = arr[0];
            int max = arr[0];
            for (int i = 0; i < arr.length; i++) {  // 找出最大值与最小值
                min = Math.min(min,arr[i]);
                max = Math.max(max,arr[i]);
            }
            int bucketNumber = (max - min)/arr.length + 1; // 桶的数量
            ArrayList<ArrayList<Integer>> buckets = new ArrayList<>(); // 存储每一个桶
            ArrayList<Integer> bucket = null;
            for (int i = 0; i < bucketNumber; i++) {  // 将没一个桶放入buckets中
                bucket = new ArrayList<Integer>();
                buckets.add(bucket);
            }
    
            for (int item : arr) {  // 循环数据插入到桶
                ArrayList<Integer> bc = buckets.get((item - min) / arr.length); // (item - min) / arr.length 表示桶的位置
                insert(bc, item); // 插入桶（桶内排序）
            }
    
            int index = 0; // 索引数组
            for (ArrayList<Integer> bc : buckets) {  // 循环每一个桶
                for (Integer item : bc) {  // 循环桶内的数据
                    arr[index++] = item; // 依次将桶内的数据取出
                }
            }
        }
    
        public void insert(ArrayList<Integer> bc, int item){ 
            ListIterator<Integer> itl = bc.listIterator();
            boolean flag = true;
            while (itl.hasNext()){ 
                if (item <= itl.next()){ 
                    itl.previous(); // 将迭代器的位置偏移到上一位
                    itl.add(item); // 将数据插入到迭代器当前的位置上
                    flag = false;
                    break;
                }
            }
            if (flag){  // 否在九八数据插插入到末端
                bc.add(item);
            }
        }
    
    
        /** * 010 计数排序 （在确定都是整数的情况下 一个数一个桶 ） * 1000万的数据排序需要0.241秒 * 时间复杂度为 n+k(k为桶的个数) * 假设数据是均匀分布的 把0—100放在数组A 把 100-200放数组B 分别对其排序 * @param arr */
        public void countSort(int[] arr){ 
            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[] counts = new int[max - min + 1];// 计数空间
    
            for (int i = 0; i < arr.length; i++) {  // 将每一个数减去最小值统计到临时数组中
                counts[arr[i] - min] += 1; // arr[i]-min对应计数空间的下表
            }
            for (int i = 0,index =0; i < counts.length; i++) { 
                int item = counts[i];//每一个数对应的统计量
                while (item-- != 0){  // 直到每一个数的统计量归零
                    arr[index++] = i + min; // 将原来的数展开放到原数组中，展开就是按照大小排列
                }
            }
        }
    
    
    
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MDk5MDgxOA_size_16_color_FFFFFF_t_70_pic_center]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MDk5MDgxOA_size_16_color_FFFFFF_t_70_pic_center]: https://img-blog.csdnimg.cn/20200812232338145.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MDk5MDgxOA==,size_16,color_FFFFFF,t_70#pic_center