目录
希尔排序法又称缩小增量法。希尔排序法的基本思想是:先选定一个整数,把待排序文件中所有记录分成个组,所有距离为的记录分在同一组内,并对每一组内的记录进行排序。然后,取,重复上述分组和排序的工作。当到达=1时,所有记录在统一组内排好序。
(1)希尔排序是对直接插入排序的优化。
(2)当gap > 1时都是预排序,目的是让数组更接近于有序。当gap == 1时,数组已经接近有序的了,这样就会很快。这样整体而言,可以达到优化的效果。我们实现后可以进行性能测试的对比。
- //希尔排序
- public static void shellSort(int[] array){
- int gap = array.length;
- while(gap > 1){
- shell(array,gap);
- gap /= 2;//增量是多少都可以,随便小伙伴们写
- }
- shell(array,1);
- }
- //有增量的直接插入排序
- //不是一组希尔排序全部排完,是间隔性的,可能是第一组先插一个,第二组再插一个,第一组再插……
- private static void shell(int[] array,int gap){
- for(int i = gap;i < array.length;i++){
- int tmp = array[i];
- int j = i - gap;
- for(;j >= 0;j -= gap){
- if(array[j] > array[j+gap]){
- array[j + gap] = array[j];
- }
- else{
- break;
- }
- }
- array[j + gap] = tmp;
- }
- }
-
-
- public static void main(String[] args) {
- int[] arr = {3,1,2,4,5};
- Sort.shellSort(arr);
- for (int x : arr) {
- System.out.print(x + " ");
- }
- }
时间复杂度 | 空间复杂度 | ||
最好 | 平均 | 最坏 | |
O(N) | O(N^1.3) | O(N^2) | O(1) |
数据有序 | 难以构造出来 |
- public static void main(String[] args) {
-
- int[] arr2 = new int[10000];
- Test.createArray2(arr2);
- long s2 = System.currentTimeMillis();
- Sort.insertSort(arr2);
- long e2 = System.currentTimeMillis();
- System.out.println("直接插入排序的数组逆序的情况:"+(e2 - s2));
-
- int[] arr1 = new int[10000];
- Test.createArray2(arr1);
- long s1 = System.currentTimeMillis();
- Sort.shellSort(arr2);
- long e1 = System.currentTimeMillis();
- System.out.println("希尔排序的数组逆序的情况:"+(e1 - s1));
- }
稳定性:不稳定。
由于增量不同,可能导致本来在后面的元素跑到前面去!