排序算法研究之直接插入排序（insert soft)

直接插入排序（insert soft)

上一节我们介绍了冒泡排序的基本思想和实现过程，本节我们讲解第二个排序算法-----直接插入排序。

1、算法思想

将数组的第一个元素看成一个有序的序列，然后把第二个元素到最后一个元素看作是未排序的序列。
从头到尾扫描未排序的序列（第二个元素到末尾），将每次扫描的元素插入到有序序列合适的位置。

注：每次扫描的元素从排好序的序列的最后一个元素开始比较，找到位置立刻停止

2、优缺点

优点：每一次的扫描过程：一边比较，一边挪位置。 挪位置是赋值操作，相比冒泡排序的交换操作，要高效。
缺点：比较轮数较多，且每一轮都是不可或缺的，无法进一步进行优化。时间复杂度O（n²）

3、关键点

（i） 每次从排好顺序的序列最末尾开始比较, index=i-1
（ii）通过挪动比较，找到插入的位置。位置：index is important
（iii）同样注意升序还是降序

4、代码实现（c++）

例子：输入一个有10个元素的数组，并对其进行插入排序，要求最后数组按照升序。

/**************************************************************************** @file Insert_sort.cpp* @author Shawn* @date 30 Dec 2018* @remark 30 Dec 2018* @theme Insert Sort***************************************************************************/
# include<iostream>
using namespace std;
void isort(int[], int);int main()
{
    int array [] = {
    55,2,6,4,32,12,9,73,26,37};int len = sizeof(array) / sizeof(int);cout<<"输入的原始序列: ";for(int i=0; i<len; i++) // 输出原序列cout<<array[i]<<",";cout<<endl<<endl;cout<<" ----插入排序开始---- " << endl;isort(array,len); // 调用排序函数return 0;
}void isort(int a[], int size)
{
    int inserter, index;// 插入排序过程for(int i=1; i<size; i++){
    inserter = a[i]; // 待插入的元素index = i - 1;  // 与待插入元素比较的元素下标，前i个元素已经排好顺序while(index>=0 && inserter < a[index]) // 找位置关键操作{
    a[index + 1] = a[index];index--;}a[index + 1] = inserter;for(int j=0; j<size; j++)cout<<a[j]<<",";cout<<endl;}
}

下一讲 快速排序