算法导论之插入排序

逃离我推掉我的手 2022-03-21 11:10 233阅读 0赞

比如我们对下面的进行排序，排序过程如下

\--------------------------------------------每次进行比较2位，然后插到合适的位置

下面先附上代码

//
    //  main.cpp
    //  算法导论
    //
    //  Created by SJCHEN on 2019/1/19.
    //  Copyright © 2019 SJCHEN. All rights reserved.
    //
    
    #include <iostream>
    #include <string>
    using namespace std;
    int len = 0;
    
    void InsertSort(int arr[])
    {
        for (int j = 1; j < len; ++j) {
            int key = arr[j];
            int i = j - 1;
            while (i >= 0 && arr[i] < key) {
                arr[i + 1] = arr[i];
                i = i - 1;
            }
            arr[i + 1] = key;
        }
    }
    
    int main()
    {
        int arr[] = {5,2,4,6,1,3};
        len = sizeof(arr) / sizeof(arr[0]);//计算数组的长度
        InsertSort(arr);
        for (int i = 0; i < len; i++) {
            cout << arr[i] << " ";
        }
        cout << endl;
        return 0;
    }

i>=0 && arr\[i\] > key

我们可以看到插入排序的时间复杂度为O(n^2), 我们有没有什么方法可以改进呢？、

答案就是二分插入排序。（如果二分排序不懂的话，可以去看下我前面写的）,我们不在一个一个的比较大小，而是在前面有序的情况下直接进行 二分查找，

二分插入排序的时间复杂度为O(nlgn)。

//
    //  main.cpp
    //  算法导论
    //
    //  Created by SJCHEN on 2019/1/19.
    //  Copyright © 2019 SJCHEN. All rights reserved.
    //
    
    #include <iostream>
    using namespace std;
    int arr[] = {1,5,2,7,6,8,9,3};
    int len = sizeof(arr) / sizeof(arr[0]);
    
    int Binary(int start, int end, int val)
    {
        for (int j = start; j <= end; j++)
            if (arr[j] > val)//和二分查找不同，这里是大于（升序）
                return j;
        return -1;
    }
    
    int BinarySearch(int start, int end, int val)
    {
        if (start == 0 && end == 0 && arr[0] > val)//特殊情况，只有一位元素
            return 0;
        if (start < end) {
            int mid = (start + end) / 2;
            if (arr[mid] > val) {//递归左边
                BinarySearch(start, mid, val);
                return Binary(start, mid, val);
            }
            else {//递归右边
                BinarySearch(mid + 1, end, val);
                return Binary(mid + 1, end, val);
            }
        }
        return -1;
    }
    
    void BinaryInsertSort(int arr[])
    {
        for (int j = 1; j < len; j++) {
            int key = arr[j];
            int i = j - 1;
            int k = BinarySearch(0,i,key);
            if (k != -1) {
                for (int s = i; s >= k; s--)
                    arr[s + 1] = arr[s];
                arr[k] = key;
            }
        }
    }
    
    int main()
    {
        BinaryInsertSort(arr);
        for (int i = 0; i < len; i++) {
            cout << arr[i] << " ";
        }
        cout << endl;
        return 0;
    }