常见排序算法体系

1. 各种排序算法的复杂度

2. 排序

具体分析各种排序及其复杂度，在综合复杂度及稳定性情况下，通常希尔、快排、归并需要重点掌握

• 冒泡排序 Bubble Sort

  它是一种简单的排序算法，它会遍历若干次要排序的数列，每次遍历时，它都会从前往后依次的比较相邻两个数的大小，如果前者比后者大，则交换它们的位置，这样一次遍历后，最大的元素就在数列的末尾，采用相同的方法遍历时，第二大的元素就被排列在最大元素之前，重复此操作，知道整个数列都有序为止

• 快速排序 Quick Sort

  它的基本思想是：选择一个基准数，通过一趟排序将要排序的数据分割成独立的两部分，其中一部分所有数据都比另一部分的所有数都要小，然后，再按此方法对两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列

• 插入排序 Insertion Sort

  直接插入排序(Straight Insertion Sort)的基本思想是：把n个带排序的元素堪称一个有序表和一个无序表。开始时有序表只包含一个元素，无序表包含n-1个元素，排序的过程中每次从无序表中去除第一个元素，将它插入到有序表中的适当位置，使之称为新的有序表，重复n-1词可完成排序过程

• Shell排序 Shell Sort

  希尔排序实质上是一种分组插入方法，它的基本思想是：对于n个带排序的数列，去一个小于n的整数gap(gap被称为步长)，将带排序元素分成若干个组子序列，所有距离为gap的倍数的记录放在同一个组中，然后，对各组内的元素进行直接插入排序。这一趟排序完成之后，每一个组的元素都是有序的，
  然后减少gap值，重复执行上述的分组和排序。当gap = 1时，整个数列就是有序的。

• 选择排序 Selection Sort

  基本思想是：首先在为排序的数列中找到最小/最大元素，然后将其放到数列的起始位置；接着，再从剩余为排序的元素中继续寻找最小/最大元素，然后放到已排序序列后面，以此类推，知道所有元素均排序完成

• 堆排序 Heap Sort

  利用堆这种数据结构所设计的一种排序算法。堆十一近似我完全二叉树的结构，并同时满足堆积的性质：即子节点的键值所索引总是小于(或大于)它的父节点

• 桶排序 Bucket Sort

  统排序的原理很简单，将数组分到有限数量的桶里面，每个桶在分别排序（有可能使用别的排序算法或者递归方式继续使用桶排序进行排序）

• 基数排序 Radix Sort

  基本思想：将整数按位数分割成不同的数字，然后按每个位数分别比较。具体做法是：将所有带比较数值统一为同样的数位长度，数位较短的前面补0，然后从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成之后，数列就变成了一个有序序列

3. 学习推荐

• 学习排序：动画展示排序

• 整体性比较好的系列：数据结构与算法系列 目录