Common Sort - 常见的几种排序 与 不常见的几种排序 - Java - 细节狂魔

2年前 (2022) 程序员胖胖胖虎阿
278 0 0

文章目录

  • 排序
    • 概念
    • 稳定性(重要)
    • 应用 - 举例
      • 1.、各大商城的价格从低到高等
      • 2、中国大学排名
  • 常见的排序算法(8 种)- 总览
  • 直接插入排序
    • 模拟实现 - 插入排序
      • 稳定性分析
      • 结论
  • 希尔排序
    • 思考
    • 原理
      • 科学家的分组思维
    • 模拟实现 - 希尔排序
    • 总结
  • 选择排序
    • 直接选择排序 - 原理
    • 优化
    • 代码如下
      • 附图
  • 双向选择排序 (了解)
    • 代码如下
  • 堆排序
    • 代码
  • 冒泡排序
    • 代码如下 - 未优化
    • 代码优化思维
      • 代码如下 - 优化
    • 未优化 和 优化代码 运行速度比较
  • 快速排序 - 重点
    • 原理
    • 总结
    • 程序框架
    • 完善 partition 部分
      • 代码细节部分
    • 总程序 - 未优化
    • 快速排序 的 时间 与 空间复杂度分析
    • 堆排序 与 快排 的区别
    • 细节拓展
      • if语句中 比较大小的代码中 等号是不能省略的
      • 目前版本的 快排代码 不支持 大量数据进行排序 - 会导致栈溢出。
    • 基准值的选择 - 优化前的知识补充
    • 快速排序(几数取中法 优化)
      • 优化总结
    • 拓展 快速排序 - 非递归实现
      • 非递归实现快速排序的思维
      • 代码如下
  • 归并排序 - 重点
    • 知识铺垫 : 二路合并
      • 二路合并的代码如下
    • 归并排序 - 原理
    • 难点1 - 如何将一个数组拆分成一个个单独数组【每个数组里只包含一个元素】。
    • 难点2 - 合并
      • 归并排序的程序框架
      • 合并程序的完善
        • 附图
    • 归并排序 - 总程序
    • 归并排序 - 时间与空间复杂度分析、稳定性
    • 归并排序 - 非递归实现
      • 代码如下
    • 海量数据的排序问题
  • 小总结
  • 排序总结
  • 不常见的排序 - 不基于比较的排序(了解)
    • 基数排序
    • 代码如下
    • 捅排序
    • 计数排序
      • 代码如下
      • 附图 - 是目前的计数排序稳定
  • 本文结束

排序

概念

排序,就是使一串记录,按照其中的某个 或 某些关键字的大小,递增 或 递减 的 排列起来的操作。
平时的上下文中,如果提到排序,通常指的是 排升序(非降序)。
通常意义上的排序,都是指的原地排序(in place sort)
原地排序:就是指在排序过程中不申请多余的存储空间,只利用原来存储待排数据的存储空间进行比较和交换的数据排序。


稳定性(重要)

两个相等的数据,如果经过排序后,排序算法能保证其相对位置不发生变化,则我们称该算法是具备稳定性的排序算法。
Common Sort - 常见的几种排序 与 不常见的几种排序 - Java - 细节狂魔


应用 - 举例

1.、各大商城的价格从低到高等

Common Sort - 常见的几种排序 与 不常见的几种排序 - Java - 细节狂魔


2、中国大学排名

Common Sort - 常见的几种排序 与 不常见的几种排序 - Java - 细节狂魔


常见的排序算法(8 种)- 总览

Common Sort - 常见的几种排序 与 不常见的几种排序 - Java - 细节狂魔


直接插入排序

插入排序:非常简单!仅次于冒泡排序。
Common Sort - 常见的几种排序 与 不常见的几种排序 - Java - 细节狂魔
根据这个思维:第一个数据是有序的,也就是说:在我们遍历的时候,是从下标1 开始的。
具体的操作见下图:
Common Sort - 常见的几种排序 与 不常见的几种排序 - Java - 细节狂魔


模拟实现 - 插入排序

import java.util.Arrays;

public class DirectInsertionSort {
    /*
    * 时间复杂度: O(N^2)
    * 最好情况: O(N) 数组有序的情况
    * 空间复杂度:O(1)  只有 一个 tmp 变量是常驻的
    * 稳定性:稳定
    * */
    public static void insertionSort(int[] array){
        for(int i = 1;i < array.length;i++){
            int tmp = array[i];
            int j = i - 1;
            for( ; j >= 0;j-- ){
            // 前移
                if(tmp < array[j]){
                    array[j + 1] = array[j];
                }else{
                    break;
                }
            }
            // 插入【无论是找到了合适插入的位置,还是不存在比 tmp更小的值,j自减到 -1.执行的代码都是一样的】
            array[j+1] = tmp;
        }
    }

    public static void main(String[] args) {
        int[] array = {23,45,56,68,8,9};
        insertionSort(array);
        System.out.println(Arrays.toString(array));
    }

}

Common Sort - 常见的几种排序 与 不常见的几种排序 - Java - 细节狂魔


稳定性分析

Common Sort - 常见的几种排序 与 不常见的几种排序 - Java - 细节狂魔


结论

一个稳定的排序,可以实现为 不稳定的排序。
但是,一个本身就不稳定的排序是 无法变成 稳定的排序。
直接插入排序 是 有序的。
它的时间复杂度是 O(N^2);最好情况:O(N【数组有序】
也就是说:对于直接插入排序,数据越有序越快!
由此,不难联想到:直接插入排序 有时候 会用于 优化 排序。
【假设:假设我们有一百万个数据需要排序,在排序的过程中,区间越来越小,数据越来越有序。直接插入排序的时间复杂度为 O(N),N 越来越小,那么,使用 直接插入排序是不是越来越快!也就是说:直接插入排序 有时候会 用于 排序优化】
直接插入排序经常使用在 数据量不多,且整体数据趋于有序的。

import java.util.Random;

public class DirectInsertionSort {
    /*
    * 时间复杂度: O(N^2)
    * 空间复杂度:O(1)  只有 一个 tmp 变量是常驻的
    * 稳定性:稳定
    * */
    public static void insertionSort(int[] array){
        for(int i = 1;i < array.length;i++){
            int tmp = array[i];
            int j = i - 1;
            for( ; j >= 0;j-- ){
                if(tmp < array[j]){
                    array[j + 1] = array[j];
                }else{
                    break;
                }
            }
            array[j+1] = tmp;
        }
    }
    // 有序
    public static void test1(int capacity){
        int[] array = new int[capacity];
        for (int i = 0; i < capacity; i++) {
            array[i] = i;
        }
        // 记录开始排序开始时间
        long start = System.currentTimeMillis();
        insertionSort(array);
         // 记录开始排序结束时间
        long end = System.currentTimeMillis();
         // 输出 整个排序过程的时间
        System.out.println(end - start);
    }
    // 无序
    public static void test2(int capacity){
        int[] array = new int[capacity];
        Random random = new Random();
        for (int i = 0; i < capacity; i++) {
            array[i] = random.nextInt(capacity);
        }
        // 记录开始排序开始时间
        long start = System.currentTimeMillis();
        insertionSort(array);
         // 记录开始排序结束时间
        long end = System.currentTimeMillis();
         // 输出 整个排序过程的时间
        System.out.println(end - start);
    }


    public static void main(String[] args) {
        test1(10000);
        test2(10000);
    }
}

Common Sort - 常见的几种排序 与 不常见的几种排序 - Java - 细节狂魔


希尔排序

思考

假设,现有 1 00 00 个 数据,如果对着组数据进行排序,使用插入排序。
时间复杂度为 O(N^2)【最坏情况:逆序的情况】
故 1 00 00 * 1 00 00 == 1 亿(量化)
它不是 1 万个数据嘛。那么,我们可以不可以这么去想:将这 一万个数据拆分成 100 组【每组100个数据】,对其中一组进行直接插入排序的时间复杂度为 100*100 ==1 00 00(量化),这样的分组还有99个,也就是将这一百组使用直接插入排序的时间复杂度为 1 00 00 * 1 00 = 1 百万(量化)。
有没有发现,分组过后,时间复杂度效率 提高很多,由1亿 变成了 1百万。
也就是说:如果采用分组的思想,我们会发现 时间复杂度会有一个很大的改变。
而这种分组的思想 就是 希尔排序。

原理

希尔排序又称缩小增量法。希尔排序法的基本思想是:先选定一个整数 n,把待排序文件中所有数据分成 n 组,所有距离为 数据量 / n 的 分在同一组。并且对每一组内的数据进行排序。然后,重复上述 分组 和 排序工作。当分组的组数为 1 是,所有数据 在进行 一个排序。
Common Sort - 常见的几种排序 与 不常见的几种排序 - Java - 细节狂魔
1、希尔排序 是对直接插入排序的优化。
2、当 group > 1 时都是预排序,目的是让数组更接近于有序。当 group == 1时,数组已经接近有序了,这样就会更快。对于整体而言,可以达到优化的效果。
那么,问题来了!我们怎去确定分多少组,而且越分越少。
【取自清华大学出版的一本书《数据结构》】
Common Sort - 常见的几种排序 与 不常见的几种排序 - Java - 细节狂魔


科学家的分组思维


Common Sort - 常见的几种排序 与 不常见的几种排序 - Java - 细节狂魔
现在这组数据,我们相当于只排序了一组数据,就走人了。数组整体还不是有序的。那么,我们该怎么解决这个问题?往下看!
Common Sort - 常见的几种排序 与 不常见的几种排序 - Java - 细节狂魔


模拟实现 - 希尔排序

import java.util.Arrays;

public class ShellSort {
    /*
    * 时间复杂度和增量有关系,所以无法得出准确的时间复杂度
    * 但只需要记住:在一定的范围里,希尔排序的时间复杂度为 O(N^1.3 ~ N^1.5)
    * 空间复杂度为 O(1)
    * 稳定性:不稳定
    * 判断稳定性的技巧:如果在比较的过程中 发生了 跳跃式交换。那么,就是不稳定的排序。
    * */
    public static void shell(int[] array,int group){
        for (int i = group; i < array.length; i += 1) {
            int tmp = array[i];
            int j = i-group;
            for (; j >= 0; j-=group) {
                if(tmp < array[j]){
                    array[j+group] = array[j];
                }else{
                    break;
                }
            }
            array[j+group] = tmp;
        }
    }
    public static void shellSort(int[] array){
        int group = array.length;
        // 预排序
        while(group > 1){
            // 第一次分组委 数组的长度,即 头尾判断。
            // 其后,每次分组个数,缩小一倍。
            shell(array,group);
            group /= 2;
        }
        // 最后调整
        shell(array,1);
    }

    public static void main(String[] args) {
        int[] array ={12,5,9,34,6,8,33,56,89,0,7,4,22,55,77};
        shellSort(array);
        System.out.println(Arrays.toString(array));
    }
}

Common Sort - 常见的几种排序 与 不常见的几种排序 - Java - 细节狂魔


总结

其实 希尔排序就是一个直接插入排序。


选择排序

直接选择排序 - 原理

Common Sort - 常见的几种排序 与 不常见的几种排序 - Java - 细节狂魔


优化

定义 一个 变量, 用来记录 此时的 i 后面最小值的下标。等 j 遍历完了,最小值的下标也就拿到了。此时,再进行交换。
这样就不必让上面那样,遇到比 i下标元素 小的,就交换。


代码如下

import java.util.Arrays;

public class SelectSort {
    /*
    * 稳定性: 不稳定 见附图
    * 时间复杂度:O(N^2) 》》 外层循环 n -1,内层循环 n -1
    * 空间复杂度:O(1)
    * */
    public static void selectSort(int[] array){
        for (int i = 0; i < array.length-1; i++) {
            int index = i;
            for (int j = i + 1; j < array.length; j++) {
                if(array[index] > array[j]){
                    index = j;
                }
            }
            int tmp = array[i];
            array[i] = array[index];
            array[index] = tmp;
        }
    }

    public static void main(String[] args) {
        int[] array = {12,6,10,3,5};
        selectSort(array);
        System.out.println(Arrays.toString(array));
    }
}

Common Sort - 常见的几种排序 与 不常见的几种排序 - Java - 细节狂魔

附图

Common Sort - 常见的几种排序 与 不常见的几种排序 - Java - 细节狂魔


双向选择排序 (了解)

每一次从无序区间选出最小 + 最大的元素,存放在无序区间的最前和最后,直到全部待排序的数据元素排完 。
Common Sort - 常见的几种排序 与 不常见的几种排序 - Java - 细节狂魔


代码如下

import java.util.Arrays;

public class SelectSortOP {
    public static void selectSortOP(int[] array){
        int low = 0;
        int high = array.length - 1;
        // [low,high] 表示整个无序区间
        while(low < high){
            int min = low;
            int max = low;
            for (int i = low+1; i <= high; i++) {
                if(array[i] < array[min]){
                    min = i;
                }
                if(array[i] > array[max]){
                    max = i;
                }
            }
            swap(array,min,low);
            if(max == low){
                max = min;
            }
            swap(array,max,high);
            low++;
            high--;
        }

    }
    public static void swap(int[] array,int x,int y){
        int tmp = array[x];
        array[x] = array[y];
        array[y] = tmp;
    }

    public static void main(String[] args) {
        int[] array = {9, 5, 2, 7, 3, 6, 8 };
        selectSortOP(array);
        System.out.println(Arrays.toString(array));
    }
}

Common Sort - 常见的几种排序 与 不常见的几种排序 - Java - 细节狂魔


堆排序

基本原理也是选择排序,只是不在使用遍历的方式查找无序区间的最大的数,而是通过堆来选择无序区间的最大的数。
注意: 排升序要建大堆;排降序要建小堆.
这个我就不讲,因为我在 堆/优先级中讲的很清楚!
有兴趣的,可以点击 链接关键字 ,跳转到该文章,该内容在 文章目录最后面。
这里我们就直接上代码。
Common Sort - 常见的几种排序 与 不常见的几种排序 - Java - 细节狂魔


代码

import java.util.Arrays;

public class HeapSort {
    public static void main(String[] args) {
        int[] array = {12,8,5,4,10,15};
        creationHeap(array);// 建堆的时间复杂度:O(N)
        System.out.println(Arrays.toString(array));
        heapSort(array);// 堆排序的时间复杂度:O(N * log2 N)
        // 空间复杂度:O(1)
        System.out.println(Arrays.toString(array));
    }
    // 创建一个大根堆
    public static void creationHeap(int[] array){
        for (int parent = (array.length-1-1)/2; parent >= 0; parent--) {
            shiftDown(array,parent,array.length);
        }
    }
    public static void heapSort(int[] array){
        /*
        * 时间复杂度:O(N * log2 N)
        * 空间复杂度:O(1)
        * 稳定性:不稳定
        * */
        int end = array.length - 1;
        while(end>0){
            int tmp = array[end];
            array[end] = array[0];
            array[0] = tmp;
            shiftDown(array,0,end);
            end--;
        }
    }
    // 向下调整
    public static void shiftDown(int[] array,int parent,int len){
        int child = parent * 2 + 1;// 做孩纸
        while(child < len){
            // 获取左右子树最大值的下标
            if(child+1 < len && (array[child] < array[child+1])){
                child++;
            }
            if(array[child] > array[parent]){
                int tmp = array[child];
                array[child] = array[parent];
                array[parent] = tmp;
                parent = child;
                child = parent * 2 + 1;
            }else{
                break;
            }
        }
    }
}

Common Sort - 常见的几种排序 与 不常见的几种排序 - Java - 细节狂魔


冒泡排序

Common Sort - 常见的几种排序 与 不常见的几种排序 - Java - 细节狂魔


代码如下 - 未优化

import java.util.Arrays;
    /*
     * 时间复杂度:O(N^2) 【无论是最好情况,还是最坏情况,时间复杂度都不变】
     * 空间复杂度:O(1)
     * 稳定性:稳定【未发生跳跃式交换】
     * */
public class BubbleSort {
    public static void bubbleSort(int[] array){
        // 比较的趟数 = 数组的长度 - 1 【 0 ~ 3 一共 4趟】
        for (int i = 0; i < array.length-1; i++) {
            // 比较完一趟后,可以比较的元素个数减一。【因为靠后的数据已经有序】
            // 内循环中,之所以要减一个 1,是因为防止 下面的if语句 发生 数组越界异常
            for(int j = 0;j< array.length-1-i;j++){
                if(array[j] > array[j+1]){
                    int tmp = array[j];
                    array[j] = array[j+1];
                    array[j+1] = tmp;
                }
            }
        }
    }

    public static void main(String[] args) {
        int[] array = {12,6,10,3,5};
        bubbleSort(array);
        System.out.println(Arrays.toString(array));
    }
}

Common Sort - 常见的几种排序 与 不常见的几种排序 - Java - 细节狂魔


代码优化思维

Common Sort - 常见的几种排序 与 不常见的几种排序 - Java - 细节狂魔


代码如下 - 优化

import java.util.Arrays;

public class BubbleSort {
    /*
    * 时间复杂度:O(N^2)
    * 最好情况【数组有序】可以达到 O(N)
    * 空间复杂度:O(1)
    * 稳定性:稳定【未发生跳跃式交换】
    * */
    public static void bubbleSort(int[] array){
        for (int i = 0; i < array.length-1; i++) {
            boolean flag = true;
            for(int j = 0;j< array.length-1-i;j++){
                if(array[j] > array[j+1]){
                    int tmp = array[j];
                    array[j] = array[j+1];
                    array[j+1] = tmp;
                    flag = false;// 表示这一趟比较,数组是无序的
                }
            }
            // flag == true
            if(flag){
                break;
            }
        }
    }

    public static void main(String[] args) {
    // 前半段无序,后半段有序
        int[] array = {2,3,1,4,5};
        bubbleSort(array);
        System.out.println(Arrays.toString(array));
    }
}

Common Sort - 常见的几种排序 与 不常见的几种排序 - Java - 细节狂魔


未优化 和 优化代码 运行速度比较

public class BubbleSort {
    // 优化
    public static void bubbleSort2(int[] array){
        for (int i = 0; i < array.length-1; i++) {
            boolean flag = true;
            for(int j = 0;j< array.length-1-i;j++){
                if(array[j] > array[j+1]){
                    int tmp = array[j];
                    array[j] = array[j+1];
                    array[j+1] = tmp;
                    flag = false;
                }
            }
            // flag == true
            if(flag){
                break;
            }
        }
    }
    // 未优化
    public static void bubbleSort1(int[] array){
        for (int i = 0; i < array.length-1; i++) {
            for(int j = 0;j< array.length-1-i;j++){
                if(array[j] > array[j+1]){
                    int tmp = array[j];
                    array[j] = array[j+1];
                    array[j+1] = tmp;
                }
            }
        }
    }

    public static void main(String[] args) {
        int[] array = new int[10000];
        for (int i = 0; i < array.length; i++) {
            array[i] = i;
        }
        long start = System.currentTimeMillis();
        bubbleSort2(array);// 优化
        long end = System.currentTimeMillis();
        System.out.println(end - start);// 输出排序所需时间
        
        start = System.currentTimeMillis();
        bubbleSort1(array);// 未优化
        end = System.currentTimeMillis();
        System.out.println(end - start);//输出排序所需时间
    }
}

Common Sort - 常见的几种排序 与 不常见的几种排序 - Java - 细节狂魔


快速排序 - 重点

原理

1、从待排序区间选择一个数,作为基准值(pivot)
2、Partition(分割):遍历整个待排序区间,将比基准值小的(可以包含相等的)放到基准值的左边,将比基准值大的(可以包含相等的)放到基准值的右边。
3、采用分治思想,对左右两个小区间按照同样的方式处理,直到小区间的长度 == 1.代表已经有序,或者小区间的长度 == 0,代表没有数据。
Common Sort - 常见的几种排序 与 不常见的几种排序 - Java - 细节狂魔


总结

快速排序,其实说白了 和 二叉树 很像,先根,再左,后右。利用递归去实现!


程序框架

public class QuickSort {
    public static void quickSort(int[] array){
        quick(array,0, array.length);
    }
    public static void quick(int[] array,int start,int end){
        if(start >= end){
            return;
        }
        int pivot = partiton(array,start,end);
        quick(array,start,pivot-1);// 递归左边
        quick(array,pivot+1,end);// 递归右边
    }
    // 分割 - 找基准
    private static int partiton(int[] array,int start,int end){

    }
}

完善 partition 部分

    // 分割 - 找基准
    private static int partiton(int[] array,int start,int end){
        int tmp = array[start];
        while(start < end){
            while(start < end && array[end] >= tmp){
                end--;
            }
            // 此时 end 下标 元素的值 是 小于 tmp的。
            array[start] = array[end];
            while(start<end && array[start] <= tmp){
                start++;
            }
            //此时 start 下标元素的值 是 大于 tmp的。
            array[end] = array[start];
        }
        // start 和 end 相遇了,将 tmp 赋予 它们相遇下标指向的空间
        array[start] = tmp;
        return start;
    }

Common Sort - 常见的几种排序 与 不常见的几种排序 - Java - 细节狂魔


代码细节部分

Common Sort - 常见的几种排序 与 不常见的几种排序 - Java - 细节狂魔


总程序 - 未优化

import java.util.Arrays;

public class QuickSort {
    /*
    * 时间复杂度:O(N^2) 【数据有序或者逆序的情况】
    * 最好情况【每次可以均匀的分割待排序序列】:O(N * log2 N)
    * 空间复杂度:O(N)[单分支的一棵树]
    * 最好:log2 N
    * 稳定性:不稳定
    * */
    public static void quickSort(int[] array){
        quick(array,0, array.length-1);
    }
    public static void quick(int[] array,int start,int end){
        if(start >= end){
            return;
        }
        int pivot = partiton(array,start,end);
        quick(array,start,pivot-1);// 递归左边
        quick(array,pivot+1,end);// 递归右边
    }
    // 分割 - 找基准
    private static int partiton(int[] array,int start,int end){
        int tmp = array[start];
        while(start < end){
            while(start < end && array[end] >= tmp){
                end--;
            }
            // 此时 end 下标 元素的值 是 小于 tmp的。
            array[start] = array[end];
            while(start<end && array[start] <= tmp){
                start++;
            }
            array[end] = array[start];
        }
        array[start] = tmp;
        return start;
    }

    public static void main(String[] args) {
        int[] array = {6,1,2,7,9,3,4,5,10,8};
        quickSort(array);
        System.out.println(Arrays.toString(array));
    }
}

快速排序 的 时间 与 空间复杂度分析

Common Sort - 常见的几种排序 与 不常见的几种排序 - Java - 细节狂魔


堆排序 与 快排 的区别

细心的朋友会发现 堆排序 和 快排 的 时间复杂度在最好情况下 都是N* log2 N。
那么,两者又有什么区别?
堆排序,无论最好还是最坏情况,时间复杂度都是N* log2 N。空间复杂度 O(1)
那么,又为什么快排 比 堆排序 要快?
其实再细一点说 :在两个排序的时间复杂度都为 N* log2 N时,其实连着前面还有 一个 k【K * N* log2 N 】,只不过快排前面的K要小一点。所以快排要快一点。
在对空间复杂度没有要求的情况: 快排
对空间复杂度有要求的情况,或者说对数据的序列也要要求: 堆排


细节拓展

if语句中 比较大小的代码中 等号是不能省略的

当 下面框选的代码 没有等号时,会造成死循环。
Common Sort - 常见的几种排序 与 不常见的几种排序 - Java - 细节狂魔
我就改了一下,末尾元素的值。
Common Sort - 常见的几种排序 与 不常见的几种排序 - Java - 细节狂魔
那么,问题来了:为什么没有等号就死循环了?
Common Sort - 常见的几种排序 与 不常见的几种排序 - Java - 细节狂魔
所以,在 写快排的时候,比较大小的代码,记住一定要加上等号!!!!!


目前版本的 快排代码 不支持 大量数据进行排序 - 会导致栈溢出。

Common Sort - 常见的几种排序 与 不常见的几种排序 - Java - 细节狂魔

这是因为 我们递归的太深了,1百万数据,4百万字节。
1TB等于1024GB;1GB等于1024MB;1MB等于1024KB;1KB等于1024Byte(字节);1Byte等于8bit(位);
Common Sort - 常见的几种排序 与 不常见的几种排序 - Java - 细节狂魔
有的朋友会说:这才多大啊?栈怎么会被挤爆?
这是因为在递归的时候,开辟的栈帧【函数的信息,参数等等等…都有】,所以,每次开辟的栈帧不止 4byte。故栈被挤爆了。

所以,我们要优化快排的 代码。【优化:数据有序的情况】


基准值的选择 - 优化前的知识补充

1、选择边上(左或者右) 【重点,上面使用的就是这种方法】
2、随机选择(针对 有序数据)【了解】
Common Sort - 常见的几种排序 与 不常见的几种排序 - Java - 细节狂魔
3、几数取中(常见的就是三数取中):array[left],array[mid] ,array[right]中 大小为 中间值的为基准值【优化的关键】
Common Sort - 常见的几种排序 与 不常见的几种排序 - Java - 细节狂魔


快速排序(几数取中法 优化)

import java.util.Arrays;

public class QuickSort {
    /*
    * 时间复杂度:O(N^2) 【数据有序或者逆序的情况】
    * 最好情况【每次可以均匀的分割待排序序列】:O(N * log2 N)
    * 空间复杂度:O(N)[单分支情况]
    * 最好:log2 N
    * 稳定性:不稳定
    * */
    public static void quickSort(int[] array){
        quick(array,0, array.length-1);
    }
    public static void quick(int[] array,int start,int end){
        if(start >= end){
            return;
        }
        // 在找基准之前,先确定 start 和 end 的 中间值。[三数取中法]
        int midValIndex = findMidValIndex(array,start,end);
        //将它 与 start 交换。这样后面的程序,就不用改动了。
        swap(array,start,midValIndex);
        int pivot = partiton(array,start,end);
        quick(array,start,pivot-1);// 递归左边
        quick(array,pivot+1,end);// 递归右边
    }
    // 确定基准值下标
    private static int findMidValIndex(int[] array,int start,int end){
        // 确定 start 和 end 的中间下标
        int mid = start + ((end - start)>>>1);// == (start + end)/ 2
        // 确定 mid、start、end 三个下标,谁指向的元素是三个元素中的中间值
        if(array[end] > array[start]){
            if(array[start] > array[mid]){
                return start;
            }else if(array[mid] > array[end]){
                return end;
            }else{
                return mid;
            }
        }else{
            // array[start] >= array[end]
            if(array[end] > array[mid]){
                return end;
            }else if(array[mid] > array[start]){
                return start;
            }else {
                return mid;
            }
        }
    }
    // 交换两个下标元素
    private static void swap(int[] array,int x,int y){
        int tmp = array[x];
        array[x] = array[y];
        array[y] = tmp;
    }

    // 分割 - 找基准
    private static int partiton(int[] array,int start,int end){
        int tmp = array[start];
        while(start < end){
            while(start < end && array[end] >= tmp){
                end--;
            }
            // 此时 end 下标 元素的值 是 小于 tmp的。
            array[start] = array[end];
            while(start<end && array[start] <= tmp){
                start++;
            }
            array[end] = array[start];
        }
        array[start] = tmp;
        return start;
    }
    // 有序
    public static void test1(int capacity){
        int[] array = new int[capacity];
        for (int i = 0; i < capacity; i++) {
            array[i] = i;
        }
        long start = System.currentTimeMillis();
        quickSort(array);
        long end = System.currentTimeMillis();
        System.out.println(end - start);
    }

    public static void main(String[] args) {
        test1(100_0000);
        int[] array = {6,1,2,7,9,3,4,5,10,6};
        quickSort(array);
        System.out.println(Arrays.toString(array));
    }
}

Common Sort - 常见的几种排序 与 不常见的几种排序 - Java - 细节狂魔


优化总结

1、选择基准值很重要,通常使用几数取中法
2、partition 过程中把和基准值相等的数也选择出来
Common Sort - 常见的几种排序 与 不常见的几种排序 - Java - 细节狂魔
3、待排序区间小于一个阈(yù)值【临界值】

随着不断的划分基准,数组逐渐趋于有序,而区间随着递归也在减小。所以,利用 直接插入排序的特性【越有序越快】,来进一步优化 快排。
Common Sort - 常见的几种排序 与 不常见的几种排序 - Java - 细节狂魔


拓展 快速排序 - 非递归实现

非递归实现快速排序的思维

Common Sort - 常见的几种排序 与 不常见的几种排序 - Java - 细节狂魔


代码如下

import java.util.Arrays;
import java.util.Stack;

public class QuickSortNonRecursion {
    public static void quickSort(int[] array){
        Stack<Integer> stack = new Stack<>();
        int left = 0;
        int right = array.length-1;
        int pivot = partiton(array,left,right);
        if(pivot > left+1){
            stack.push(left);
            stack.push(pivot-1);
        }
        if(pivot < right -1){
            stack.push(pivot+1);
            stack.push(right);
        }
        while(!stack.isEmpty()){
            right = stack.pop();
            left = stack.pop();
            pivot = partiton(array,left,right);
            if(pivot>left+1){
                stack.push(left);
                stack.push(pivot-1);
            }
            if (pivot<right-1){
                stack.push(pivot+1);
                stack.push(right);
            }
        }
    }
    public static int partiton(int[] array,int start,int end){
        int tmp = array[start];
        while(start<end){
            while(start<end && array[end] >=tmp){
                end--;
            }
            array[start] = array[end];
            while (start<end && array[start] <= tmp){
                start++;
            }
            array[end] = array[start];
        }
        array[start] = tmp;
        return start;
    }

    public static void main(String[] args) {
        int[] array = {12,5,8,1,10,15};
        quickSort(array);
        System.out.println(Arrays.toString(array));
    }
}

Common Sort - 常见的几种排序 与 不常见的几种排序 - Java - 细节狂魔


归并排序 - 重点

知识铺垫 : 二路合并

将两个有序表合并成一个有序表,称为二路归并。【简单说就是 将两个有序数组合并为一个有序数组,称为二路合并】
Common Sort - 常见的几种排序 与 不常见的几种排序 - Java - 细节狂魔


二路合并的代码如下

import java.util.Arrays;

public class MergeSort {


/*
* array1 已有序
* array2 已有序
* */
    public static int[] mergeArrays(int[] array1,int[] array2){
        if(array1 == null || array2 == null){
            return array1 == null ? array2: array1;
        }
        int[] arr = new int[array1.length + array2.length];
        int i = 0;// arr 的 遍历变量
        int s1 = 0;//array1 的 遍历变量
        int s2 = 0;//array2 的 遍历变量
        while(s1 < array1.length && s2 < array2.length){
            if(array1[s1] > array2[s2]){
                arr[i++] = array2[s2++];
//                s2++;
//                i++;
            }else{
                arr[i++] = array1[s1++];
//                s1++;
//                i++;
            }
        }
        // 循环结束,有一个数组的元素已经全部存入
        // 接下来就是将另一个数组的元素放入 arr 中
        while (s1 < array1.length){
            arr[i++] = array1[s1++];
//            i++;
//            s1++;
        }
        while (s2 < array2.length){
            arr[i++] = array2[s2++];
//            i++;
//            s2++;
        }
        return arr;
    }

    public static void main(String[] args) {
        int[] array1 = {1,6,7,10};
        int[] array2 = {2,3,4,9};
        int[] mergeArray = mergeArrays(array1,array2);
        System.out.println(Arrays.toString(mergeArray));
    }
}

Common Sort - 常见的几种排序 与 不常见的几种排序 - Java - 细节狂魔


归并排序 - 原理

归并排序(MERGE - SORT)是建立在归并操作上的一种有效的排序算法,该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为二路归并。
Common Sort - 常见的几种排序 与 不常见的几种排序 - Java - 细节狂魔


难点1 - 如何将一个数组拆分成一个个单独数组【每个数组里只包含一个元素】。

Common Sort - 常见的几种排序 与 不常见的几种排序 - Java - 细节狂魔


难点2 - 合并

Common Sort - 常见的几种排序 与 不常见的几种排序 - Java - 细节狂魔


归并排序的程序框架

public class MergeSort {
    // 归并排序的调用“接口”
    public static int[] mergeSort(int[] array){
        if(array == null){
            return array;
        }
        mergeSortFunc(array,0,array.length-1);
        return array;
    }
    // 归并排序实现
    private static void mergeSortFunc(int[] array,int low,int high){
        if(low >= high){
            return;
        }
        // 递归分解
//       int mid = (high + low) >>> 1
        int mid = low + ((high - low) >>> 1);
        mergeSortFunc(array,low,mid);// 左边
        mergeSortFunc(array,mid+1,high);// 右边

         // 合并
        merge(array,low,mid,high);
    }

    private static void merge(int[] array,int low,int mid,int high){

    }
}

合并程序的完善

其实这个并不难,跟我前面做的知识铺垫的思路是一样的。
需要注意的是:
1、我们的参数中 只有一个数组
2、数组 arr ,只是一个临时数组,用来存储 合并之后的结果。
3、在将 arr 数组 存储的结果,转移到 原本数组的时候,注意赋值的位置!

    private static void merge(int[] array,int low,int mid,int high){
    // 获取 区间之内的元素个数,加一 是因为 零下标元素也算一个元素。
        int[] arr = new int[high - low +1];
        // 左边 区间 【你可以理解为 有序数组 array1的起始与结束下标位置】
        int start1 = low;
        int end1 = mid;
        // 右边 区间【你可以理解为 有序数组 array2的起始与结束下标位置】
        int start2 = mid+1;
        int end2 = high;
        int i = 0;
        while (start1 <= end1 && start2 <= end2){
            if(array[start1] > array[start2]){
                arr[i++] = array[start2++];
            }else{
                arr[i++] = array[start1++];
            }
        }
        while(start1 <= end1){
            arr[i++] = array[start1++];
        }
        while(start2 <= end2){
            arr[i++] = array[start2++];
        }
        // 将 arr 存储的 合并数据,转换到原本数组上。
        // 注意 array 数组中括号的下标的位置。
        for (int j = 0; j < arr.length; j++) {
            array[low++] = arr[j];
        }
    }

附图

Common Sort - 常见的几种排序 与 不常见的几种排序 - Java - 细节狂魔


归并排序 - 总程序

import java.util.Arrays;

public class MergeSort {
    /*
    * 时间复杂度:N * log2 N
    * 空间复杂丢:O(N)
    * 稳定性:稳定
    * */
    public static int[] mergeSort(int[] array){
        if(array == null){
            return array;
        }
        mergeSortFunc(array,0,array.length-1);
        return array;
    }
    private static void mergeSortFunc(int[] array,int low,int high){
        if(low >= high){
            return;
        }
//       int mid = (high + low) >>> 1
        int mid = low + ((high - low) >>> 1);
        mergeSortFunc(array,low,mid);// 左边
        mergeSortFunc(array,mid+1,high);// 右边
        merge(array,low,mid,high);
    }

    private static void merge(int[] array,int low,int mid,int high){
        int[] arr = new int[high - low +1];
        int start1 = low;
        int end1 = mid;
        int start2 = mid+1;
        int end2 = high;
        int i = 0;
        while (start1 <= end1 && start2 <= end2){
            if(array[start1] > array[start2]){
                arr[i++] = array[start2++];
            }else{
                arr[i++] = array[start1++];
            }
        }
        while(start1 <= end1){
            arr[i++] = array[start1++];
        }
        while(start2 <= end2){
            arr[i++] = array[start2++];
        }
        for (int j = 0; j < arr.length; j++) {
            array[low++] = arr[j];
        }
    }
    
    public static void main(String[] args) {
        int[] array = {1,6,7,10,2,3,4,9};
        mergeSort(array);
        System.out.println(Arrays.toString(array));
    }
}

Common Sort - 常见的几种排序 与 不常见的几种排序 - Java - 细节狂魔


归并排序 - 时间与空间复杂度分析、稳定性

Common Sort - 常见的几种排序 与 不常见的几种排序 - Java - 细节狂魔


归并排序 - 非递归实现

Common Sort - 常见的几种排序 与 不常见的几种排序 - Java - 细节狂魔


代码如下

import java.util.Arrays;

public class MergeSortNonRecursion {
    public static void mergeSort(int[] array){
        //归并排序非递归实现
        int groupNum = 1;// 每组的数据个数
        while(groupNum < array.length){
            // 无论数组含有几个元素, 数组每次都需要从下标 0位置,开始遍历。
            for(int i = 0;i<array.length;i+= groupNum * 2){
                int low = i;
                int mid = low + groupNum -1;

                // 防止越界【每组的元素个数,超过了数组的长度】
                if(mid >= array.length){
                    mid = array.length-1;
                }
                int high = mid + groupNum;

                // 防止越界【超过了数组的长度】
                if(high >= array.length){
                    high = array.length-1;
                }
                merge(array,low,mid,high);
            }
            groupNum *= 2;//每组的元素个数扩大到原先的两倍。
        }
    }
    public static void merge(int[] array,int low,int mid,int high){
    // high 与 mid 相遇,说明 此时数组分组只有一组,也就说没有另一组的数组与其合并
    // 即数组已经有序了,程序不用再往下走。
         if(high == mid){
            return;
        }
        int[] arr = new int[high -low + 1];
        int start1 = low;
        int end1 = mid;
        int start2 = mid+1;
        int end2 = high;
        int i = 0;
        while(start1 <= end1 && start2 <= end2){
            if(array[start1]>array[start2]){
                arr[i++] = array[start2++];
            }else{
                arr[i++] = array[start1++];
            }
        }
        while (start1 <= end1){
            arr[i++] = array[start1++];
        }
        while(start2 <= end2){
            arr[i++] = array[start2++];
        }
        for (int j = 0; j < arr.length; j++) {
            array[low++] = arr[j];
        }
    }

    public static void main(String[] args) {
        int[] array = {12,5,8,7,3,4,1,10};
        mergeSort(array);
        System.out.println(Arrays.toString(array));
    }
}

Common Sort - 常见的几种排序 与 不常见的几种排序 - Java - 细节狂魔


海量数据的排序问题

外部排序:排序过程需要在磁盘等外部存储进行的排序
【内部排序:排序过程需要在 内存上进行排序】
前提:内存只有 1G,需要排序的数据有 100G
因为内存中无法把所有数据全部放下,所以需要外部排序,而归并排序是最常用的外部排序。
1、先把文件切分成 200 份,每个512M
Common Sort - 常见的几种排序 与 不常见的几种排序 - Java - 细节狂魔
2、分别对 512M 的数据量 进行排序,因为 内存已经被分割了,512M < 1G 内存放得下。所以任何排序方式都可以,
3、进行 200 路归并,同时对 200 份有序文件做归并过程,最终结果就有序了
Common Sort - 常见的几种排序 与 不常见的几种排序 - Java - 细节狂魔


小总结

目前,我们讲了八种排序:直接插入排序、希尔排序、直接选择排序,双向选择排序、冒泡排序,堆排序、快速排序,归并排序。
其中稳定的排序:插入排序,冒泡排序,归并排序,一共三种。

另外,堆排序、归并排序、快速排序的时间复杂度都是 N * log2 N。
如果,你想速度快,就用快排。
如果,你想稳定,就用归并。
如果,你想空间复杂度低,就用堆排。


排序总结

Common Sort - 常见的几种排序 与 不常见的几种排序 - Java - 细节狂魔

排序方法 最好(时间复杂度) 平均(时间复杂度) 最坏(时间复杂度) 空间复杂度 稳定性
冒泡排序 O(N) O(N^2) O(N^2) O(1) 稳定
插入排序 O(N) O(N^2) O(N^2) O(1) 稳定
选择排序 O(N^2) O(N^2) O(N^2) O(1) 不稳定
希尔排序 O(N) O(N^1.3) O(N^2) O(1) 不稳定
堆排序 O(N * log2 N) O(N * log2 N) O(N * log2 N) O(1) 不稳定
快速排序 O(N * log2 N) O(N * log2 N) O(N ^ 2) O(N) 不稳定
归并排序 O(N * log2 N) O(N * log2 N) O(N * log2 N) O(N) 稳定

不常见的排序 - 不基于比较的排序(了解)

基数排序

它的思路:假设待排序的数据类型是 整形/十进制数,每个数据 分别按照 个,百,千,万的大小,放入拿出对应编号空间,其最终的结果就是有序的。
放入拿出的次数 取决于 这组数据中 最大值的位数。
Common Sort - 常见的几种排序 与 不常见的几种排序 - Java - 细节狂魔


代码如下

import java.util.Arrays;

public class RadixSort {
//  基数排序功能 实际功能实现方法
    private static void radixSortFunc(int[] array,int maxDigit){
        int mode = 10 ; // 十进制
        int divide = 1;// 将 数值上的每个数“分割”,方便获取数据的一个位上的值

        // 每个数据从个位到最大值的最高位,按照其位上的大小 放出 拿出
        for (int i = 0; i < maxDigit; i++,mode *= 10,divide *=10) {
            // 考虑 负数的 情况,0~9 对应负数,10 ~ 19 对应正数
            // 行 对应的是编号, 列 对应的存储的数据
            int[][] counter = new int[mode*2][0];

            for (int j = 0; j < array.length; j++) {
                int number = ((array[j] % mode)/divide) + mode; /*获取 数据对应 空间的编号 */
                counter[number] = arrayAppend(counter[number],array[j]);
            }
            int pos = 0;
            for (int[] number:counter) {
                for (int val:number) {
                    array[pos++] = val;
                }
            }
        }
    }
    // 添加 元素
    private static int[] arrayAppend(int[] arr,int value){
        arr = Arrays.copyOf(arr,arr.length+1);
        arr[arr.length-1] = value;
        return  arr;
    }



    // 基数排序 功能调用方法“窗口”
    public static void radixSort(int[] array){
        int maxNumLength = getNumLength(array);
        radixSortFunc(array,maxNumLength);
    }


    
    // 获取最大值的位数 - 功能“窗口”
    private static int getNumLength(int[] array){
        int maxVal = getMaxValue(array);
        return getMaxDigit(maxVal);
    }
    
    //获取最大值
    private static int getMaxValue(int[] array){
        int maxValue= array[0];
        for (int value: array) {
            if(value > maxValue){
                maxValue = value;
            }
        }
        return maxValue;
    }
    
    // 获取最大值的位数 - 执行
    private static int getMaxDigit(int num){
        if(num == 0){
            return 0;
        }
        int len = 0;
        while(num > 0){
            len++;
            num /= 10;
        }
        return len;
    }

       // 程序入口
    public static void main(String[] args) {
        int[] array = {124,366,170,52,200,78,468};
        radixSort(array);
        System.out.println(Arrays.toString(array));
    }
}

Common Sort - 常见的几种排序 与 不常见的几种排序 - Java - 细节狂魔


捅排序

Common Sort - 常见的几种排序 与 不常见的几种排序 - Java - 细节狂魔


计数排序

Common Sort - 常见的几种排序 与 不常见的几种排序 - Java - 细节狂魔

在使用 计数排序时,需注意以下几点:
1、确定基数排序的大小
2、这个计数排序 适用的范围【假设数据中最小值 10000,最大 12000,那么,我们的计数数组容量只需要2001(0 下标也算入) 就够了。不需要创建 12000容量,避免空间浪费】
计数数组 计数也简单,用元素值减去 10000(最小值) 就行了
3、必须找到数据中的最大值 和 最小值,锁定计数数组的长度:max - min + 1
4、 拿出数据的时候,记得将减去的 最小值 加上,再进行对原始数组的覆写。
Common Sort - 常见的几种排序 与 不常见的几种排序 - Java - 细节狂魔


代码如下

import java.util.Arrays;
/*
* 时间复杂度:O(N)
* 空间复杂度: O(M) : M 表示 当前数据的范围
* 【空间 换 时间】
* 稳定性: 当前代码是不稳定,本质是稳定的。
* 在借助一个 数组来存储 每个元素排序后,最后出现的位置,
* 拿出来的时候,就能确定位置。致使该排序 稳定。 - 见附图
* */
public class CountingSort {
    public static void countingSort(int[] array){
        int maxVal = array[0];
        int minVal = array[0];
        for (int i = 0; i < array.length; i++) {
            if (array[i] > maxVal){
                maxVal = array[i];
            }
            if(array[i] < minVal){
                minVal =array[i];
            }
        }
        // 当循环结束,获得了 数据的最大值 和 最小值
        // 可以确定计数数组的容量
        int[] count = new int[maxVal -minVal +1];
        for (int i = 0; i < array.length; i++) {
          // 提高空间利用率
            count[ array[i] - minVal ]++;
        }
        // 此时,计数数组 已经把array数组当中,每个元素的出现次数统计好了
        // 接下来,只需要遍历计数数组,把 数据 覆写 到 array当中。
        int indexArray = 0; // 用于遍历 array数组,标记 覆写的位置。
        for (int i = 0; i < count.length; i++) {
            while(count[i]>0){
                // 这里一定要加上减去minVal,因为 下标 i 不一定 在 array 数组中出现过。
                array[indexArray++] = i + minVal;// 拿出来的时候,记得将减去的值加上
                // indexArray++;
                count[i]--;
            }
        }
    }

    public static void main(String[] args) {
        int[] array = {5,0,2,3,4,5,2};
        countingSort(array);
        System.out.println(Arrays.toString(array));
    }
}

Common Sort - 常见的几种排序 与 不常见的几种排序 - Java - 细节狂魔


附图 - 是目前的计数排序稳定

Common Sort - 常见的几种排序 与 不常见的几种排序 - Java - 细节狂魔

本文结束

相关文章

暂无评论

暂无评论...