希尔排序
程序员文章站
2022-07-10 21:14:47
...
希尔排序思路概括来说是:分组 + 插入排序.
/**
* 希尔排序
* 思路:希尔排序,是缩小增量排序, 需要分组. 对每个分组实行直接插入排序.
* 最好的情况:O(nlog2n)
* 最坏的情况:O(n ^ 2)
* 不稳定
* 使用情况:中等大小规模
*/
@Test
public void testShellSort(){
int[] arr = {4,2,5,1,2,9,8,3,5,6,2,8};
// 分组 + 直接插入排序.
for(int i=arr.length / 2; i>0; i/=2){
shellSort(arr, i);
}
System.out.println(Arrays.toString(arr));
}
public void shellSort(int[] arr, int d){
for(int i=d; i<arr.length; i++){
int temp = arr[i];
int j;
for(j=i-d; j>=0; j-=d){
if(temp < arr[j]){
arr[j+d] = arr[j];
}else{
break;
}
}
arr[j+d] = temp;
}
}
/**
* 希尔排序
* 思路:希尔排序,是缩小增量排序, 需要分组. 对每个分组实行直接插入排序.
* 最好的情况:O(nlog2n)
* 最坏的情况:O(n ^ 2)
* 不稳定
* 使用情况:中等大小规模
*/
@Test
public void testShellSort(){
int[] arr = {4,2,5,1,2,9,8,3,5,6,2,8};
// 分组 + 直接插入排序.
for(int i=arr.length / 2; i>0; i/=2){
shellSort(arr, i);
}
System.out.println(Arrays.toString(arr));
}
public void shellSort(int[] arr, int d){
for(int i=d; i<arr.length; i++){
int temp = arr[i];
int j;
for(j=i-d; j>=0; j-=d){
if(temp < arr[j]){
arr[j+d] = arr[j];
}else{
break;
}
}
arr[j+d] = temp;
}
}