八大排序算法

2021年09月15日 阅读数:1
这篇文章主要向大家介绍八大排序算法,主要内容包括基础应用、实用技巧、原理机制等方面,希望对大家有所帮助。
  1. 交换排序 -- 冒泡排序
  2. 交换排序 -- 快速排序
  3. 选择排序 -- 简单选择排序
  4. 选择排序 -- 堆排序
  5. 插入排序 -- 简单插入排序
  6. 插入排序 -- 希尔排序
  7. 归并排序
  8. 基数排序

 

1.冒泡排序

指定一个元素和第二个元素进行比较,将下的放在前面,而后再让第二个和三个进行比较,算法

将最小的放在前面,每次对应的(i和j+1),直到最后只剩下一个元素,则结束,每次也要固定最大的元素数组

八大排序算法_插入排序

 

 

 2.快速排序

是对冒泡排序的改进数据结构

在排序数组中随机找出一个数,通常取第一个或最后一个,称为基准数。ide

而后将比基准数小的排在左边,大的排在右边。和基准数进行交换,交换完后左边都是比基准数小的,优化

右边都是比基准数大的,这样就至关于将一个数组分红了两个子数组,spa

而后按一样的方法把子数组分红更小的数组,直到不能分解为止设计

  1. 选择一个基准位
  2. 从后往前遍历找到小于基准位的值
  3. 从前日后遍历找到大于基准位的值
  4. 将两个值交换
  5. 继续从两个位置从后往前找,从前日后找,交换
  6. 直到相遇,将碰头的值与基准值交换,将交换后中间的那个值固定
  7. 这时就分红分红了两个子序列,重复上面的操做

八大排序算法_插入排序_02

 

 3.简单选择排序

  • 从原始数据中选择最小的数字,将其和位于第一个位置的数据交换位置
  • 从剩下的n-1个数据中选择次小的一个与第二个位置的数据交换位置
  • 而后不断的重复,直到最后两个数据完成交换

八大排序算法_基数排序_03

 

4.堆排序

利用堆这种数据结构而设计的一种选择排序算法,难点在于二叉树的顺序数组存储到大顶堆(小顶堆)的转换3d

例如数组arr[1,2,5,4,6,3,7]blog

1.构建初始堆排序

八大排序算法_希尔排序_04

 

2.转换成大顶堆

八大排序算法_插入排序_05

 

3.交换堆顶和末尾元素,取出最大元素

八大排序算法_数组_06

 

4。继续调整堆为大顶堆,而后重复上述,取出次大元素

八大排序算法_基数排序_07

 

 5.继续重复,取出第三大元素,一直到取完全部元素

 

5.简单插入排序

1.把数组分为三个部分,有序段、待插入元素和无序段,最开始有序段只有第一个元素

2.把待插入元素放入有序段的段尾,进行依次比较大小,而后交换位置

八大排序算法_数组_08

优化措施:并无下降算法的时间复杂度,可是减小了许多无谓的交换

例如这里的第四次插入,3与6先交换,3与5再交换,3与4又交换

咱们能够把3保存起来,把4,5,6逐一复制到交换后的位置,而后再将3插入到交换后的位置,这样就不用三次交换了

 

6.希尔排序

希尔排序是简单插入排序的升级版

1.设置一个增量n/2(n为数组长度),将间隔为n/2的元素视为一组,而后组内进行简单插入排序

2.而后将增量缩小为n/4,再在组内进行简单插入排序

3.重复,直到增量为1,全部的元素为一个组,再次进行简单插入排序

八大排序算法_希尔排序_09

 

7.归并排序

 将一个数组的进行两两分组,进行组内排序,排好序后两个数为一个元素,两两元素内的全部数进行比较排序,

而后重复,最后只有两个元素,合并以后再比较排序

八大排序算法_数组_10

 

8.基数排序

基数排序是桶排序的推广,适合有不一样的数字进行比较,

1.先到10个桶,0~9

2.第一轮排序按照个位数字大小排序,而后再按照十位排序,把未放入桶中的取出来,按顺序保存

3.而后千位排序,把未放入桶中的取出来,按顺序保存

4.重复到没有位数,把保存好的数字取出来就排序好了

八大排序算法_冒泡排序_11