数据结构--插入排序-蒲公英云

数据结构--插入排序

算法中经常会用到各种各样的算法，比较简答的思想就是冒泡排序，一般刚开始编程时遇到排序问题时，会很容易想到冒泡排，冒泡排序是通过两辆比较数值，从而将数字移动到开始或者末尾的位置，反复重复这个过程从而就达到了排序的目的。其时间复杂度大概是Ο(n2)。还有一种比较常用的插入排序，其思想与冒泡排序比较类似。下面来逐步讲解插入排序的思想：

1、首先考虑到将一个数字插入到一个有序表中，这里有序表代表可以是非增序列，也可以是非减序列。插入完成后，该有序表仍然保持原有的特性。

对于这种情况下，实现的C++代码是：

/**
    @para:    sorted_array:           有序表
              element:                需要插入的元素
              length:                 有序表在没有插入元素时的原始长度
    @function:                        实现插入排序
*/
template<class T>
void Insert(T *sorted_array, const T &element, int length)
{
    //sorted_array[0:length-1] is ordered array and is in increasing order
    int cnt = length;
    while (element<sorted_array[cnt] && cnt>=0)
    {
        sorted_array[cnt + 1] = sorted_array[cnt];
        cnt--;
    }
    sorted_array[cnt + 1] = element;
}

2、紧接着我们考虑迭代的过程，对于一个长度为length的序列，从分别对其部分长度为1,2，……，一直到length的序列进行插入，插入的数字即该长度范围外的第一个数字，即对序列sorted_array[0]开始插入数字sorted_array[1],sorted_array[2]。。。。

最后得到的序列保持了在第一步进行过程中的有序性，因此最后得到的序列是有序的，实现过程是：

template<class T>
void InsertOrder(T *sorted_array, int length)
{
    for (int i = 1; i<length; i++)
    {
        T temp = sorted_array[i];
        Insert(sorted_array, temp, i - 1);
    }
}

3、最后的完整实现过程是：

#include <iostream>
using namespace std;
/**
@para:sorted_array:           有序表
element:                需要插入的元素
length:                 有序表在没有插入元素时的原始长度
@function:                    实现插入排序
*/
template<class T>
void Insert(T *sorted_array, const T &element, int length)
{
    //sorted_array[0:length-1] is ordered array and is in increasing order
    int cnt = length;
    while (element<sorted_array[cnt] && cnt>=0)
    {
        sorted_array[cnt + 1] = sorted_array[cnt];
        cnt--;
    }
    sorted_array[cnt + 1] = element;
}
template<class T>
void InsertOrder(T *sorted_array, int length)
{
    for (int i = 1; i<length; i++)
    {
        T temp = sorted_array[i];
        Insert(sorted_array, temp, i - 1);
    }
}
int main()
{
    int length ;
    cout<<"please input the length of array being sorted:";
    cin>>length;
    int *sorted_array;
    sorted_array = new int[length];
    cout<<"input the array and the separate with numbers with space:"<<endl;
    for (int i = 0; i<length; i++)
    {
        cin >> sorted_array[i];
    }
    InsertOrder(sorted_array, length);
    for (int i = 0; i<length; i++)
    {
        cout << sorted_array[i] << " ";
    }
    return 0;
}