/
ShellSort.java
56 lines (54 loc) · 1.42 KB
/
ShellSort.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
package com.algorithm.sort;
/*
* 希尔排序
* 时间复杂度:
* 最好:0(n)
* 最坏:0(n^2)
* 平均:0(n^1.3)
* 稳定性:不稳定
*/
public class ShellSort {
public static void main(String arg[]){
int [] a ={10,2,4,7,15,8,9,1};
ShellSort.sort2(a, a.length);
for(int v:a){
System.out.print(" "+v);
}
}
public static void sort(int [] array,int n){
int gap,i,j;
for( gap=n / 2;gap>0;gap /= 2){//步长再递减
for(i=0;i<gap;i++){//循环每一组
for(j=i+gap;j<n;j+=gap){//每组的元素
if(array[j]<array[j-gap]){
//直接插入
int temp = array[j];
int key = j-gap;
while(key>=0 && array[key]>temp ){
array[key+gap]=array[key];
key-=gap;
}
array[key+gap] =temp;
}
}
}
}
}
public static void sort2(int a[], int n)
{
int j, gap;
for (gap = n / 2; gap > 0; gap /= 2)
for (j = gap; j < n; j++)//从数组第gap个元素开始
if (a[j] < a[j - gap])//每个元素与自己组内的数据进行直接插入排序
{
int temp = a[j];
int k = j - gap;
while (k >= 0 && a[k] > temp)
{
a[k + gap] = a[k];
k -= gap;
}
a[k + gap] = temp;
}
}
}