本帖最后由 天下 于 2013-12-8 10:39 编辑
献丑了:
- /**希尔排序的原理:根据需求,如果你想要结果从大到小排列,它会首先将数组进行分组,然后将较大值移到前面,较小值
- * 移到后面,最后将整个数组进行插入排序,这样比起一开始就用插入排序减少了数据交换和移动的次数,可以说希尔排序是加强
- * 版的插入排序
- * 拿数组5, 2, 8, 9, 1, 3,4来说,数组长度为7,当increment为3时,数组分为两个序列
- * 5,2,8和9,1,3,4,第一次排序,9和5比较,1和2比较,3和8比较,4和比其下标值小increment的数组值相比较
- * 此例子是按照从大到小排列,所以大的会排在前面,第一次排序后数组为9, 2, 8, 5, 1, 3,4
- * 第一次后increment的值变为3/2=1,此时对数组进行插入排序,
- */
- public class ShellSort {
- public static void shellSort(int[] arr) {
- int j = 0;
- int temp = 0;
- for (int increment = arr.length / 2; increment > 0; increment /= 2) {
-
- for (int i = increment; i < arr.length; i++) {
- temp = arr[i];
- for (j = i; j >= increment; j -= increment) {
- if(temp > arr[j - increment]){
- arr[j] = arr[j - increment];
- }else{
- break;
- }
- }
- arr[j] = temp;
- }
- }
- }
-
- public static void main(String[] args) {
- int[] arr = new int[] {5, 2, 8, 9, 1, 3,4};
- int[] arr1=new int[]{ 5, 2, 8, 6, 9, 7, 1, 3, 10, 4};
- System.out.println("未排序前");
-
- print(arr);
- System.out.println();
- print(arr1);
-
- shellSort(arr);
- shellSort(arr1);
-
- System.out.println("\n排序后");
- print(arr);
- System.out.println();
- print(arr1);
-
- }
- public static void print(int[] arr){
- for(int i: arr){
- System.out.print(i+" ");
- }
- }
-
- }
- 打印结果:
- 未排序前
- 5 2 8 9 1 3 4
- 5 2 8 6 9 7 1 3 10 4
- 排序后
- 9 8 5 4 3 2 1
- 10 9 8 7 6 5 4 3 2 1
复制代码
|