近來很熱啊，菜鳥準備放水了。在寫一篇夏雨的腦洞文，喜歡雨。
相關(guān)的原理與細節(jié)，看視頻，我講不清楚了，汗啊。
python03-05-05希爾排序
計算機科學9.2&9.3希爾排序與堆排序（浙江大學陳越、何欽銘
堆的形狀如下
堆.jpg
采用大根堆，根結(jié)點從0開始，其左兒子為2i+1,右兒子為2i+2, 在[0,(n-1)/2]之間循環(huán)建立堆。
相關(guān)的code
package day20180728;
public class DuiSort {
/**
*
建大根堆的函數(shù)。
*/
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);
}
}
結(jié)果如下
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，
相關(guān)的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+"次結(jié)果");
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);
}
}
結(jié)果
11 6 8 666 -5 33 88 6
第4次結(jié)果
-5 6 8 666 11 33 88 6
第5次結(jié)果
-5 6 8 666 11 33 88 6
第6次結(jié)果
-5 6 8 666 11 33 88 6
第7次結(jié)果
-5 6 8 6 11 33 88 666
第2次結(jié)果
-5 6 8 6 11 33 88 666
第3次結(jié)果
-5 6 8 6 11 33 88 666
第4次結(jié)果
-5 6 8 6 11 33 88 666
第5次結(jié)果
-5 6 8 6 11 33 88 666
第6次結(jié)果
-5 6 8 6 11 33 88 666
第7次結(jié)果
-5 6 8 6 11 33 88 666
第1次結(jié)果
-5 6 8 6 11 33 88 666
第2次結(jié)果
-5 6 8 6 11 33 88 666
第3次結(jié)果
-5 6 6 8 11 33 88 666
第4次結(jié)果
-5 6 6 8 11 33 88 666
第5次結(jié)果
-5 6 6 8 11 33 88 666
第6次結(jié)果
-5 6 6 8 11 33 88 666
第7次結(jié)果
-5 6 6 8 11 33 88 666
-5 6 6 8 11 33 88 666
