文章详情

短信预约-IT技能 免费直播动态提醒

请输入下面的图形验证码

提交验证

短信预约提醒成功

常见的初级排序算法有哪些

2024-04-02 19:55

关注

本篇内容主要讲解“常见的初级排序算法有哪些”,感兴趣的朋友不妨来看看。本文介绍的方法操作简单快捷,实用性强。下面就让小编来带大家学习“常见的初级排序算法有哪些”吧!

前言

相信所有的程序员刚开始接触到的算法都会是排序算法,因为排序在对数据处理和计算有这重要的地位,排序算法往往是其他算法的基础;本文我们就先从初级排序算法开始学习算法。

排序算法的模板

在开始之前我们先定义一个排序算法通用的模板,在后面的排序算法都会实现这个模板

public interface SortTemplate {      void sort(Comparable[] array);      default void print(Comparable[] array) {         for (Comparable a : array) {             System.out.print(a + " ");         }     }      default boolean less(Comparable a, Comparable b) {         return a.compareTo(b) < 0;     }      default void exch(Comparable[] array, int i, int j) {         Comparable tmp = array[i];         array[i] = array[j];         array[j] = tmp;     }      }

选择排序

算法实现的思路:

常见的初级排序算法有哪些

代码实现:

public class SelectionSort implements SortTemplate {      @Override     public void sort(Comparable[] array) {         int length = array.length;         for (int i = 0; i < length; i++) {             int min = i;             for (int j = i + 1; j < length; j++) {                 if (less(array[j], array[min])) {                     min = j;                 }             }             exch(array, i, min);         }     }  }

假如输入的数组是有序的,我们会发现选择排序运行的时候和未排序的时间一样长!

对于N个元素的数组,使用「选择排序的时间复杂度是O(n2)」

选择排序的是「数据移动最少」的,交换的次数与数组的大小是线性关系,N个元素的数组需要N次交换

冒泡排序

算法实现的思路:

比较相邻的两个元素,如果前一个比后一个大,那么就交换两个元素的位置

对每一组相邻的元素执行同样的操作,直到最后一个元素,操作完成之后就可以排定一个最大的元素

如此往复,直到数组中所有的元素都有序

常见的初级排序算法有哪些

代码实现:

public class BubbleSort implements SortTemplate {      @Override     public void sort(Comparable[] array) {         int length = array.length - 1;         for (int i = 0; i < length; i++) {             for (int j = 0; j < length - i; j++) {                 if (less(array[j + 1], array[j])) {                     exch(array, j, j + 1);                 }             }         }     }  }

对于N个元素的数组,使用「冒泡排序的时间复杂度是O(n2)」

插入排序

想象我们在玩扑克牌时,整理扑克牌都是把每一张插入到左边已经排好序的牌中适当的位置。插入排序的思路类似

算法实现的思路:

常见的初级排序算法有哪些

代码实现:

public class InsertionSort implements SortTemplate {      @Override     public void sort(Comparable[] array) {         int length = array.length;         for (int i = 1; i < length; i++) {             for (int j = i; j > 0 && less(array[j], array[j - 1]); j--) {                 exch(array, j, j - 1);             }         }     }  }

从代码的实现我们可以看出,当遇到了当前索引的元素大于了左边有序数组的最后一个元素时,内层循环就直接结束了,所以所我们排序的数组中存在着部分有序,那么插入排序算法会很快。

考虑最糟糕的情况,如果输入数组是一个倒置的,那么插入排序的效率和选择排序一样,「时间复杂度是O(n2)」

希尔排序

对于大规模的乱序数组插入排序很慢,是因为它只交换相邻的元素,元素只能一点一点的从数组中移动到正确的位置;插入排序对于部分有序的数组排序是的效率很高;

希尔排序基于这两个特点对插入排序进行了改进;

算法实现的思路

希尔排序高效的原因,在排序之初,各个子数组都很短,子数组排序之后都是部分有序的,这两种情况都很适合插入排序。

常见的初级排序算法有哪些

代码实现:

public class ShellSort implements SortTemplate {      @Override     public void sort(Comparable[] array) {         int gap = 1;         int length = array.length;          while (gap < length / 3) {             gap = 3 * gap + 1;         }          while (gap >= 1) {             for (int i = gap; i < length; i++) {                 for (int j = i; j >= gap && less(array[j], array[j - gap]); j -= gap) {                     exch(array, j, j - gap);                 }             }             gap = gap / 3;         }     }  }

到此,相信大家对“常见的初级排序算法有哪些”有了更深的了解,不妨来实际操作一番吧!这里是编程网网站,更多相关内容可以进入相关频道进行查询,关注我们,继续学习!

阅读原文内容投诉

免责声明:

① 本站未注明“稿件来源”的信息均来自网络整理。其文字、图片和音视频稿件的所属权归原作者所有。本站收集整理出于非商业性的教育和科研之目的,并不意味着本站赞同其观点或证实其内容的真实性。仅作为临时的测试数据,供内部测试之用。本站并未授权任何人以任何方式主动获取本站任何信息。

② 本站未注明“稿件来源”的临时测试数据将在测试完成后最终做删除处理。有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341

软考中级精品资料免费领

  • 历年真题答案解析
  • 备考技巧名师总结
  • 高频考点精准押题
  • 2024年上半年信息系统项目管理师第二批次真题及答案解析(完整版)

    难度     813人已做
    查看
  • 【考后总结】2024年5月26日信息系统项目管理师第2批次考情分析

    难度     354人已做
    查看
  • 【考后总结】2024年5月25日信息系统项目管理师第1批次考情分析

    难度     318人已做
    查看
  • 2024年上半年软考高项第一、二批次真题考点汇总(完整版)

    难度     435人已做
    查看
  • 2024年上半年系统架构设计师考试综合知识真题

    难度     224人已做
    查看

相关文章

发现更多好内容

猜你喜欢

AI推送时光机
位置:首页-资讯-前端开发
咦!没有更多了?去看看其它编程学习网 内容吧
首页课程
资料下载
问答资讯