一、常见算法之排序算法简单描述_排序算法的问题描述

作者：我家自动化 | 2024-04-11 11:59:06

踩

排序算法的问题描述

  1、冒泡排序 

  基本思想：两两比较，小的上浮，大的下沉。 

  算法描述：对一组数据，两个两个的依次比较，将小数放到前面，大数放到后面（小的上浮，大的下沉） 

  第一次排序：首先比较第1个和第2个数，将小数放前，大数放后。然后比较第2个数和第3个数，将小数放前，大数放后，如此继续，直至比较最后两个数，将小数放前，大数放后。至此第一趟结束，将最大的数放到了最后。 

  第二次排序：仍从第一对数开始比较（因为可能由于第2个数和第3个数的交换，使得第1个数不再小于第2个数），将小数放前，大数放后，一直比较到倒数第二个数（倒数第一的位置上已经是最大的），第二趟结束，在倒数第二的位置上得到一个新的最大数（其实在整个数列中是第二大的数）。 

  时间复杂度： O(n^2) 

  2、选择排序 

  基本思想：遍历选择，位置交换 

  算法描述：对一组数进行遍历，第一次遍历选择出最小的数，与下标为0的数进行交换，第二次从下表为1出开始遍历，从余下的数中选择最小的数与当前下标为1的数进行交换，依次下去 

  时间复杂度：O(n^2) 

  3、插入排序 

  插入排序主要分为：直接插入排序和希尔排序 

  （1）直接插入排序 

  基本思想：有序列和无序列，从无序列中取数插到有序列中相对应的位置 

  算法描述：将一组数分为两块，一块是有序列，一块是无序列，有序列是按照顺序排列的，从无序列中取出一个数a，对有序列进行遍历，找到数a在有序列中应在的位置并插入到有序列中，依次循环。 

  时间复杂度：O(n^2) 

  (2)希尔排序 

  基本思想：选取关键字（增量），分组，插入排序 

  算法描述：第一轮：将一组数通过关键字，分为好几个小组，对每个小组进行插入排序，第二轮：将第一轮后的结果通过关键字再次分为好几个小组，在对每个小组进行插入排序操作，依次执行……直到关键字为1为止 

  关键字（增量）的取值规则：第一次取总长度的一半,第二次取一半的一半,依次累推直到1为止, 

  时间复杂度：O(nlogn) 

  4、 归并排序 

  基本思想：利用分而治之的思想，先分散，在合并 

  算法描述，第一轮：将数组中的元素两两排序合并，第二轮，在第一轮的基础上，在将小组进行两两排序合并，依次类推，直到整个数组排序完成。 

  时间复杂度：O(n log n) 

  5、堆排序 

  基本思想：堆本质是一颗完全二叉树（大顶堆，和小顶堆），构造初始堆，最大最小交换，输出最大值，重新调整大顶堆 

  算法描述：1、首先构造初始堆，即完全二叉树，父节点大于左孩子节点并且大于右孩子节点； 

  2、将最小值和最大值交换位置，输出最大值，然后将预先的数再次调整为大顶堆，依次输出。 

  时间复杂度： 
 O(n log n) 

 
 6、 快速排序 

  基本思想：分治法，1、将原问题分解为若干个规模更小但结构与原问题相似的子问题。 

  2、递归地解这些子问题， 

  3、然后将这些子问题的解组合为原问题的解。 

  算法描述：找一个标准数，将比这个数小的放在左边，将比这个数大的放到右边，对这两组数再次分而治之，找中间的数，将比这个数小的放在左边，将比其大的放到右边，依次类推 直到排序完成为止。 

  时间复杂度： 
 O(n log n) 

 
 常见排序算法的比较： 

本文内容由网友自发贡献，转载请注明出处：【wpsshop博客】