算法-希尔排序

Posted on | In |

介绍

分析

基本思想:

1
将需要排序的序列划分为若干个较小的序列，对这些序列进行直接插入排序，通过这样的操作可使需要排序的数列基本有序，最后再使用一次直接插入排序对整个数列进行排序

算法描述:

  1. 首先使用元素数量的一半作为增量，划分为n/2个子序列，分别对这些子序列分别进行插入排序
  2. 再原有增量基础上，缩小一般，划分为n/4个子序列，分别对这些子序列分别进行插入排序
  3. 重复上述步骤，知道n/4>=1，对整个序列进行插入排序
C实现
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
/**
 希尔排序
 
 @param a 原数组
 @param len 数组长度
 */
void shellSort(int a[], int len)
{
    int d = len / 2;
    while (d >= 1) {
        for (int i = d; i < len; i++) {
            //序列中的下一个数据
            int x = a[i];
            //序列中前一个数据的序号
            int j = i - d;
            //下一个数大于前一个数
            while (j >= 0 && a[j] > x) {
                //后一个数向前移动
                a[j + d] = a[j];
                //向前比较
                j = j - d;
            }
            //保存数据
            a[j + d] = x;
        }
        //缩小增量
        d /= 2;
    }
    
}

/**
 测试希尔排序
 */
void testShellSort()
{
    int arr[8] = { 19, 3, 10, 9, 16, 11, 28, 26 };
    int len = sizeof(arr)/ sizeof(arr[0]);
    
    printf("希尔排序前:");
    for (int i = 0; i < len; i++) {
        printf("%d ",arr[i]);
    }
    
    shellSort(arr, len);
    
    printf("\n希尔排序后:");
    for (int i = 0; i < len; i++) {
        printf("%d ",arr[i]);
    }
    printf("\n");
}
Swift实现
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
57
58
59
60
61
62
63
64
65
66
class ShellSort {
    
    /// 希尔排序
    ///
    /// - Parameters:
    ///   - a: 原数组
    ///   - len: 数组长度
    func shellSort(a: inout [Int], len: Int) {
        var d = len / 2
        while d >= 1 {
            for i in d..<len {
                let x = a[i]
                var j = i - d
                while j >= 0 && a[j] > x {
                    a[j + d] = a[j]
                    j -= d
                }
                a[j + d] = x
            }
            d /= 2
        }
    }
    
    /// 测试
    func testShellSort() {
        var arr = [ 19, 3, 10, 9, 16, 11, 28, 26 ]
        print("希尔排序前:\(arr)", separator: " ")
        shellSort(a: &arr, len: arr.count)
        print("希尔排序后:\(arr)", separator: " ")
    }
}


class InsertSort {
    
    /// 插入排序
    ///
    /// - Parameters:
    ///   - a: 原数组
    ///   - len: 数组长度
    func insertSort(a: inout [Int], len: Int) {
        for i in 1..<len {
            let temp = a[i];
            var index = i - 1;
            for j in (0...i-1).reversed() {
                if temp < a[j] {
                    a[j + 1] = a[j]
                }
                else {
                    break;
                }
                
                index -= 1
            }
            a[index + 1] = temp
        }
    }
    
    /// 测试
    func testInserSort() {
        var arr = [ 19, 3, 10, 9, 16, 11, 28, 26 ]
        print("插入排序前:\(arr)", separator: " ")
        insertSort(a: &arr, len: arr.count)
        print("插入排序后:\(arr)", separator: " ")
    }
}

总结

时间复杂度:

  • 最差O(n^2)
  • 最优O(n)
  • 平均O(n^1.3)

空间复杂度:

  • O(1)

稳定性:

  • 不稳定