一、排序的概念以及运用
1.1 排序的概念
排序 ：所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。
稳定性 ：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j] ，且 r[i] 在 r[j] 之前，而在排序后的序列中， r[i] 仍在 r[j] 之前，则称这种排序算法是稳定的；否则称为不稳定的。
内部排序：数据元素全部放在内存中的排序。
外部排序 ：数据元素太多不能同时放在内存中，根据排序过程的要求不能在内外存之间移动数据 的排序。
1.2 常见的排序算法
二、七大经典排序算法的实现
2.1 插入排序
2.1.1 基本思想
直接插入排序是一种简单的插入排序法，其基本思想是： 把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列 。实际中我们玩扑克牌时，就用了插入排序的思想。
2.1.2 直接插入排序
当插入第 i(i>=1) 个元素时，前面的 array[0],array[1],…,array[i-1] 已经排好序，此时用 array[i] 的排序码与 array[i-1],array[i-2],…的排序码顺序进行比较，找到插入位置即将 array[i] 插入，原来位置上的元素顺序后移。
2.1.3 插入排序实现代码
public static void insertSort(int[] array){ for (int i = 1; i < array.length ; i++) { int tmp=array[i]; int j = i-1; for (; j >=0 ; j--) { if(array[j]>tmp){ array[j+1]=array[j]; }else{ break; } } array[j+1]=tmp; } }
2.1.4 直接插入排序的特性总结
- 元素集合越接近有序，直接插入排序算法的时间效率越高
- 时间复杂度：O(N^2)
- 空间复杂度：O(1)，它是一种稳定的排序算法
- 稳定性：稳定
2.2 希尔排序
2.2.1 基本思想
希尔排序法又称缩小增量法。希尔排序法的基本思想是： 把待排序文件中所有记录分成多个组，并对每一组内的记录进行排序。然后，取，重复上述分组和排序的工作。最后，所有记录在同一组内排好序。
2.2.2 希尔排序实现代码
public static void shellSort(int[] array){ int gap= array.length; while(gap>1){ gap/=2; shell(array,gap); } } public static void shell(int[] array,int gap){ for (int i = gap; i <array.length ; i++) { int tmp=array[i]; int j = i-gap; for (; j >=0 ; j-=gap) { if(array[j]>tmp){ array[j+gap]=array[j]; }else{ break; } } array[j+gap]=tmp; } }
2.2.3 希尔排序特性总结
希尔排序是对直接插入排序的优化。
当gap > 1时都是预排序，目的是让数组更接近于有序。当gap == 1时，数组已经接近有序的了，这样就会很快。整体而言，可以达到优化的效果。
希尔排序的时间复杂度不好计算，因为gap的取值方法很多，导致很难去计算，因此在好些树中给出的希尔排序的时间复杂度都不固定。
稳定性：不稳定
2.3 选择排序
2.3.1 基本思想
每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完 。
2.3.2 选择排序
在元素集合array[i]--array[n-1]中选择关键码最大(小)的数据元素
若它不是这组元素中的最后一个(第一个)元素，则将它与这组元素中的最后一个（第一个）元素交换
在剩余的array[i]--array[n-2]（array[i+1]--array[n-1]）集合中，重复上述步骤，直到集合剩余1个元素
2.3.3 选择排序实现代码
public void selectSort(int[] array){ for (int i = 0; i < array.length; i++) { int smallest=i; int j = i+1; for (; j < array.length; j++) { if(array[j]<array[smallest]){ smallest=j; } } swap(array,i,smallest); } } public static void swap(int[] array,int i,int j){ int tmp=array[i]; array[i]=array[j]; array[j]=tmp; }
2.3.4 选择排序特性总结
- 直接选择排序思考非常好理解，但是效率不是很好。实际中很少使用
- 时间复杂度：O(N^2)
- 空间复杂度：O(1)
- 稳定性：不稳定
