4.希尔排序(相对较快,不稳定)
思想:
先确定一个间隔,我们从0开始,每经过一个间隔取一个数,把这些数分成一组,把这一组数用插入排序排好。然后将间隔逐渐变小,循环该过程。
为什么比插入排序的效率高?
因为如果1在比较后面的位置,它要排到最前面必须经过很多次交换。如果用希尔排序,因为有间隔,所以只需要很少的次数就能把1排到前面。这就是它能提高效率的地方。希尔排序也叫改进排序。
希尔排序在间隔较大的时候交换的次数比较少,间隔小的时候交换的距离比较近。但希尔排序是跳着排的,所以不稳定。
实现:
//希尔排序(也叫改进排序,是对插入排序的改进;时间复杂度为n**1.3,空间为1,不稳定) //思想:将插入排序的每次插入后一个改成间隔为n的插入; //即:逻辑上将间隔为N的数取出来组成一个新的数组,然后进行插入排序 //然后逐渐将间隔减小,最终使用间隔为1的时候即为插入排序 //因为是跳着排的,所以希尔排序不稳定 //改进点:1.间隔大时,每次交换的步数变大了 // 2.间隔小时,交换的次数变少了 //N最大取多少:1.希尔第一次N取数组长度的1/2,每次为N*1/2 // 2.Knuth序列 n=3k+1(<=length) 初始k=1;一般会更快 int k=1; while(3*k+1<a.length){ k=3*k+1; } while(k>0) { for (int j = k; j < a.length; j++) { //一次以k为间隔的插入排序 for (int i = j; i > k - 1; i-=k) { if (a[i] < a[i - k]) swap(a, i, i - k); } } k=(k-1)/3; }