数据结构八大排序算法

数据结构排序算法

分类

直接插入排序

• 核心思想：将数组中所有的元素依次和前面排序好的元素进行比较，如果当前选择的元素比已排序过的元素小，则进行交换，直到所有元素都排序完毕
• 时间复杂度：O(n^2)
• 稳定性：稳定
• 例如：有一个序列4，2，8，0，5，1
  • 第一趟：2与4比较，小于，插入4之前。序列为：2，4，8，0，5，1
  • 第二趟：8与前面的序列比较，大于4，插入4之后。序列不变
  • 第三趟：0与前面的序列比较，小于2，插入2之前。序列为：0，2，4，8，5，1
  • 第四趟：5与前面的序列比较，大于4小于8，插入4之后8之前。序列为：0，2，4，5，8，1
  • 第五趟：1与前面的序列比较，大于0小于2，插入0之后2之前。序列为：0，1，2，4，5，8

希尔排序

• 核心思想：希尔排序是对直接插入排序的加强，先将序列按步长分组，再进行直接插入排序。每次将步长减小一半，直到步长为1时对所有元素进行排序
• 关于步长的选择一般是使用序列长度的1/2
• 时间复杂度：O(n^1.3)(平均)
• 稳定性：不稳定
• 例如：有一个序列9，1，2，5，7，4，8，6，3，5
  • 长度为10，取步长为5
  • 第一趟：由于步长为5，因此9和4比较，1和8比较，2和6比较，5和3比较，7和5比较。小于的话就交换位置。因此第一趟排序后序列为：4，1，2，3，5，9，8，6，5，7
  • 第二趟取步长为2，因此4、2、5、8、5比较，1、3、9、6、7比较。排序后序列为：2，1，4，3，5，6，5，7，8，9
  • 第三趟取步长为1，直接插入排序得到最终序列：1，2，3，4，5，5，6，7，8，9

简单选择排序

• 核心思想：在排序的序列中选择最小(最大)的一个数与第一个数交换位置，然后在剩下的数中选择最小(最大)的数与第二个位置的数交换，以此类推
• 时间复杂度：O(n^2)
• 稳定性：不稳定
• 这个算法较为简单，大家自行推导吧

堆排序

• 核心思想：首先将序列构建为一个大顶堆(小顶堆)，也就是整个序列的最大值(最小值)是堆顶的根结点(关于根结点请自行查找二叉树相关知识)，将根节点的值和堆数组的末尾元素进行交换，此时末尾元素就是最大值(最小值)，然后将剩余元素构成新的堆，得到次大值(次小值)，以此类推
• 时间复杂度：O(nlogn)
• 稳定性：不稳定
• 这个比较复杂，可以参考堆排序详解

冒泡排序

• 核心思想：首先从数组的第一个元素开始到数组最后一个元素为止，对数组中相邻的两个元素进行比较，如果位于数组左端的元素大于数组右端的元素，则交换这两个元素在数组中的位置，此时数组最右端的元素即为该数组中所有元素的最大值。接着对该数组剩下元素进行冒泡排序，直到整个数组有序排列
• 时间复杂度为：O(n^2)
• 稳定性：稳定
• 这个也不多做解释，相信大家都会

快速排序

• 核心思想：从序列中选取一个记录(通常选取第一个记录)为基准值，将序列中比他小的值放在他之前，比他大的值放在他之后，以该基准为分界线分为两个子序列，分别对两个序列进行排序，达到整个序列有序
• 时间复杂度：O(nlogn)
• 稳定性：不稳定
• 举例：有一个序列72，6，57，88，60，42，83，73，48，85。取基准值temp = 72，为了方便理解，这里省略的左指针和右指针的说法
  • 第一趟：从序列后面向前查找小于temp的值为48，将48替换第一位，此时48的位置变为空，再从前向后查找大于temp的值为88，将88替换到此前48留下的空，此时序列为：48，6，57，空，60，42，83，73，88，85
  • 第二趟：继续从序列后面向前查找小于temp的值为42，将其填如前面留下的空位置，此时序列为：48，6，57，42，60，空，83，73，88，85。再从前向后查找大于temp的值，直到空位置时还没有比temp大的值，因此把temp的值72填入空位置，形成序列：48，6，57，42，60，72，83，73，88，85。这时可以发现temp的值前面都是小于他的值，后面都是大于他的值。之后对temp前面的序列和后面的序列分别执行上述步骤即可

归并排序

• 核心思想：将两个有序的数列合并成一个大的有序序列，通过递归的方式，也就是分治的思想
• 时间复杂度：O(nlogn)
• 稳定性：稳定
• 举例：有一个序列5，4，7，9，3，8，2，1
  • 第一趟：先将其从中分为两个序列5，4，7，9和3，8，2，1
  • 第二趟：再将两个序列分为5，4和7，9和3，8和2，1
  • 第三趟：比较值，序列变为4，5，7，9，3，8，1，2
  • 第四趟：分别比较左边序列的值和右边序列的值，序列变为4，5，7，9，1，2，3，8
  • 第五趟：整体合并比较，得出序列1，2，3，4，5，7，8，9
• 可以看一张动图，加深理解

  

基数排序

• 核心思想：利用桶来实现，创建10个桶(因为基数为0～9)，按照基数入桶，例如51的基数是1，62的基数是2，相同的基数排列在上一个后面，全部排列完毕后按桶号从小到大依次取值组成新序列，接下来将十位数作为基数入桶，同样的方法，以此类推
• 稳定性：稳定
• 举例：