常用的排序算法及其思想

十大排序算法

• 冒泡排序
  • 两两交换，直到不进行交换操作
• 选择排序
  • 每次循环在未排序的数列里找到最大或最小
• 插入\直接排序
  • 将待排数字插入已排序的位置里
• 希尔排序
  • 将间隔为n（通常为数组长度的一半）的数字设为一组，对组内进行插入排序，逐渐减小n直至n为1。(依据：对于有序数组，插入排序的时间复杂度低。)
• 归并排序
  • 对数组分组（初始每组一个），两两合并数组，比较两组内的索引节点的大小，插入后移动索引。（创建两个数组来保存待合并数据，插入到原数组）
• 快速排序
  • 分治，每块区域执行操作：将比key大的数字放在右边，比key小的数字放在左边，继续对key的左右区域执行上述操作直至区域内只有两个数字（无监督快速排序，其他两种为单边递归和基本快速排序）
• 堆排序
  • 堆是一种特殊的完全二叉树，当父节点都比子节点小叫最小堆，反之叫最大堆，堆排序就是初始化一个最大堆，取走根节点，将堆尾放到堆首，重新排列子树
• 计数排序
  • 找出最大值与最小值，计算这范围内的数据出现的次数，然后进行还原。
• 桶排序
  • 将数据放在几个有序的桶内，将每个桶内的数据进行排序，最后有序地将每个桶中的数据从小到大依次取出，即完成了排序。
• 基数排序
  • 队列（先进先出）、计数排序的改良，先按个位将各个数字入计数列，然后依次出列，再按下一个数位依次重新入列，再依次出列，重复直到所有数据都没有对应的数位。数字越小越快