文档介绍：概述
因为健忘,加上对各种排序算法理解不深刻,过段时间面对排序就蒙了。所以决定对我们常见的这几种排序算法进行统一总结。首先罗列一下常见的十大排序算法:
我们讨论的这八大排序算法的实现可以参考我的Github:SortAlgorithms,其中也包括了排序测试模块[]和排序算法对比模块[],大家可以试运行。
它们都属于内部排序,也就是只考虑数据量较小仅需要使用内存的排序算法,他们之间关系如下:
一、直接插入排序(Insertion Sort)
插入排序的设计初衷是往有序的数组中快速插入一个新的元素。它的算法思想是:把要排序的数组分为了两个部分, 一部分是数组的全部元素(除去待插入的元素), 另一部分是待插入的元素; 先将第一部分排序完成, 然后再插入这个元素. 其中第一部分的排序也是通过再次拆分为两部分来进行的.
插入排序由于操作不尽相同, 可分为 直接插入排序 , 折半插入排序(又称二分插入排序), 链表插入排序 , 希尔排序 。我们先来看下直接插入排序。
1、基本思想
直接插入排序的基本思想是:将数组中的所有元素依次跟前面已经排好的元素相比较,如果选择的元素比已排序的元素小,则交换,直到全部元素都比较过为止。
2、算法描述
一般来说,插入排序都采用in-place在数组上实现。具体算法描述如下:
①. 从第一个元素开始,该元素可以认为已经被排序 
②. 取出下一个元素,在已经排序的元素序列中从后向前扫描 
③. 如果该元素(已排序)大于新元素,将该元素移到下一位置 
④. 重复步骤3,直到找到已排序的元素小于或者等于新元素的位置 
⑤. 将新元素插入到该位置后 
⑥. 重复步骤②~⑤
如果比较操作的代价比交换操作大的话,可以采用二分查找法来减少比较操作的数目。该算法可以认为是插入排序的一个变种,称为二分查找插入排序。
3、代码实现
/**
* 插入排序
*
* 1. 从第一个元素开始,该元素可以认为已经被排序
* 2. 取出下一个元素,在已经排序的元素序列中从后向前扫描
* 3. 如果该元素(已排序)大于新元素,将该元素移到下一位置
* 4. 重复步骤3,直到找到已排序的元素小于或者等于新元素的位置
* 5. 将新元素插入到该位置后
* 6. 重复步骤2~5
* ***@param arr 待排序数组
*/
public static void insertionSort(int[] arr){
for( int i=0; i<-1; i++ ) {
for( int j=i+1; j>0; j-- ) {
if( arr[j-1] <= arr[j] )
break;
int temp = arr[j]; //交换操作
arr[j] = arr[j-1];
arr[j-1] = temp;
("Sorting: " + (arr));
}
}
}
直接插入排序复杂度如下:
平均时间复杂度
最好情况
最坏情况
空间复杂度
O(n²)
O(n²)
O(n²)
O(1)
Tips: 由于直接插入排序每次只移动一个元素的位, 并不会改变值相同的元素之间的排序, 因此它是一种稳定排序。
二、希尔排序(Shell Sort)
第一个突破O(n^2)的排序算法;是简单插入排序的改进版;它与插入排序的不同之处在于,它会优先比较距离较远的元素。
希尔排序,也称递减增量排序算法,1959年Shell发明。是插入排序的一种高速而稳定的改进版本。
希尔排序是先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序,待整个序列中的记录“基本有序”时,再对全体记录进行依次直接插入排序。
1、基本思想
将待排序数组按照步长gap进行分组,然后将每组的元素利用直接插入排序的方法进行排序;每次再将gap折半减小,循环上述操作;当gap=1时,利用直接插入,完成排序。
可以看到步长的选择是希尔排序的重要部分。只要最终步长为1任何步长序列都可以工作。一般来说最简单的步长取值是初次取数组长度的一半为增量,之后每次再减半,直到增量为1。更好的步长序列取值可以参考维基百科。
2、算法描述
①. 选择一个增量序列t1,t2,…,tk,其中ti>tj,tk=1;(一般初次取数组半长,之后每次再减半,直到增量为1) 
②. 按增量序列个数k,对序列进行k 趟排序; 
③. 每趟排序,根据对应的增量ti,将待排序列分割成若干长度为m 的子序列,分别对各子表进行直接插入排序。仅增量因子为