数据结构笔记(八):排序算法之直接插入排序

发布于 / 程序猿 / 2 条评论

介绍排序的基本知识与直接插入排序算法,实现直接插入排序,并验证直接插入排序的稳定性。若文中存在错误,敬请指出,感谢阅读。

排序基本知识

所谓排序,就是要整理文件中的记录,使之按关键字递增(或递减)次序排列起来。

被排序对象–文件

被排序的对象–文件由一组记录组成。
记录则由若干个数据项(或域)组成。其中有一项可用来标识一个记录,称为关键字项。该数据项的值称为关键字(Key)

排序运算的依据–关键字

来作排序运算依据的关键字,可以是数字类型,也可以是字符类型。
关键字的选取应根据问题的要求而定。
【例】在高考成绩统计中将每个考生作为一个记录。每条记录包含准考证号、姓名、各科的分数和总分数等项内容。若要惟一地标识一个考生的记录,则必须用”准考证号”作为关键字。若要按照考生的总分数排名次,则需用”总分数”作为关键字。

排序的稳定性

当待排序记录的关键字均不相同时,排序结果是惟一的,否则排序结果不唯一。
在待排序的文件中,若存在多个关键字相同的记录,经过排序后这些具有相同关键字的记录之间的相对次序保持不变,该排序方法是稳定的;若具有相同关键字的记录之间的相对次序发生变化,则称这种排序方法是不稳定的。

排序方法的分类

1.按是否涉及数据的内、外存交换分
在排序过程中,若整个文件都是放在内存中处理,排序时不涉及数据的内、外存交换,则称之为内部排序(简称内排序);反之,若排序过程中要进行数据的内、外存交换,则称之为外部排序。
注意
① 内排序适用于记录个数不很多的小文件
② 外排序则适用于记录个数太多,不能一次将其全部记录放人内存的大文件。

2.按策略划分内部排序方法
可以分为五类:插入排序、选择排序、交换排序、归并排序和分配排序。


插入排序

基础知识

插入排序分为直接插入排序希尔排序,我们先谈一谈直接插入排序。

直接插入排序(Direct Insertion Sort)的基本思想是:把n个待排序的元素看成为一个有序表和一个无序表。开始时有序表中只包含1个元素,无序表中包含有n-1个元素,排序过程中每次从无序表中取出第一个元素,将它插入到有序表中的适当位置,使之成为新的有序表,重复n-1次可完成排序过程。

插入排序与打扑克时整理手上的牌非常类似。摸来的第1张牌无须整理,此后每次从桌上的牌(无序区)中摸最上面的1张并插入左手的牌(有序区)中正确的位置上。为了找到这个正确的位置,须自左向右(或自右向左)将摸来的牌与左手中已有的牌逐一比较。

演示

排序前,数组为3,9,21,15,36,26,21,30,50

排序。

排序后,数组为3,9,15,21,21,26,30,36,50

说白了,就是像下面这张图一样。

代码实现

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

void display(int a[], int n) // 输出显示
{
    for (int i = 0; i < n; ++i)
        cout << a[i] << " ";
    cout << endl;
}

void _insert(int a[], int n, int val) // 插入操作
{
    int pos = 0;
    while (pos < n && a[pos] <= val) // 找到插入位置
        ++pos;
    for (int i = n - 1; i >= pos; --i) // 元素后移
        a[i+1] = a[i];
    a[pos] = val; // 插入操作
}

void insert_sort(int a[], int n) 
{
    for (int i = 1; i < n; ++i) 
        _insert(a, i, a[i]);
}

int main()
{
    int a[100] = {3,44,38,5,47,15,36,26,27,2,46,4,19,50,48};
    cout << "排序前:" << endl;
    display(a, 15);
    insert_sort(a, 15);
    cout << "排序后:" << endl;
    display(a, 15);
    return 0;
}
/*
3 44 38 5 47 15 36 26 27 2 46 4 19 50 48
2 3 4 5 15 19 26 27 36 38 44 46 47 48 50
*/

使用结构体数组,进行直接插入排序,验证其为稳定排序。

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

struct Node
{
    int idx; // 下标(从1开始)
    int val; // 值
};

void display(Node a[], int n) // 输出显示
{
    for (int i = 0; i < n; ++i)
        cout << "下标: " << a[i].idx << "\t值:" << a[i].val << endl;
}

void _insert(Node a[], int n, Node x) // 插入操作
{
    int pos = 0;
    while (pos < n && a[pos].val <= x.val) // 找到插入位置
        ++pos;
    for (int i = n - 1; i >= pos; --i) // 元素后移
        a[i+1] = a[i];
    a[pos] = x; // 插入操作
}

void insert_sort(Node a[], int n) 
{
    for (int i = 1; i < n; ++i) 
        _insert(a, i, a[i]);
}

int main()
{
    int _a[100] = {3,44,38,5,47,15,36,26,47,2,46,4,26,50,48};
    Node a[100];
    for (int i = 0; i < 15; ++i)
    {
        a[i].idx = i + 1;
        a[i].val = _a[i];
    }
    cout << "排序前:" << endl;
    display(a, 15);
    insert_sort(a, 15);
    cout << "排序后:" << endl;
    display(a, 15);
    return 0;
}
排序前:
下标: 1        值:3
下标: 2        值:44
下标: 3        值:38
下标: 4        值:5
下标: 5        值:47
下标: 6        值:15
下标: 7        值:36
下标: 8        值:26
下标: 9        值:47
下标: 10       值:2
下标: 11       值:46
下标: 12       值:4
下标: 13       值:26
下标: 14       值:50
下标: 15       值:48
排序后:
下标: 10       值:2
下标: 1        值:3
下标: 12       值:4
下标: 4        值:5
下标: 6        值:15
下标: 8        值:26
下标: 13       值:26
下标: 7        值:36
下标: 3        值:38
下标: 2        值:44
下标: 11       值:46
下标: 5        值:47
下标: 9        值:47
下标: 15       值:48
下标: 14       值:50

算法分析

1.算法的时间性能分析
假设被排序的数列中有N个数,遍历一趟的时间复杂度是O(N),需要进行N-1次排序,所以时间复度为O(N^2)

2.算法的空间复杂度分析
空间复杂度为O(1),用于记录需要插入的数据。

3.直接插入排序的稳定性
直接插入排序是稳定的排序方法(已验证)。
算法稳定性 — 假设在数列中存在a[i]=a[j],若在排序之前,a[i]在a[j]前面;并且排序之后,a[i]仍然在a[j]前面。则这个排序算法是稳定的。

补充

直接插入排序的另一种写法。

void insertionsort(int a[], int n)
{
    int i, j, t;
    for (i = 1; i < n; ++i)
    {
        t = a[i];
        for (j = i - 1; j >= 0 && a[j] > t; j--)
            a[j+1] = a[j];
        a[j+1] = t;
    }
}

此外,也可以使用二分查找寻找插入位置对直接插入排序进行优化,提高算法效率,但算法的时间复杂度仍为O(N^2)。具体代码就不实现了,希尔排序有时间再谈。

娱乐

太无聊了,我们通过rand()函数产生不同的随机数来测试一下直接插入排序的时间吧!话不多说,直接上代码!

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdlib>
#include <ctime>
using namespace std;
const int Min = 1; // 控制随机数范围
const int Max = 10000;
const int maxn = 100000;
int a[maxn];

void _insert(int a[], int n, int val) // 插入操作
{
    int pos = 0;
    while (pos < n && a[pos] <= val) // 找到插入位置
        ++pos;
    for (int i = n - 1; i >= pos; --i) // 元素后移
        a[i+1] = a[i];
    a[pos] = val; // 插入操作
}

void insert_sort(int a[], int n) 
{
    for (int i = 1; i < n; ++i) 
        _insert(a, i, a[i]);
}

void insertionsort(int a[], int n)
{
    int i, j, t;
    for (i = 1; i < n; ++i)
    {
        t = a[i];
        for (j = i - 1; j >= 0 && a[j] > t; --j)
            a[j+1] = a[j];
        a[j+1] = t;
    }
}

int main()
{
    srand((unsigned)time(NULL)); // 设置随机数种子
    for (int i = 0; i < maxn; ++i)
        a[i] = rand() % (Max-Min) + Min;
    clock_t _start, _end;
    _start = clock();
    //insertionsort(a, maxn);
    insert_sort(a, maxn);
    _end = clock();
    cout << (double)(_end - _start) / CLOCKS_PER_SEC << endl;
    return 0;
}

这是运行结果:

使用insertionsort(a, maxn);
maxn = 1000时,  用时:0.002s;
maxn = 10000时, 用时:0.192s;
maxn = 50000时, 用时:5.696s;
maxn = 100000时,用时:25.574s;
maxn = 1000000时,用时:你自己去玩吧,我不想等了。
-----------------------------
使用insert_sort(a, maxn);
maxn = 1000时,  用时:0.002s;
maxn = 10000时, 用时:0.415s;
maxn = 50000时, 用时:11.523s;
maxn = 100000时,用时:38.624s;
maxn = 1000000时,用时:你自己去玩吧,我不想等了。

通过运行结果我们可以知道insertionsort(a, maxn);insert_sort(a, maxn);要快一些,即使它们的时间复杂度是一样的(存在随机数的偏差),所以写法不同会对程序运行时间产生影响。当然,当数量较大(特别大)时,相对来说也差不了多少。当待排序数达到10000时,我们就能感受到有一个等待过程。

突然发现,我要是在产生随机数时不使用srand()函数设置随机数种子的话,可能两种不同写法的直接插入排序比较的结果应该更佳准确,不管了不管了。

此外,获取函数运行时间还有一种高逼格的写法。

void getTime(void f(int [], int))
{
    clock_t _start, _end;
    _start = clock();
    insertionsort(a, maxn);
    _end = clock();
    cout << (double)(_end - _start) / CLOCKS_PER_SEC << endl;
}

调用时只需要:getTime(insertionsort);

文中基础部分来自数据结构学习网,同时也参考了skywang12345写的直接插入排序,同时推荐河边一支柳写的插入排序


To be continued.
2017-12-03 星期日

更新

补充直接插入排序倒序查找与二分查找插入位置代码,其实倒序的在上面另一种写法已经提到过了,在这里做一下汇总。

  • 正序查找(从第一个位置开始)
void _insert(int a[], int n, int val) // 插入操作
{
    int pos = 0;
    while (pos < n && a[pos] <= val) // 找到插入位置
        ++pos;
    for (int i = n - 1; i >= pos; --i) // 元素后移
        a[i+1] = a[i];
    a[pos] = val; // 插入操作
}

void insert_sort(int a[], int n) // 插入排序
{
    for (int i = 1; i < n; ++i) //
        _insert(a, i, a[i]);
}
  • 倒序查找(从最后一个位置开始)
void _Insert(int a[], int n, int val)
{
    int pos = n - 1;
    while (pos >= 0 && val < a[pos])
        a[pos+1] = a[pos], --pos;
    a[pos+1] = val;
}

void Insert_sort(int a[], int n) // 插入排序
{
    for (int i = 1; i < n; ++i) //
        _Insert(a, i, a[i]);
}
  • 二分查找插入位置
void binary_insert(int a[], int n, int val)
{
    int l = 0, r = n - 1;
    while (l <= r) // 稳定排序--查找第一个大于val的数的位置
    {
        int m = (l+r) >> 1;
        if (a[m] <= val)
            l = m + 1;
        else
            r = m - 1;
    }
    int pos = r + 1; // 插入位置
    for (int i = n - 1; i >= pos; --i)
        a[i+1] = a[i];
    a[pos] = val;
}

void binary_insert_sort(int a[], int n) 
{
    for (int i = 1; i < n; ++i) 
        binary_insert(a, i, a[i]);
}
  • 直接插入排序链式存储结构实现(太懒了,就不写注释了)
#include <iostream>
#include <cstdlib>
#include <ctime>
using namespace std;

const int maxn = 100;
const int Max = 10000;
const int Min = 1;

struct Node
{
    int value;
    Node *next;
};

int a[maxn];
Node Nodes[maxn];

void display(int a[], int n)
{
    for (int i = 0; i < n; ++i)
    {
        cout << a[i] << " ";
        if ((i+1) % 5 == 0)
            cout << endl;
    }
    cout << endl;
}

void list_insert(Node *head, Node *p)
{
    Node *q = head;
    while (q->next && q->next->value <= p->value)
        q = q->next;
    p->next = q->next;
    q->next = p;
}

Node * List_Insert_Sort(Node a[], int n)
{
    Node *head = new Node;
    head->next = NULL;
    for (int i = 0; i < n; ++i)
        list_insert(head, &a[i]);
    return head;
}

int main()
{
    for (int i = 0; i < maxn; ++i)
        a[i] = rand() % (Max - Min) + 1;
    for (int i = 0; i < maxn; ++i)
    {
        Nodes[i].value = a[i];
        Nodes[i].next = NULL;
    }
    clock_t _start, _end;
    _start = clock();
    Node * head = List_Insert_Sort(Nodes, maxn);
    _end = clock();
    cout << (double)(_end - _start) / CLOCKS_PER_SEC << endl;
    Node * pt = head->next;
    int k = 0;
    while (pt != NULL)
    {
        ++k;
        cout << pt -> value << "\t";
        pt = pt->next;
        if (k % 5 == 0)
            cout << endl;
    }
    return 0;
}
maxn = 100时,输出:
0
40      42      110     154     289
293     337     492     779     1105
1325    1326    1480    1540    1541
1729    1842    1843    1870    1944
2083    2193    2318    2384    2395
2443    2625    2651    2666    2761
2861    2932    2996    3036    3284
3549    3808    3814    3903    3933
4087    4373    4396    4467    4606
4629    4665    4773    4828    4967
5008    5143    5352    5437    5448
5538    5550    5670    5706    5726
5892    6120    6302    6311    6335
6503    6543    6730    6829    6869
6946    6965    7037    7377    7423
7449    7532    7647    7675    7712
8148    8256    8469    8706    8718
8724    8758    8943    9041    9171
9266    9361    9631    9720    9742
9895    9897    9914    9956    9962
------------------------------------
maxn = 1000时,耗时:0.003s
maxn = 10000时,耗时:0.343s
maxn = 100000时,耗时:自己慢慢等吧

The end.
2017-12-05 星期二

转载原创文章请注明,转载自: 太傅 » 数据结构笔记(八):排序算法之直接插入排序
  1. 知道91博客

    不错有意思啊,这是数据结构必学的吧

    1. TaiFu_S
      @知道91博客

      对呀,?