超全经典排序大汇总

算法思想

设置三个变量low,high,mid，令mid = (low + high) / 2,若a[mid] > key, 则令high = mid - 1,否则令low = mid + 1,直到low > hig时停止循环。对序列中的每个元素做以上处理，找到合适位置将其他元素后移，进行插入。

时间复杂度

1. 最好 — $O(nlogn)$
2. 最坏 — $O(n^2)$
3. 平均 — $O(n^2)$

注：比较次数与待排序列的初始装态无关，仅取决于表中的元素个数

空间复杂度 O（1）

1. 不带哨兵用临时变量temp
2. 带哨兵用a[0]

稳定性

稳定

适用性

仅适用于顺序表

算法特点

1. 稳定排序
2. 因为要进行折半查找，所以只能用于顺序表，不能用于链表
3. 适合初始记录无序，n较大的情况。
4. 先比于直接插入排序，比较次数大大减少。

代码

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <fstream>

using namespace std;
const int N = 20;
int num, idx;//num存放元素个数 

int data[N]; 

//折半插入排序 (带哨兵) 
void BinaryInsertSort(int a[], int n){
    int i, j, low, high, mid;
    for(i = 2; i <= n; i ++){
        a[0] = a[i];//将带插入元素赋给哨兵
        low = 1, high = i - 1;//在1~i-1之间进行二分查找 
        while(low <= high){//high > low循环结束
         mid = low + high >> 1;
         if(a[0] < a[mid]) high = mid - 1;
         else low = mid + 1;//即便元素相等也插入其后，保持排序稳定性
        }
        for(j = i - 1; j >= high + 1; j --){// 待插元素应位于high+1处
         a[j + 1] = a[j];//将有序元素后移 
        }
        a[high + 1] = a[0];//将待插元素插入到正确位置
    }
}

int main(){
    //读文件 
    ifstream infile;
    infile.open("D:\\学习\\数据结构\\第8章排序\\in.txt",ios::in);

    //写文件
    ofstream outfile; 
    outfile.open("D:\\学习\\数据结构\\第8章排序\\out.txt",ios::out);

    if(!infile.is_open()){//判断文件是否打开成功 
        cout << "file open failure !" << endl;
    }

    infile >> num;
    while(num != 0){
        infile >> data[++ idx];
        num --;
    }

    num = idx;
    for(int i = 1; i <= num; i ++) cout << data[i] << ' '; cout << endl;

    BinaryInsertSort(data, idx);
    //sort(data,data + num);
    for(int i = 1; i <= num; i ++) cout << data[i] << ' '; cout << endl; 

    idx = 1;
    outfile << num; outfile << endl;
    while(num != 0){
        outfile << data[idx ++] << ' ';
        num --;
    }
    outfile << endl;

    //关闭文件 
    infile.close();
    outfile.close();
    return 0;
} 

输入数据(in.txt)

10
13 69 86 99 59 23 64 32 86 72

输出数据(out.txt)

10
13 23 32 59 64 69 72 86 86 99