十大排序算法(Java实现)

这篇具有很好参考价值的文章主要介绍了十大排序算法(Java实现)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

零、总览 / 前言

十大排序算法(Java实现),2022,排序算法,java,算法

复杂度和稳定性表格一览

排序算法 平均时间 最好时间 最坏时间 空间 稳定性
冒泡 O ( n 2 ) O(n^2) O(n2) O ( n ) O(n) O(n) O ( n 2 ) O(n^2) O(n2) O ( 1 ) O(1) O(1) 稳定
选择 O ( n 2 ) O(n^2) O(n2) O ( n 2 ) O(n^2) O(n2) O ( n 2 ) O(n^2) O(n2) O ( 1 ) O(1) O(1) 不稳定
插入 O ( n 2 ) O(n^2) O(n2) O ( n ) O(n) O(n) O ( n 2 ) O(n^2) O(n2) O ( 1 ) O(1) O(1) 稳定
希尔 O ( 1 ) O(1) O(1) 不稳定
归并 O ( n l o g n ) O(nlogn) O(nlogn) O ( n l o g n ) O(nlogn) O(nlogn) O ( n l o g n ) O(nlogn) O(nlogn) O ( n ) O(n) O(n) 稳定
快排 O ( n l o g n ) O(nlogn) O(nlogn) O ( n l o g n ) O(nlogn) O(nlogn) O ( n 2 ) O(n^2) O(n2) O ( l o g n ) O(logn) O(logn) 不稳定
堆排序 O ( n l o g n ) O(nlogn) O(nlogn) O ( n l o g n ) O(nlogn) O(nlogn) O ( n l o g n ) O(nlogn) O(nlogn) O ( 1 ) O(1) O(1) 不稳定
计数排序 O ( n + k ) O(n+k) O(n+k) O ( n + k ) O(n+k) O(n+k) O ( n + k ) O(n+k) O(n+k) O ( n + k ) O(n+k) O(n+k) 稳定
基数排序 稳定
桶排序 O ( n ) O(n) O(n) O ( n ) O(n) O(n) O ( 1 ) O(1) O(1) 稳定

解释一下稳定性:
对于存在相等元素的序列,排序后,原相等元素在排序结果中的 相对位置 相比原输入序列不变
例如 nums={3,1, 2 1 2_1 21, 2 2 2_2 22} ,数字 2 出现了两次,下标表示他们出现的次序,若排序方法将 nums 排成了 {1, 2 2 2_2 22​ , 2 1 ​ 2_1​ 21 ,3} ,虽然排序结果正确,但改变了两个 2 的相对位置。只有排序为 {1, 2 1 2_1 21, 2 2 2_2 22,3} 我们才说该排序是稳定的。

如果排序对象只是数值,那么是否稳定没有区别。但若是对引用类型进行排序,排序依据是该类型中的某个可比较的数值字段,那么我们可能会希望该字段相同,但其他字段不同的元素相对位置相比原输入保持不变,这时候就需要稳定排序。

不稳定排序算法
堆排序、快速排序、希尔排序、直接选择排序

稳定排序算法
基数排序、冒泡排序、插入排序、归并排序

一、冒泡排序

1.算法描述

对于要排序的数组,从第一位开始从前往后比较相邻两个数字,若前者大,则交换两数字位置,然后比较位向右移动一位。第1轮从前到后的比较将使得最大的数字 冒泡 到最后

接着第二轮,同样的操作,只不过只需要比到倒数第二个(倒数第一已经最大了)

重复以上操作……

2.代码&复杂度

//冒泡排序,从小到大排序,比较相邻元素,更大的往数组右边移动
    static void bubbleSort3(int[] arr)
    {
        for(int i=arr.length-1;i>0;i--)
        {
            for(int j=0;j<i;j++)
            {
                if(arr[j]>arr[j+1])
                {
                    int tmp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = tmp;
                }
            }
        }
    }

时间复杂度:O(n^2)
空间复杂度:O(1)

二、选择排序

1.算法描述

步骤:
(1)长度为n的数组中,第一次遍历n-1个数,找到最小的数值与第一个元素交换

(2)第二次遍历n-2个数,找到最小的数值与第二个元素交换

(3)第n-1次遍历,找到最小的数值与第n-1个元素交换,排序完成

2.代码&复杂度

 public void selectSort3(int[] arr)
    {
        for(int i=0;i<arr.length;i++)
        {
            int minTmp = Integer.MAX_VALUE;
            int index=0;
            // 开始寻找本轮最小的数字
            for(int j=i;j<arr.length;j++)
            {
                if(minTmp>arr[j])
                {
                    // 每次找到更小的时候记录数字和下标值
                    minTmp = arr[j];
                    index = j;
                }
            }
            // 本轮循环结束,将最小值交换到数组前方
            int temp = arr[i];
            arr[i] = minTmp;
            arr[index] = temp;
    }

时间复杂度:O(n^2)
空间复杂度:O(1)

三、插入排序

1.算法描述

插入排序是一种最简单直观的排序算法,它的工作原理是通过构建有序序列

算法步骤:
(1)将第一待排序序列第一个元素看做一个有序序列,把第二个元素到最后一个元素当成是未排序序列。

(2)从头到尾依次扫描未排序序列,将扫描到的每个元素插入有序序列的适当位置。如果待插入的元素与有序序列中的某个元素相等,则将待插入元素插入到相等元素的后面。

2.代码&复杂度分析

 /*插入排序:从小到大排序,类似于打扑克牌*/
    static void insertSort(int[] arr)
    {
        for(int i=1;i<arr.length;i++)
        {
            int now=arr[i]; //刚抓的手牌
            int j=i-1; //现有最后一张手牌的位置
            while (j>=0 && now<arr[j])  //刚抓的手牌小于手上现有的
            {
                arr[j+1]=arr[j];
                j--;
            }
            arr[j+1]=now;
        }
    }

时间复杂度:O(n^2)—— i 遍历一次,j遍历了一次,所以n^2
空间复杂度:O(1)—— 原地修改,没有用额外空间

四、希尔排序

1.算法步骤

先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序,待整个序列中的记录"基本有序"时,再对全体记录进行依次直接插入排序。

2.代码&复杂度分析

  //希尔排序:从小到大
  static void shellSort(int[] arr)
  {
      for(int interval=arr.length/2;interval>0;interval=interval/2)
      {
          for(int i=interval;i<arr.length;i++)
          {
              int temp=arr[i]; //从中间开始
              int j=i-interval; //增量是interval的前面的一个元素
              while (j>=0 && temp<arr[j])
              {
                  arr[j+interval]=arr[j];
                  j-=interval;
              }
              arr[j+interval]=temp;
          }
      }
  }

时间复杂度:
空间复杂度:

五、归并排序

1.算法描述

分而治之,先分治,再合并

2.代码&复杂度分析

public static void main(String[] args) {
        int[] arr = {5, 3, 8, 6, 2, 7};
        mergeSort(arr, 0, arr.length-1);
        System.out.println(Arrays.toString(arr));
    }
       // 自顶向下,递归实现
        public static void mergeSort(int[] arr, int left, int right) {
            if (left < right) {
                int mid = (left + right) / 2;
                mergeSort(arr, left, mid);
                mergeSort(arr, mid+1, right);
                merge(arr, left, mid, right);
            }
        }

        // 非原地合并
        public static void merge(int[] arr, int left, int mid, int right) {
            int[] temp = new int[arr.length];
            int i = left;
            int j = mid + 1;
            int k = left;
            while (i <= mid && j <= right) {
                if (arr[i] <= arr[j]) {
                    temp[k++] = arr[i++];
                } else {
                    temp[k++] = arr[j++];
                }
            }
            while (i <= mid) {
                temp[k++] = arr[i++];
            }
            while (j <= right) {
                temp[k++] = arr[j++];
            }
            for (int m = left; m <= right; m++) {
                arr[m] = temp[m];
            }
        }

六、快速排序

1.算法描述

首先在数组中确定一个主轴元素 (一般以第一个元素为主轴元素),然后遍历数组,将数组分为两部分, 小于 主轴的元素放在 (最终的) 主轴下标 p 的左侧, 大于等于 主轴的放在右侧。

具体每一轮的操作过程是:
双指针的思想,左指针指向第一个元素,右指针指向最后一个元素。左指针的目标是找到比主轴元素大的,找到后指针就停止,右指针则相反。当两者都找到后,就进行交换。然后继续这个过程,知道两指针相遇。

贴一个简单易懂的快排的排序过程:https://blog.csdn.net/qq_40941722/article/details/94396010

2.代码&复杂度分析

void quickSort(int[] arr,int left,int right)
    {
        if(left>right)
            return;
        int pivot=arr[left];
        int i=left;
        int j=right;
        while(i!=j)
        {
            while (i<j && arr[j]>=pivot)
                j--;
            while(i<j && arr[i]<=pivot)
                i++;
            if(i<j)
            {
                int temp=arr[j];
                arr[j]=arr[i];
                arr[i]=temp;
            }
        }
        arr[left]=arr[i];
        arr[i]=pivot;

        quickSort(arr,left,i-1);
        quickSort(arr,i+1,right);
    }

时间复杂度:O(nlogn)
空间复杂度:O(logn)

七、堆排序

八、计数排序——非比较排序

1.算法描述

计数排序的核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。通常 适用于整数数组,是一种利用整数特点取得 线性复杂度非比较排序方法

算法步骤:
(1)找出待排序的数组中最大max和最小min的元素

(2)创建一个计数数组 countArr ,其大小为 arrarr 中的max-min+1

(3)统计数组中每个值为i的元素出现的次数,每读取一个arr[i] ,直接令countArr[arr[i]-min]++

(4) 遍历countArr ,依次输出 counter[i] 个 i ,即为排序结果

2.代码&复杂度分析

static int[] countSort(int[] arr)
    {
        int minNum=0,maxNum=0;
        // 先求出数组中的最大值和最小值
        for (int num : arr) {
            minNum = Math.min(minNum, num);
            maxNum = Math.max(maxNum, num);
        }
        // 开辟一个新数组:计数数组
        int[] count = new int[maxNum-minNum+1];
 
        // 遍历原数组,对应计数数组索引值++
        for(int num:arr)
        {
            count[num-minNum]++;
        }
        // 开始将计数数组输出
        int index=0;
        for(int i=0;i<count.length;i++)
        {
            while(count[i]>0)
            {
                arr[index++] = i;
                count[i]--;
            }
        }
        return arr;
    }

时间复杂度: O(n + k),n 为元素个数, k 计数数组大小

空间复杂度:O(k)

上面的还是属于不稳定版本的,稳定版本可以参见:https://leetcode.cn/circle/discuss/eBo9UB/

九、基数排序——非比较排序

十、桶排序——非比较排序

参考链接:https://leetcode.cn/circle/discuss/eBo9UB/文章来源地址https://www.toymoban.com/news/detail-520205.html

到了这里,关于十大排序算法(Java实现)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 归并排序算法(Java实现)

    也称 合并排序算法 ,是将两个或两个以上的有序数据序列合并成一个新的有序数据序列。该算法采用分治法(Divide and Conquer)的思想,将待排序的序列分成若干个子序列,分别对子序列进行排序,然后将有序的子序列合并成一个大的有序序列 注:将几个有序队列合并成一个

    2024年01月17日
    浏览(38)
  • Java 语言实现选择排序算法

    【引言】 选择排序算法是一种简单但有效的排序算法。它的原理是每次从未排序的元素中选择最小(或最大)的元素,放在已排序的末尾(或开头),逐渐形成有序序列。本文将使用Java语言实现选择排序算法,并详细讲解其思想和代码实现。 【算法思想】 选择排序的核心思

    2024年02月11日
    浏览(55)
  • Java 语言实现归并排序算法

    【引言】 归并排序算法是一种高效且稳定的排序算法。它采用分治法的思想,将数组反复分割成两个子数组,直到每个子数组只有一个元素。然后将这些子数组逐个合并,最终得到排序完毕的数组。本文将使用Java语言实现归并排序算法,并详细讲解其核心思想和代码实现。

    2024年02月11日
    浏览(35)
  • Java高级语言实现插入排序算法

    【引言】 插入排序算法是一种简单且常用的排序算法。它通过依次将未排序的元素插入已排序序列中的正确位置来达到排序的目的。本文将使用Java高级语言实现插入排序算法,并讲解其核心思想和代码实现。 【算法思想】 插入排序的核心思想是通过构建有序序列,对于未排

    2024年02月11日
    浏览(48)
  • Java十大经典算法—KMP

    概念 Knuth-Morris-Pratt 字符串查找算法 ,简称为 “KMP 算法”,常用于在一个文本串 S 内查找一个模式串 P 的出现位置,这个算法由 Donald Knuth、Vaughan Pratt、James H. Morris 三人于 1977 年联合发表,故取这 3 人的姓氏命名此算法. KMP 方法算法就利用之前判断过信息,通过一个 next 数

    2024年02月02日
    浏览(45)
  • java实现七种经典排序算法

    简单算法:冒泡,简单选择,直接插入 改进算法:希尔,堆,归并,快速 直接插入排序:将一个记录插入到已经拍好的有序列表中,从而得到一个新的、记录数增加1的有序表。 冒泡排序:两两比较,反序交换。每趟将最大(小 )的浮到最上面或沉到最底下。 简单选择排序

    2024年02月15日
    浏览(31)
  • 【数据结构】用Java实现七大排序算法

    目录 🌷1. 排序的概念及引用 1.1 排序的概念 1.2 衡量指标 1.2 十个排序算法  1.3 十个排序性能对比 🌷2. 冒泡排序 2.1 算法描述 2.2 动图 ⭐️代码优化 🌷3. 选择排序 3.1 算法描述 3.2 动图  3.3 代码 🌷4. 插入排序 4.1 算法描述 4.2 动图  4.3 代码 🌷5 希尔排序 5.1 描述 5.2 动图  

    2023年04月23日
    浏览(54)
  • 【算法与数据结构】Java实现查找与排序

    也叫做折半查找,属于有序查找算法。 前提条件 :数组数据必须有序,从小到大,或者从大到小都是可以的。 如果是无序的,也可以先进行排序。 但是排序之后,会改变原有数据的顺序,查找出来元素位置跟原来的元素可能是不一样的,所以排序之后再查找只能判断当前数

    2024年01月19日
    浏览(51)
  • 数据结构与算法中的七大排序(Java实现)

    目录 一、直接插入排序 二、希尔排序 三、直接选择排序 四、堆排序 五、冒泡排序 六、快速排序 七、归并排序               定义i下标之前的元素全部已经有序 ,遍历一遍要排序的数组,把i下标前的元素全部进行排序,当遍历玩这个数组后,就已经排好序了。        

    2024年02月06日
    浏览(58)
  • 【华为OD机试】启动多任务排序(拓扑排序算法—Java&Python&C++&JS实现)

    本文收录于专栏:算法之翼 本专栏所有题目均包含优质解题思路,高质量解题代码(JavaPythonC++JS分别实现),详细代码讲解,助你深入学习,深度掌握!

    2024年04月15日
    浏览(45)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包