江苏龙网

  1. 主页 > 生活百科 > >

十大排序算法，你会几种？

排序算法

今天我们就来讨论面试官最喜欢问到的排序算法吧，从冒泡排序、选择排序、插入排序等十大排序算法的排序步骤、代码实现两个方面入手，彻底搞清实现原理，保证面试道路一路畅通 。
01 排序算法的概述所谓排序算法，就是通过特定的算法因式将一组或多组数据按照一定模式进行重新排序 。
这种新序列遵循着一定的规则，体现出一定的规律，因此，经处理后的数据便于筛选和计算，大大提高了计算效率 。
02 排序算法的分类

十大排序算法，你会几种？

文章插图
 
03评价标准（1）时间复杂度：即从序列的初始状态到经过排序算法的变换移位等操作变到最终排序好的结果状态的过程所花费的时间度量 。
（2）空间复杂度：就是从序列的初始状态经过排序移位变换的过程一直到最终的状态所花费的空间开销 。
（3）稳定性：稳定性是不管考虑时间和空间必须要考虑的问题，往往也是非常重要的影响选择的因素 。
04 实现步骤与代码冒泡排序（Bubble Sort）冒泡排序是一种简单直观的排序算法 。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来 。走访数列的工作是重复地进行直到没有再需要交换的数据，也就是说该数列已经排序完成 。这个算法的名字由来是因为越小的元素会经由交换慢慢"浮"到数列的顶端 。
（1）算法步骤
【十大排序算法，你会几种？】步骤1：比较相邻的元素 。如果第一个比第二个大，就交换他们两个；步骤2：对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对 。这步做完后，最后的元素会是最大的数；步骤3：针对所有的元素重复以上的步骤，除了最后一个；步骤4：重复步骤1~3，直到排序完成；
（2）过程演示
十大排序算法，你会几种？

文章插图
 
（3）代码实现
public class BubbleSort implements IArraySort {@Overridepublic int[] sort(int[] sourceArray) throws Exception {// 对 arr 进行拷贝，不改变参数内容int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);for (int i = 1; i < arr.length; i++) {// 设定一个标记，若为true，则表示此次循环没有进行交换，也就是待排序列已经有序，排序已经完成 。boolean flag = true;for (int j = 0; j < arr.length - i; j++) {if (arr[j] > arr[j + 1]) {int tmp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = tmp;flag = false;}}if (flag) {break;}}return arr;}}选择排序（Selection Sort）选择排序是一种简单直观的排序算法，无论什么数据进去都是 O(n²) 的时间复杂度 。所以用到它的时候，数据规模越小越好 。
（1）算法步骤
步骤1：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置；步骤2：再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾；步骤3：重复步骤2，直到所有元素均排序完毕；
（2）过程演示
十大排序算法，你会几种？

文章插图
 
（3）代码实现
public class SelectionSort implements IArraySort {@Overridepublic int[] sort(int[] sourceArray) throws Exception {int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);// 总共要经过 N-1 轮比较for (int i = 0; i < arr.length - 1; i++) {int min = i;// 每轮需要比较的次数 N-ifor (int j = i + 1; j < arr.length; j++) {if (arr[j] < arr[min]) {// 记录目前能找到的最小值元素的下标min = j;}}// 将找到的最小值和i位置所在的值进行交换if (i != min) {int tmp = arr[i];arr[i] = arr[min];arr[min] = tmp;}}return arr;}}插入排序（Insertion Sort）插入排序的算法描述是一种简单直观的排序算法 。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入 。插入排序在实现上，通常采用in-place排序（即只需用到O(1)的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间 。
（1）算法步骤
步骤1：从第一个元素开始，该元素可以认为已经被排序；步骤2：取出下一个元素，在已经排序的元素序列中从后向前扫描；步骤3：如果该元素（已排序）大于新元素，将该元素移到下一位置；步骤4：重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；步骤5：将新元素插入到该位置后；步骤6：重复步骤2~5；


推荐阅读


上一篇：在头条上怎么赚钱？告诉你五种方法，绝对干货

下一篇：吸引人的文案句子有哪些？