数据结构—排序

内部排序：指待排序记录全部存放在内存中排序的过程。
外部排序：指待排序记录的数量很大，以至于内存不能容纳全部记录，在排序过程中尚需对外存进行访问的过程。

插入排序

1.直接插入排序
先将序列中的第一个记录看成一个有序列，然后从第二个记录开始，逐个进行插入，直至整个序列有序，排序过程为n-1躺插入。

• 时间效率：因为在最坏情况下，所有元素的比较次数总和为（0+1+...+n-1)—>O(n的平方），时间复杂度O(n的平方）。
• 空间效率：仅占用1个缓冲单元—O(1)

• 算法的稳定性：稳定
  2、希尔排序

  
  

示意图

选择排序

每一次从待排序的数据元素中选出最小的一个元素，存放在已排序列的后面，直到全部待排序的数据元素排完。

• 优点：实现简单
• 缺点：每趟只能确定一个元素，表长为n时需要n-1趟
• 前提：顺序存储结构

1、直接选择排序
在所有记录中选出最小的记录，把它与第一个记录交换，然后在剩余的记录内选出最小的记录与第二个记录交换...依次类推。

示意图

2、堆排序

示意图

堆排序的最坏时间复杂度为O(n倍的log以2为底的n次方），堆排序平均性能接近最坏性能。
堆排序的辅助空间为O(1)。

交换排序

1、冒泡排序

• 时间效率：O(n的平方)
• 空间效率：O(1)
• 稳定性：稳定

2、快速排序

• 优点：因为每趟可以确定不止一个元素的位置，而且呈指数增加，所以特别
  示意图

快速排序最坏时间复杂度O(n的平方），最好时间复杂度为O(n倍的log以2为底的n次方）

归并排序

可以把一个长度为n的无序序列看成是n个长度为1的有序子序列，首先做两两归并，得到n/2个长度为2的有序子序列；再做两两归并，如此重复，直到最后得到一个长度为n的有序序列。

示意图

时间效率：O(nLog以2为底的n次方)
空间效率：O(n)
稳定性：稳定

算法复杂性比较

排序算法时间复杂度表