一文带你秒懂十大排序(下)

简介: 一文带你秒懂十大排序

一文带你秒懂十大排序(上):https://developer.aliyun.com/article/1521563

2、快速排序

算法思想:在待排序的序列中选择一个基准,按照基准将元素分成左右两个子序列,使得左边的子序列的元素都小于基准元素,使得右边的子序列都大于基准元素,对左右子序列继续重复上述步骤,使得每个子序列的长度为1为止。

动图演示:

代码实现:

public static void quickSort(int[] array){
        
        quick(array,0,array.length - 1);
    }
    public static void quick(int[] array,int left,int right){
        if(left >= right){
            return;
        }
        int part = partition(array,left,right);
        quick(array,left,part -1);
        quick(array,part + 1,right);
    }
    public static int partition(int[] array,int start,int end){
        int temp=array[start];
        while(start < end){
            while(start < end && array[end] >= temp){
                end--;
            }
            array[start] = array[end];
            while (start < end && array[start] <= temp){
                start++;
            }
            array[end] = array[start];
        }
        array[start] = temp;
        return start;
    }

性能分析:

  • 时间复杂度:O(nlog2 n)。
  • 空间复杂度:O(log2 n)。
  • 稳定性:稳定。

上述快速排序的时间复杂度是在最好情况下的,最坏情况下整个待排序元素是顺序或是逆序的,时间复杂度高达O(n^2),并且当数据量很大的时候,空间复杂度也是很大的,可能会出现栈溢出,所以需要进行优化:


每次选择基准元素时采用三数取中法,就是将right坐标、left坐标的值和mid中间值约束,以确保每次的基准元素不是最大值或最小值,还有当子序列长度不太大时,可以使用直接插入排序来提高效率。  

public static void quickSort(int[] array){
        quick(array,0,array.length - 1);
    }
    public static void quick(int[] array,int left,int right){
        if(left >= right){
            return;
        }
        if(right-left <=15){
            insertSort(array,left,right);
            return;
        }
        int index = midThree(array,left,right);
        int temp = array[index];
        array[index] = array[left];
        array[left] = temp;
        int part = partition(array,left,right);
        quick(array,left,part -1);
        quick(array,part + 1,right);
    }
    public static int partition(int[] array,int start,int end){
        int temp=array[start];
        while(start < end){
            while(start < end && array[end] >= temp){
                end--;
            }
            array[start] = array[end];
            while (start < end && array[start] <= temp){
                start++;
            }
            array[end] = array[start];
        }
        array[start] = temp;
        return start;
    }
    public static void insertSort(int[] array,int left,int right){
        for(int i = left+1;i <= right;i++){
            int temp = array[i];
            int j = i-1;
            for(;j >=left;j--){
                if(array[j] > temp){
                    array[j+1] = array[j];
                }else{
                    break;
                }
            }
            array[j+1] = temp;
        }
    }
    public static  int midThree(int[] array,int left,int right){
        int mid=(left+right) / 2;
        if(array[left] < array[right]){
            if(array[mid] > array[left]){
                return mid;
            }else{
                return left;
            }
        }else{
            if(array[mid] > array[right]){
                return mid;
            }else{
                return right;
            }
        }
    }

快速排序也可以非递归实现: 利用栈将每次划分的左右子序列的下标入栈,只要栈不为空,每次弹出两个元素,作为调整区间的下标。直到子序列只有一个元素的时候就停止入栈。

代码实现:

public static void quickSort2(int[] array){
        Deque<Integer> stack = new LinkedList<>();
        int left=0;
        int right=array.length-1;
        stack.push(left);
        stack.push(right);
        while (!stack.isEmpty()){
            right=stack.pop();
            left=stack.pop();
            int part=partition(array,left,right);
            if(part > left+1){
                stack.push(left);
                stack.push(part-1);
            }
            if(part < right-1){
                stack.push(part+1);
                stack.push(right);
            }
 
        }
    }

四、归并排序

算法思想:采用的是分治法的思想,先把待排序的序列分解成若干个子序列,先让子序列有序,然后将有序的子序列合并是整个待排序的序列。

动图演示:

代码实现:

public static void mergeSort(int[] array){
        divideMerge(array,0,array.length-1);
    }
    public static void divideMerge(int[] array,int left,int right){
        if(left >= right){
            return;
        }
        int mid=(left+right) / 2;
        divideMerge(array,left,mid);
        divideMerge(array,mid+1,right);
        merge(array,left,right,mid);
    }
    public static void merge(int[] array,int left,int right,int mid){
        int s1=left;
        int s2=mid+1;
        int[] nums=new int[right-left+1];
        int k=0;
        while(s1 <= mid && s2 <= right){
            if(array[s1]<array[s2]){
                nums[k++] = array[s1++];
            }else{
                nums[k++] = array[s2++];
            }
        }
        while(s1 <= mid){
            nums[k++] = array[s1++];
        }
        while (s2 <= right){
            nums[k++] = array[s2++];
        }
        for(int i=0;i< k;i++){
            array[i+left]=nums[i];
        }
    }


性能分析:

  • 时间复杂度:O(nlog2 n)。
  • 空间复杂度:O(n)。
  • 稳定性:稳定 。

同样,归并排序也可以进行非递归实现。

 public static void mergeSort2(int[] array) {
        int gap = 1;
        while (gap < array.length) {
            for (int i = 0; i < array.length; i = i + gap * 2) {
                int left = i;
                int mid = left + gap - 1;
                if (mid >= array.length) {
                    mid = array.length - 1;
                }
                int right = mid + gap;
                if (right >= array.length) {
                    right = array.length - 1;
                }
                merge(array, left, right, mid);
            }
            gap *= 2;
        }
    }

海量数据的排序问题:

外部排序:排序过程需要在磁盘等外部存储进行的排序

前提:内存只有 1G ,需要排序的数据有 100G

解决方案:因为待排序的数据有100G而内存只有1G,那么就可以将待排序的数据等分为200份,每份数据大小为512M,然后将每份数据存入内存中排好序,然后对这200份数据在内存外进行再进行归并排序即可。


五、计数排序

算法思想:利用鸽巢原理,开辟一段较大的空间的数组,数组中默认元素为0,将待排序的元素对应到下标所对应的元素值加一,计数排序主要应用于待排序的序列在某个范围内。

动图演示:

代码实现:

public static void countingSort(int[] array){
        int min = array[0];
        int max = array[0];
        for(int i = 1;i < array.length;i++){
            if(array[i] < min){
                min = array[i];
            }
            if(array[i] > max){
                max = array[i];
            }
        }
        int[] nums = new int[max-min+1];
        for(int i = 0;i < array.length;i++){
            nums[array[i]-min]++;
        }
        int k=0;
        for(int i = 0;i < nums.length;i++){
            while(nums[i] != 0){
                array[k++] = min+i;
                nums[i]--;
            }
        }
    }

性能分析:

  • 时间复杂度:O(max(n,数组范围))。
  • 空间复杂度:O(数组范围)。
  • 稳定性:稳定。

六、基数排序

算法思想:基数排序是对数字的每一位进行排序的,最大数字的位数决定了排列的次数,每次先排列,然后再收集,重复上述步骤,直到最高位排序完成。

动图演示:

代码实现:

 //基数排序
    public static void baseSort(int[] array){
        int max = array[0];
        for(int i = 1;i < array.length;i++){
            if(array[i] > max){
                max = array[i];
            }
        }
        int count=countByte(max);
        LinkedList<LinkedList<Integer>> lists = new LinkedList<>();
        for(int i = 0;i < 10;i++){
            lists.add(new LinkedList<>());
        }
        int k=1;
        while(k <= count){
            for(int i = 0;i < array.length;i++){
                int num = getByteNum(array[i],k);
                lists.get(num).add(array[i]);
            }
            int j = 0;
            for(int i = 0;i < lists.size();i++){
                while(!lists.get(i).isEmpty()){
                    array[j++] =lists.get(i).poll();
                }
            }
            k++;
 
        }
    }
    //计算出数字的位数
    public static int countByte(int num){
        int count = 0;
        while(num != 0){
            num=num/10;
            count++;
        }
        return count;
    }
    //获取到指定位的数字
    public static int getByteNum(int num,int index){
        String s = String.valueOf(num);
        if(index <= s.length()){
            return (int)(s.charAt(s.length() - index) - '0');
        }
        return 0;
 
    }

性能分析:

  • 时间复杂度:O(n*k)。
  • 空间复杂度:O(n+k)。
  • 稳定性: 稳定。

七、桶排序

算法思想:将待排序的序列划分为多个范围大小相同的区间,将元素分别放入到对应的区间,对每个子区间进行排序,最后整个序列变得有序。

动图演示:

代码实现:

public static void bucketSort(int[] array){
        int min = array[0];
        int max = array[0];
        for(int i = 1;i < array.length;i++){
            if(array[i] < min){
                min = array[i];
            }
            if(array[i] > max){
                max = array[i];
            }
        }
        int size = (max-min) / array.length + 1;
        LinkedList<LinkedList<Integer>> lists = new LinkedList<>();
        for(int i = 0;i < size;i++){
            lists.add(new LinkedList<>());
        }
        for(int i = 0;i < array.length;i++){
            int num = (array[i] - min) / size;
            lists.get(num).add(array[i]);
        }
        int k=0;
        for(int i = 0;i < size;i++){
            lists.get(i).sort(new Comparator<Integer>() {
                @Override
                public int compare(Integer o1, Integer o2) {
                    return o1-o2;
                }
            });
            while(!lists.get(i).isEmpty()){
                array[k++]=lists.get(i).poll();
            }
        }
    }

性能分析

  • 时间复杂度:O(n+k)。
  • 空间复杂度:O(n+k)。
  • 稳定性:稳定。

八、排序总结

算法名称 时间复杂度 空间复杂度 稳定性
直接插入排序 O(n^2) O(1) 稳定
希尔排序 O(n^1.3) O(1) 不稳定
直接选择排序 O(n^2) O(1) 不稳定
堆排序 O(nlog2 n) O(1) 不稳定
冒泡排序 O(n^2) O(1) 稳定
快速排序

O(nlog2 n)

O(log2 n) 不稳定
归并排序 O(nlog2 n) O(n) 稳定
计数排序

O(max(n,数组范围))

O(数组范围) 稳定
基数排序

O(n*k)

O(n+k) 不稳定
桶排序 O(n+k) O(n+k) 稳定

注意点:

序列基本有序时,快排退化成冒泡排序,直接插入排序最快。

各排序算法中,最坏情况下时间复杂度最低的是堆排序。

初始数据集的排列顺序对算法的性能无影响的有堆排序、归并排序、选择排序。

目录
相关文章
十大排序引出的问题()
十大排序引出的问题()
34 0
|
7月前
|
算法 搜索推荐 测试技术
一文带你秒懂十大排序(上)
一文带你秒懂十大排序
36 0
|
7月前
|
搜索推荐 算法
Sort-00-十大排序算法汇总
这是一个关于排序算法的系列文章总结,包括冒泡、选择、插入、归并、快速、堆、希尔、计数、桶和基数排序的详细讲解。十大排序算法各有特点,如冒泡排序适合小规模或基本有序的数据,快速排序在大规模随机数据中表现优秀。时间复杂度和空间复杂度各不相同,选择时需根据数据特性与应用场景权衡。
|
7月前
|
存储 搜索推荐 算法
十大基础排序算法
十大基础排序算法
|
7月前
|
搜索推荐 算法
【十大排序】带你深入了解归并排序
【十大排序】带你深入了解归并排序
|
7月前
|
算法 搜索推荐 程序员
【十大排序】带你深入分析快速排序
【十大排序】带你深入分析快速排序
|
7月前
|
算法
【十大排序】深入浅出冒泡排序
【十大排序】深入浅出冒泡排序
|
存储 移动开发 算法
十大排序算法
十大排序算法
134 0
|
存储 搜索推荐 算法
理解实现八大排序(二)
理解实现八大排序
53 0
|
算法 搜索推荐 C++
理解实现八大排序(一)
理解实现八大排序
77 0