折半插入排序

直接插入排序的改进。 比较次数减少，移动次数增加，时间复杂度不变。

代码

#include<iostream>
using namespace std;

void BinSort(int num[],int n) {
    int low, high,temp,mid;
    for (int i = 0; i < n; i++) {
        low = 0;
        temp = num[i];
        high = i - 1;
        while (low <= high) {
            mid = (low + high) / 2;
            if (temp < num[mid]) high = mid - 1;
            else low = mid + 1;
        }
        for (int j = i - 1; j >= high + 1; j--) {
            num[j + 1] = num[j];
        }
        num[high + 1] = temp;
    }
}
void main(){
    int num[12] = { 10,6,2,33,15,12,23,76,1,54,22,9 };
    BinSort(num, 12);
    for (auto x : num) {
        cout << x << " ";
    }
    cout << endl;
    system("pause");
}

---

本文总阅读量次 本站访客数人次