希尔排序
第8节 希尔排序练习题
对于一个int数组，请编写一个希尔排序算法，对数组元素排序。
给定一个int数组A及数组的大小n，请返回排序后的数组。保证元素小于等于2000。
测试样例：
[1,2,3,5,2,3],6
[1,2,2,3,3,5]
Java (javac 1.7)
代码自动补全
1
import java.util.*;
2
3
public class ShellSort {
4
public int[] shellSort(int[] A, int n) {
5
int i, step; //i标识每一组，step标识步长
6
for(step = n / 2; step > 0; step /= 2){ //起始的步长为数组长度的一半
7
for(i = step; i < n; i++){ //当前步长为step,开始插入排序
8
if(A[i] < A[i-step]){ //每个元素与自己组内的数据进行直接插入排序
9
int target = A[i];
10
int j = i; //j指示当前这一组遍历到哪一个元素
11
while(j>0 && A[j-step] > target){
12
A[j] = A[j-step]; //将j-step位置上的元素移到位置j
13
j -= step;
14
if(j-step < 0)//如果j=1,step=3,没有这个if的话，就会数组越界
15
break;
16
}
17
A[j] = target;
18
}
19
}
20
}
21
return A;
22
}
23
}
您的代码已保存
答案正确:恭喜！您提交的程序通过了所有的测试用例
答案正确:恭喜！您提交的程序通过了所有的测试用例