排序算法二：二分（折半）插入排序算法

声明：引用请注明出处http://blog.csdn.net/lg1259156776/

引言

在我的博文《“主宰世界”的10种算法短评》中给出的首个算法就是高效的排序算法。本文将对排序算法做一个全面的梳理，从最简单的“冒泡”到高效的堆排序等。

上一篇博文《排序算法一：直接插入排序》讲述了直接插入排序，本文讲述另一种插入排序算法：二分（折半）插入排序。

排序相关的的基本概念

• 排序：将一组杂乱无章的数据按一定的规律顺次排列起来。
  
  • 数据表( data list): 它是待排序数据对象的有限集合。
  • 排序码(key):通常数据对象有多个属性域，即多个数据成员组成,其中有一个属性域可用来区分对象,作为排序依据。该域即为排序码。每个数据表用哪个属性域作为排序码，要视具体的应用需要而定。
• 分类
  
  • 内排序：指在排序期间数据对象全部存放在内存的排序；
  • 外排序：指在排序期间全部对象个数太多，不能同时存放在内存，必须根据排序过程的要求，不断在内、外存之间移动的排序。

排序算法的分析

排序算法的稳定性

如果在对象序列中有两个对象$r[i]$和$r[j]$ ,它们的排序码$k[i] ==k[j]$ 。如果排序前后,对象$r[i]$和$r[j]$ 的相对位置不变，则称排序算法是稳定的；否则排序算法是不稳定的。

排序算法的评价

时间开销

• 排序的时间开销可用算法执行中的数据比较次数与数据移动次数来衡量。
• 算法运行时间代价的大略估算一般都按平均情况进行估算。对于那些受对象排序码序列初始排列及对象个数影响较大的，需要按最好情况和最坏情况进行估算

空间开销

算法执行时所需的附加存储。

二分（折半）插入排序

基本思想

设在顺序表中有一个对象序列$V[0], V[1], …, V[ n- 1]$。其中, $V[0],V [1] , …, V[i- 1]$是已经排好序的对象。在插入$V[i]$时,利用二分搜索法寻找$V[i]$的插入位置。关于二分搜索法在我的博文《查找searching》中有精彩论述，这里只是简要的说明一下二分搜索在二分插入排序中的应用。

二分插入排序图示

第一行是原始数据，第二行是假设已经排好了前$i$个数据，在排$a[i]$时，采用二分搜索（查找）的方法在前$i$个数据中找到合适的位置插入。下面几行是二分查找的步骤，每次将查找的范围缩小一半儿，直到找到合适位置为止，然后在该位置上插入$a[i]$，其余数据往后移动一个位置。

二分插入排序算法分析

1. 二分搜索比顺序搜索查找快,所以二分插入排序就平均性能来说比直接插入排序要快。
2. 它所需的排序码比较次数与待排序对象序列的初始排列无关,仅依赖于对象个数。在插入第$i$个对象时,需要经过$log_2i +1$次排序码比较,才能确定它应插入的位置。 将n个对象用折半插入排序所进行的排序码比较次数比较次数(KCN)：$\sum^{n-1}(log_2i+1)≈nlog_2n$
3. 二分插入排序是一个稳定的排序方法。
4. 当n较大时,总排序码比较次数比直接插入排序的最坏情况要好得多,但比其最好情况要差。
5. 在对象的初始排列已经按排序码排好序或接近有序时,直接插入排序比折半插入排序执行的排序码比较次数要少。折半插入排序的对象移动次数与直接插入排序相同,依赖于对象的初始排列。

C代码实现

// C program for implementation of binary insertion sort
#include <stdio.h>

// A binary search based function to find the position
// where item should be inserted in a[low..high]
int binarySearch(int a[], int item, int low, int high)
{
    if (high <= low)
        return (item > a[low])?  (low + 1): low;

    int mid = (low + high)/2;

    if(item == a[mid])
        return mid+1;

    if(item > a[mid])
        return binarySearch(a, item, mid+1, high);
    return binarySearch(a, item, low, mid-1);
}

// Function to sort an array a[] of size ‘n‘
void insertionSort(int a[], int n)
{
    int i, loc, j, k, selected;

    for (i = 1; i < n; ++i)
    {
        j = i - 1;
        selected = a[i];

        // find location where selected sould be inseretd
        loc = binarySearch(a, selected, 0, j);

        // Move all elements after location to create space
        while (j >= loc)
        {
            a[j+1] = a[j];
            j--;
        }
        a[j+1] = selected;
    }
}

// Driver program to test above function
int main()
{
    int a[] = {37, 23, 0, 17, 12, 72, 31,
              46, 100, 88, 54};
    int n = sizeof(a)/sizeof(a[0]), i;

    insertionSort(a, n);

    printf("Sorted array: \n");
    for (i = 0; i < n; i++)
        printf("%d ",a[i]);

    return 0;
}

2015-9-24 艺少