一文带你秒懂十大排序（下）-阿里云开发者社区

一文带你秒懂十大排序（上）：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)	稳定

注意点：

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

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

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

一文带你秒懂十大排序（下）

2、快速排序

四、归并排序

五、计数排序

六、基数排序

七、桶排序

八、排序总结

热门文章

最新文章

相关电子书