《算法之美》---插入排序

不断地从无序部分抽取一个元素，并将其插入到有序部分合适位置上的排序方法称为插入排序。

插入排序的特点是将待排序的元素一个个插入到已经排好序的数列中，这涉及到插入位置的确定。显然，要确定一个元素的位置，就需要将待排序的元素与已排序部分的元素进行比较，最简单的方法就是一个一个元素地进行：

/*

函数名： InsertionSort

功能： 插入排序

模板参数说明：T必须支持小于操作

参数说明： data待排序数组, size待排序数组大小

前置条件： data!=NULL, size>0

后置条件： data按非降序排列

用法： int arr[]={10,9,8,4,5,7,6,3,1,4};

InsertionSort(arr, 10);

*/

template<typename T>

void InsertionSort(T data[], int size)

{

T temp;

for(int i=1; i<size; i++)

{

temp = data[i];

//从已排好序元素的最后面开始和temp比较

for(int j=i; j>0 && temp<data[j-1]; --j)

{

data[j] = data[j-1];//大于temp的元素data[j-1]值往后移，前面空出的留给temp嘛

}

//最后空出的位置就是留给插入元素的

data[j] = temp;

}

}

/*

函数名： InsertionSort

功能： 插入排序

模板参数说明：T元素类型，Func函数对象或函数指针

参数说明： data待排序数组, size待排序数组大小，f函数对象或地址

前置条件： data!=NULL, size>0

后置条件： data按f排列

用法：

bool cmp(int a, int b)

{ return a<b; }

int arr[]={10,9,8,4,5,7,6,3,1,4};

InsertionSort(arr, 10, cmp);

*/

template <typename T, typename Func >

void InsertionSort (T data[], int size, Func f)

{

T temp;

for (int i=1; i<size; ++i)

{

temp=data[i];

for (int j=i; j>0 && f(temp,data[j-1]); --j)

data[j]=data[j-1];

data[j]=temp;

}

}

上面代码中，数组data中是待排序的元素，而排好序的元素还是存放在数组data中。这种在排序过程中不使用临时存储空间，即排序前和排序后元素都存在同一个地方的排序称为原地排序。

新元素与有序部分的比较是从后面开始，一个个往前比较，直到找到一个比新元素小的元素或者有序部分的元素已经比较完。此时我们将新元素插入刚才找到的比它小的元素的后面（或数组的首位置）。插入排序的整个过程：

8 2 4 9 3 6 //开始状态，第一个元素8是唯一排好序的部分，即有序部分

2 8 4 9 3 6 //第一步，元素2插入到元素8前面，有序部分增加到两个元素

2 4 8 9 3 6 //第二步，元素4插入到元素8前面，有序部分增加到三个元素

2 4 8 9 3 6 //第三步，元素9位置不变，有序部分增加到四个元素

2 3 4 8 9 6 //第四步，元素3插入到元素4前面，有序部分增加到五个元素

2 3 4 6 8 9 //第五步，元素6插入到元素8前面，有序部分增加到六个元素

此时，无序部分为空，插入排序结束。

插入排序的时间复杂度在最坏和平均情况下都是Θ(n²)；而在最好情况下是Θ(n)。

上面的直接插入排序算法的时间复杂度实在不能接受，因为这是最笨的比较方法了。由于序列的前面部分为已经排好序的，因此新元素在插入过程中与有序部分的比较可以使用折半进行，即先与有序部分最中间元素比较，如果新元素与中间元素大小一样，则插入位置就在中间元素的后面。否则有两种情况需要考虑：一是新元素比中间元素大，则将比较范围缩小为中间元素到有序部分最后的元素区域；一是新元素比中间元素小，则将比较范围缩小到有序部分起始元素到中间元素区域。然后按照上述过程重复进行，直到找到排序位置为止。

这种在寻找插入位置过程中使用折半查找的插入排序就是折半插入排序。折半插入排序的时间复杂度是

Θ(nlogn)：

/*

函数名： BiInsertionSort

功能： 折半插入排序

模板参数说明：T必须支持小于操作

参数说明： data待排序数组, size待排序数组大小

前置条件： data!=NULL, size>0

后置条件： data按非降序排列

用法： int arr[]={10,9,8,4,5,7,6,3,1,4};

BiInsertionSort(arr, 10);

*/

template<typename T>

void BiInsertionSort(T data[], int size)

{

int low, high, mid;

T temp;

for(int i=1; i<size; i++)

{

temp = data[i];

low = 0; // 设置查找区间上下限

high = i-1;

while(low <= high)

{

mid = (low+high)/2;

if(temp < data[mid])

high = mid - 1; //插入点在前半区

else

low = mid + 1; //插入点在后半区

}

for(int j=i-1; j>=low; --j)

{

data[j+1] = data[j]; //记录后移

}

data[low] = temp; //插入

}

}