排序算法
2018-05-05，本文 1158 字，阅读全文约需 4 分钟
稳定排序和不稳定排序：
稳定排序：排序后相等元素的前后位置不会变化。
1、插入排序（稳定）
-
直接插入排序（从后向前找到合适位置插入）
就是从第二位数到最后一位， 每一位都跟当前位的前面所有位置的数进行比较放在大小合适的地方，进而实现每一次都是往有序列中插入一个数。 -
二分法插入排序（按二分法找到合适位置插入）
和直接插入排序一样，只是不需要每次比较所有的数，取一半一半进行比较 -
希尔排序（每次取间隔递减的数进行直接插入排序）（不稳定）
直到最后对间隔为1的数组进行直接插入排序
2、选择排序（不稳定）
- 直接选择排序
在要排序的数组中比较每个数，取最小的数放在第一位。然后除去第一位最小的放在第二位。。 - 堆排序
大根堆：父节点大于等于子节点。小根堆：父节点小于等于子节点。
- 建（大根）堆 —— 先从上到下，从左到右将数组中的数据填入，然后，从下到上，从左到右，必须满足父节点大于子节点进行调整，这样就建好一个堆了。
- 取堆顶作为数组最大值，调整堆为大根堆。循环。。
3、交换排序
-
冒泡排序（稳定）
对相邻的数进行比较，将较小的数往上冒，较大的数往下沉，然后就可以去掉最小的那个数，继续冒泡。 -
快速排序（不稳定）
选择第一个或最后一个元素，比较所有元素。分为大小两部分，再在这两个部分进行快速排序。
实现：
第一个元素为基准数，从最后面往前寻找一个小于基准数的位置，从最前面往后寻找一个大于基准数的位置，找到后两者交换位置，交换完继续前进与后退，直到两者相遇，交换相遇点与第一位既可完成第一次快速排序。
然后对左边、右边分别再次进行快速排序。
4、归并排序（稳定）
待排序序列分为若干个子序列，每个子序列是有序的，然后再合并子序列。从小到大比较子序列，小的放入新序列，然后两个子序列的第一个元素继续比较，取小的放入新序列。
5、基数排序（稳定）
先按个位数大小，排序出新的序列
再按十位数大小，将新序列重新排序
。。。
Arrays.sort(T[],Comparator<? super T> c)
内部采用的归并排序，因此是稳定的。
Arrays.sort(int[] a)
内部采用的快速排序，因此是不稳定的。
Collections.sort(List
其他排序
计数排序
先设定好数组长度（数的最大值），值都初始化为0。然后再将数作为下标，出现一次这个下标的值加一，最后将不为0的下标输出既可获得排序。
桶排序
与计数排序类似
- 将待排序的一组数统一的分布在一个范围中，并将这一范围划分成几个子范围，也就是桶
- 将待排序的一组数，分档规入这些子桶，并将桶中的数据进行排序，可以选择任意一种排序算法
- 将各个桶中的数据有序的合并起来