当前位置： 首页 > article >正文

七大经典基于比较排序算法【Java实现】

article 2024/11/12 21:47:31

七种基于比较的排序算法

  • 一.直接插入排序:
    • 1.1插入排序
    • 1.2希尔排序（缩小增量排序法）
  • 二.选择排序
    • 2.1选择排序
    • 2.2堆排序（基于树（堆）的数据结构）
  • 三.交换排序
    • 3.1冒泡排序
    • 3.1快速排序(大致分三种partition方法)
      • 3.1.1Hoare法
      • 挖坑法（最常用，选择题首选)
      • 前后指针法
  • 四.归并排序

排序 是我们平时经常需要使用的操作， 所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。 这里我们介绍七种常用的经典排序，要想理解排序就必须理解每种排序背后的算法思想。 在不同的场景合理地应用不同地排序方法,以便我们能高效地解决问题。

接下来每种排序我都从 算法实现，时间复杂度，空间复杂度，稳定性这几个方面进行阐述。
时间复杂度和空间复杂度是数据结构的基础知识，而稳定性需要着重阐述一下：

在这里插入图片描述

即不改变相同数值的内部既定顺序的排序称为稳定排序。

一.直接插入排序:

1.1插入排序

在这里插入图片描述

 /** 时间复杂度:o(n^2)
         最坏情况：5 4 3 2 1
         最好情况: 1 2 3 4 5 o(n)
         如果一组数据越有序，则直接插入排序效率越高
         空间复杂度:o(1)
         稳定性：稳定排序（>)
         如果一个排序本身是稳定的，那么他可以实现为不稳定的
         若是不稳定的，则它不能实现为稳定的
         *
         */
        //默认从小到大,第一个数字默认有序
public static void insertSort(int[] array) {
        for (int i = 1; i < array.length; i++) {
            int tmp = array[i];
            int j = i - 1;
            for (; j >= 0; j--) {
                if (array[j] > tmp) {
                    array[j + 1] = array[j];
                } else {
                    array[j + 1] = tmp;
                    break;
                }
            }
            array[j + 1] = tmp;
        }
    }

1.2希尔排序（缩小增量排序法）

在这里插入图片描述
在这里插入图片描述

希尔排序可视为直接插入排序的一种优化，其本质是将数据分为多组别，在不同组别内部进行插入排序，随着组别数减少，组别内数据元素趋于有序，效率加快。

/**
     * 希尔排序(直接插入排序的一种优化)
     * 首先通过gap对所需排序数据分组进行预排序
     * gap的取法不一致导致时间复杂度不同
     * 当gap越大时，每组数据趋于无序，但数据较少
     * 当gap越小时，每组数据越多，但相较趋于有序
     * 时间复杂度:就我这种gap取法而言,n*log2n
     * 			一般来说n^1,3~n^1.5(实验得出）
     * 空间复杂度:o(1)
     * 稳定性:不稳定
     *
     * @param array
     */
public static void shellSort(int[] array) {
        int gap = array.length;
        //时间复杂度:o(log2n)
        while (gap > 1) {
            //在gap>1之前进行的都是预排序
            gap /= 2;//这里仅仅只gap的一种取法，取法不固定
            shell(array, gap);//gap可以取到1
        }
    }

    private static void shell(int[] array, int gap) {
        //shell的时间复杂度大约为o(n)(可以考虑极端情况)
        for (int i = gap; i < array.length; i++) {
            //i最后是需要i++的
            int tmp = array[i];
            int j = i - gap;
            for (; j >= 0; j -= gap) {
                if (array[j] > tmp) {
                    array[j + gap] = array[j];
                } else {
                    array[j + gap] = tmp;
                    break;
                }
            }
            array[j + gap] = tmp;
        }
    }

二.选择排序

2.1选择排序

在这里插入图片描述

思想简单，但效率不高！

/**
     * 选择排序:
     * 时间复杂度：o(n^2)
     * 和数据是否有序无关
     * 空间复杂度:o(1)
     * 稳定性:不稳定排序
     *
     * @param array
     */
    public static void selectSort1(int[] array) {
        //12,5,2,9,10,7
        //i j

        for (int i = 0; i < array.length; i++) {
            int minIndex = i;
            for (int j = i + 1; j < array.length; j++) {
                if (array[j] < array[i]) {
                    minIndex = j;
                }
            }
            swap(array, i, minIndex);
        }
    }
    public static void selectSort2(int[] array) {
        //12,5,2,9,10,7
        //i j
        int left = 0;
        int right = array.length - 1;
        while (left < right) {
            int minIndex = left;
            int maxIndex = left;
            for (int i = left + 1; i <= right; i++) {
                if (array[i] < array[minIndex]) {
                    minIndex = i;
                }
                if (array[i] > array[maxIndex]) {
                    maxIndex = i;
                }
            }
            swap(array, left, minIndex);
            //这里有个问题，如果left是最大值的话，它会被交换到minIndex处，则在下一次交换时找不到maxIndex
            if (left == maxIndex) {
                maxIndex = minIndex;
            }
            swap(array, right, maxIndex);
            left++;
            right--;
        }
    }

    private static void swap(int[] array, int i, int minIndex) {
        int tmp = array[i];
        array[i] = array[minIndex];
        array[minIndex] = tmp;
    }

2.2堆排序（基于树（堆）的数据结构）

在这里插入图片描述
在这里插入图片描述

/**堆排序(Heapsort):是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。它是通过堆
     来进行选择数据。需要注意的是 排升序要建大堆，排降序建小堆。
     * 时间复杂度:o(n*logn)
     * 空间复杂度:o(1)
     * 稳定性:不稳定
     * @param array
     */
    public static void heapSort(int[] array){
        createHeap(array);
        int end=array.length-1;
        while(end>0){
            swap(array,0,end);
            siftDown(array,0,end);
            end--;
        }
    }

    private static void createHeap(int[] array) {
        for(int parent=(array.length-1-1)/2;parent>=0;parent--){
            siftDown(array,parent,array.length);
        }
    }
    /**
     * @param array
     * @param parent 每棵子树调整的根节点
     * @param length 每棵子树调整的结束节点
     */
    private static void siftDown(int[] array, int parent, int length) {
        int child=2*parent+1;
        while(child<length){
            if(child+1<length&&array[child+1]>array[child]){
                child++;
            }
            if(array[child]>array[parent]){
                swap(array,parent,child);
                parent=child;
                child=2*parent+1;
            }else{
                break;
            }
        }
    }

三.交换排序

3.1冒泡排序

最大（小）的数据不断移动到数据末尾，就像水泡一样浮出水面。

/**冒泡排序:
     *时间复杂度:o(n^2)---优化前
     * 优化后可能达到o(n)
     * 空间复杂度:o(1)
     * 稳定性:稳定排序
     * @param array
     */
    public static void bubbleSort(int[] array){
    //外层循环表示循环趟数
        for(int i=0;i< array.length-1;i++){
            boolean flag=false;//优化
            for(int j=0;j< array.length-1-i;j++){
                if(array[j]>array[j+1]){
                    swap(array,j,j+1);
                    flag=true;
                }
            }
            if(!flag){
                break;
            }
        }
    }

3.1快速排序(大致分三种partition方法)

在这里插入图片描述
在这里插入图片描述
以递归左边为例子：
在这里插入图片描述

快速排序不适用于数据是完全的顺序和逆序的这种极端情况。而适合在数据相对随机的时候使用。因为使用的递归，所以会在栈上开辟空间。

3.1.1Hoare法

/**
     * 时间复杂度：
     *       最坏情况：当数据给定的是1 2 3 4 5 6 7.....有序的情况下 确实是O(n^2)
     *                          9 8 7 6 5 4
     *       最好情况：O(N*logN)
     * 空间复杂度：
     *      最坏情况：O(N)
     *      最好情况：O(logN)
     * 稳定性：
     *      不稳定性
     * @param array
     */
    public static void quickSort(int[] array){
        //为了保证接口统一,所以创建quick方法
        quick(array,0,array.length-1);
    }

    private static void quick(int[] array, int start, int end) {
        if(start>=end)return;
        int pivot=partitionHoare(array,start,end);//找中间值
        quick(array,start,pivot-1);//递归左边
        quick(array,pivot+1,end);//递归右边
    }

    private static int partitionHoare(int[] array, int left, int right) {
        int tmp=array[left];
        int tmpLeft=left;
        while(left<right){
            while(left<right&&array[right]>=tmp){
                right--;
            }
            while(left<right&&array[left]<=tmp){
                left++;
            }
            swap(array,left,right);
        }
        swap(array,left,tmpLeft);
        return left;
        //return right;
    }
}

挖坑法（最常用，选择题首选)

前后指针法

四.归并排序

测试代码：

public class Test {
    public static void orderArray(int[] array){
        for(int i=0;i<array.length;i++){
            array[i]=i;//顺序
            //array[i]= array.length-i-1;//逆序
        }
    } public static void notorderArray(int[] array){
        Random random=new Random();
        for(int i=0;i<array.length;i++){
            array[i]=random.nextInt(10_0000);
        }
    }
    public static void testSimple(){
        int[] array={12,5,2,9,10,7};
        System.out.println("排序前:"+ Arrays.toString(array));
        Sort.quickSort(array);
        System.out.println("排序后："+Arrays.toString(array));
    }
    public static void testOther(){
        int[] array=new int[10_0000];
        //orderArray(array);
        notorderArray(array);
        testInsertSort(array);
        testShellSort(array);
        testSelectSort1(array);
        testSelectSort2(array);
        testHeapSort(array);
        testBubbleSort(array);
        testQuickSort(array);
    }
    public static void testInsertSort(int[] array){
        //避免测试后数组本身被修改
        array=Arrays.copyOf(array,array.length);
        long startTime=System.currentTimeMillis();
        Sort.insertSort(array);
        long endTime=System.currentTimeMillis();
        System.out.println("直接插入排序1时间："+(endTime-startTime));
    }
    public static void testShellSort(int[] array){
        array=Arrays.copyOf(array,array.length);
        long startTime=System.currentTimeMillis();
        Sort.shellSort(array);
        long endTime=System.currentTimeMillis();
        System.out.println("希尔插入排序时间："+(endTime-startTime));
    }
    public static void testSelectSort1(int[] array){
        array=Arrays.copyOf(array,array.length);
        long startTime=System.currentTimeMillis();
        Sort.selectSort1(array);
        long endTime=System.currentTimeMillis();
        System.out.println("选择插入排序1时间："+(endTime-startTime));
    }
    public static void testSelectSort2(int[] array){
        array=Arrays.copyOf(array,array.length);
        long startTime=System.currentTimeMillis();
        Sort.selectSort2(array);
        long endTime=System.currentTimeMillis();
        System.out.println("选择插入排序2时间："+(endTime-startTime));
    }
    public static void testHeapSort(int[] array){
        array=Arrays.copyOf(array,array.length);
        long startTime=System.currentTimeMillis();
        Sort.heapSort(array);
        long endTime=System.currentTimeMillis();
        System.out.println("堆排序时间："+(endTime-startTime));
    }
    public static void testBubbleSort(int[] array){
        array=Arrays.copyOf(array,array.length);
        long startTime=System.currentTimeMillis();
        Sort.bubbleSort(array);
        long endTime=System.currentTimeMillis();
        System.out.println("冒泡排序时间："+(endTime-startTime));
    }
    public static void testQuickSort(int[] array){
        array=Arrays.copyOf(array,array.length);
        long startTime=System.currentTimeMillis();
        Sort.quickSort(array);
        long endTime=System.currentTimeMillis();
        System.out.println("快速排序时间："+(endTime-startTime));
    }
    public static void main(String[] args) {
        testSimple();
        testOther();
    }
}

http://www.kler.cn/a/388250.html

相关文章：

  • Qt初识简单使用Qt
  • 现代Web开发：Vue 3 组件化开发实战
  • 移门缓冲支架的作用与优势
  • 深入解析Hadoop：大数据处理的基石
  • el-input 正则表达式校验输入框不能输入汉字
  • Fortran安装（vscode+gcc+Python）
  • Elasticsearch实战应用：打造高效的全文搜索与高亮显示功能
  • Python实现粒子滤波算法
  • 1024程序员节|借势AI，写出牛码
  • jmeter常用配置元件介绍总结之jsr223执行python脚本
  • 【温度表达转化】
  • mybatis-plus 长sql执行缓慢问题
  • 【前端】Svelte：核心语法和组件基础
  • RabbitMQ — 异步调用
  • 【Webpack配置全解析】打造你的专属构建流程️(4)
  • 【解决】Pico 串流 Unity 开发环境 Preview 黑屏问题
  • 现代化汽车共享：SpringBoot管理系统开发
  • 数据与Python
  • 企业内部知识库搭建工具精选
  • 用js去除变量里的html标签
  • Android gradle下载失败后 解决方案
  • python在车载电子测试方面的应用
  • uniapp—android原生插件开发（1环境准备）
  • 深度学习：微调（Fine-tuning）详解
  • 蓝牙规范系列--属性协议（基础篇）
  • Pytorch学习--神经网络--网络模型的保存与读取