数据结构--插入排序

﹏ヽ暗。殇╰゛Y 2022-07-28 10:53 173阅读 0赞

算法中经常会用到各种各样的算法，比较简答的思想就是冒泡排序，一般刚开始编程时遇到排序问题时，会很容易想到冒泡排，冒泡排序是通过两辆比较数值，从而将数字移动到开始或者末尾的位置，反复重复这个过程从而就达到了排序的目的。其时间复杂度大概是Ο(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;
    }

4、最后我们来看看插入排序的每次插入的过程：  
![20160414203509394][]

[20160414203509394]: /images/20220724/fb58f416498d4e42b071d14ea1ffd132.png