超全经典排序大汇总

算法思想

将序列分为有序部分和无序部分，从无序部分中依次选择元素，与有序部分进行比较，找到合适的位置，将原来的元素后移，将元素插入到相应的位置，直到全部记录插入完成。

动画演示

时间复杂度

1. 最好 — $O(n)$ 序列有序
2. 最坏 — $O(n^2)$ 序列逆序
3. 平均 — $O(n^2)$

空间复杂度 O（1）

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

稳定性

稳定

适用性

1. 顺序表
2. 链表

算法特点

1. 稳定排序
2. 算法简易，易实现
3. 顺序表、链表均可实现
4. 更适用于初始记录基本有序的情况，当n较大时，时间复杂度高不宜采用。

核心代码

//直接插入排序（无哨兵） 
void InsertSort(int a[], int n){
    int i, j , temp;
    for(i = 1; i < n; i ++){
        if(a[i] < a[i - 1]){
            temp = a[i];
            for(j = i - 1; j >= 0 && temp < a[j]; j --){
                a[j + 1] = a[j];
            }
            a[j + 1] = temp;
        }
    }
}

//直接插入排序（有哨兵） 
void InsertSort2(int a[], int n){
    int i , j;
    for(i = 2; i <= n; i ++){
        if(a[i] < a[i - 1]){
            a[0] = a[i];
            for(j = i - 1; a[0] < a[j]; j --){
                a[j + 1] = a[j];
            }
            a[j + 1] = a[0];
        }
    }
} 

完整代码（无哨兵）

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

using namespace std;
const int N = 10;
int data[N], idex;

//直接插入排序（无哨兵） 
void InsertSort(int a[], int n){
    int i, j , temp;
    for(i = 1; i < n; i ++){
        if(a[i] < a[i - 1]){
            temp = a[i];
            for(j = i - 1; j >= 0 && temp < a[j]; j --){
                a[j + 1] = a[j];
            }
            a[j + 1] = temp;
        }
    }
}

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 << "Open file failure" << endl; 
    }
    while(!infile.eof()){
        infile >> data[idex ++];
    }

    //原数组元素 
    for(int i = 0; i < N; i ++) cout << data[i] << ' '; cout << endl;

    //不带哨兵的插入排序后 
    InsertSort(data,idex);
    for(int i = 0; i < N; i ++) cout << data[i] << ' '; cout << endl;

    for(int i = 0; i < N; i ++) outfile << data[i] << ' '; outfile << endl;

    infile.close();
    outfile.close();
    return 0;
} 

输入案例（in.txt）

13 69 86 99 59 23 64 32 86 72

输出结果(out.txt)

13 23 32 59 64 69 72 86 86 99

完整代码（有哨兵）

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

using namespace std;
const int N = 20;
int data[N], idex,num = 10;

//直接插入排序（有哨兵） 
void InsertSort2(int a[], int n){
    int i , j;
    for(i = 2; i <= n; i ++){
        if(a[i] < a[i - 1]){
            a[0] = a[i];
            for(j = i - 1; a[0] < a[j]; j --){
                a[j + 1] = a[j];
            }
            a[j + 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 << "Open file failure" << endl; 
    }

    idex = 1;
    while(!infile.eof()){
        infile >> data[idex ++];
    }

    //原数组元素 
    for(int i = 1; i <= num; i ++) cout << data[i] << ' '; cout << endl;

    //不带哨兵的插入排序后 
    InsertSort2(data,num);
    //sort(data + 1 ,data + num + 1);
    for(int i = 1; i <= num; i ++) cout << data[i] << ' '; cout << endl;

    //输出排序后文件数据 
    for(int i = 1; i <= num; i ++)  outfile << data[i] << ' '; outfile << endl;

    infile.close();
    outfile.close();
    return 0;
} //直接插入排序（有哨兵）

输入案例（in.txt）

13 69 86 99 59 23 64 32 86 72

输出结果(out.txt)

13 23 32 59 64 69 72 86 86 99