近来很热啊，菜鸟准备放水了。在写一篇夏雨的脑洞文，喜欢雨。
相关的原理与细节，看视频，我讲不清楚了，汗啊。
python03-05-05希尔排序
计算机科学9.2&9.3希尔排序与堆排序（浙江大学陈越、何钦铭
堆的形状如下
堆.jpg
采用大根堆，根结点从0开始，其左儿子为2i+1,右儿子为2i+2, 在[0,(n-1)/2]之间循环建立堆。
相关的code
package day20180728;
public class DuiSort {
/**
*
建大根堆的函数。
*/
public static void heap(int[] arr,int k,int n){
int i=k,j=2*i+1;
while(j<n) //筛选进行到叶子的判别方法。
{
if(j<n-1&&arr[j]<arr[j+1])
{
j=j+1;
}
if(arr[i]<arr[j])
{
int temp=arr[j];
arr[j]=arr[i];
arr[i]=temp;
i=j;
j=2*i+1;
}else {
break;
}
}
}
public static void heapSort(int[] arr,int n)
{
int temp,i=0;
for(i=(n-1)/2; i>=0; i--)
{
heap(arr,i,n);
display(arr);
}
for(i=1; i<n; i++)
{
temp=arr[0];
arr[0]=arr[n-i];
arr[n-i]=temp;
heap(arr,0,n-i);
System.out.println("第"+i+"建堆的情况:");
display(arr);
}
}
public static void display(int[] arr)
{
for(int i:arr)
{
System.out.print(i+" ");
}
System.out.println();
}
public static void main(String[] args) {
int[] arr= {11,6,8,666,-5,33,88,6};
heapSort(arr,arr.length);
}
}
结果如下
11 6 8 666 -5 33 88 6
11 6 88 666 -5 33 8 6
11 666 88 6 -5 33 8 6
666 11 88 6 -5 33 8 6
第1建堆的情况:
88 11 33 6 -5 6 8 666
第2建堆的情况:
33 11 8 6 -5 6 88 666
第3建堆的情况:
11 6 8 6 -5 33 88 666
第4建堆的情况:
8 6 -5 6 11 33 88 666
第5建堆的情况:
6 6 -5 8 11 33 88 666
第6建堆的情况:
6 -5 6 8 11 33 88 666
第7建堆的情况:
-5 6 6 8 11 33 88 666
shell排序
就是改变增量的插入排序，这里增量采用n/2递归到0，
相关的code
package day20180728;
public class ShellSort {
public static void shell(int[] arr,int k)
{
for(int i=k; i<arr.length; i=i+1)
{
int temp=0;
temp=arr[i];
int m=i-k;
//这里的判断index是坑，先判断它，不然会下标越界。
while(m>=0&&arr[m]>temp)
{
arr[m+k]=arr[m];
m=m-k;
}
if(m!=i)
arr[m+k]=temp;
System.out.println("第"+i+"次结果");
display(arr);
}
}
public static void shellSort(int[] arr)
{
for(int k=arr.length/2; k>0; k=k/2)
shell(arr,k);
}
public static void display(int[] arr)
{
for(int i:arr)
{
System.out.print(i+" ");
}
System.out.println();
}
public static void main(String[] args) {
int[] arr= {11,6,8,666,-5,33,88,6};
display(arr);
shellSort(arr);
display(arr);
}
}
结果
11 6 8 666 -5 33 88 6
第4次结果
-5 6 8 666 11 33 88 6
第5次结果
-5 6 8 666 11 33 88 6
第6次结果
-5 6 8 666 11 33 88 6
第7次结果
-5 6 8 6 11 33 88 666
第2次结果
-5 6 8 6 11 33 88 666
第3次结果
-5 6 8 6 11 33 88 666
第4次结果
-5 6 8 6 11 33 88 666
第5次结果
-5 6 8 6 11 33 88 666
第6次结果
-5 6 8 6 11 33 88 666
第7次结果
-5 6 8 6 11 33 88 666
第1次结果
-5 6 8 6 11 33 88 666
第2次结果
-5 6 8 6 11 33 88 666
第3次结果
-5 6 6 8 11 33 88 666
第4次结果
-5 6 6 8 11 33 88 666
第5次结果
-5 6 6 8 11 33 88 666
第6次结果
-5 6 6 8 11 33 88 666
第7次结果
-5 6 6 8 11 33 88 666
-5 6 6 8 11 33 88 666
