【数据结构】中的插入(InsertSort)排序

清疚 2022-06-16 10:14 171阅读 0赞

插入排序的解释：

有一个已经有序的数据序列，要求在这个已经排好的数据序列中插入一个数，但要求插入后此数据序列仍然有序。

这个时候就要用到一种新的排序方法——插入排序法,插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中，从而得到一个新的、个数加一的有序数据，算法适用于少量数据的排序，[时间复杂度][Link 1]为O(n^2)。是稳定的排序方法。

插入算法把要排序的数组分成两部分：

第一部分包含了这个数组的所有元素，但将最后一个元素除外（让数组多一个空间才有插入的位置）、

第二部分就只包含这一个元素（即待插入元素）。

在第一部分排序完成后，再将这个最后元素插入到已排好序的第一部分中。

插入排序的基本思想是：每步将一个待排序的纪录，按其关键码值的大小插入前面已经排序的文件中适当位置上，直到全部插入完为止。

插入排序的代码实现：

#include<iostream>
    using namespace std;
    #include<assert.h>
    void InsertSort(int *a, size_t n)
    {
    	for (int i = 1; i < n; i++)
    	{
    		int j = 0;
    		while (j < i&&a[j] <= a[i])
    		{
    			j++;
    		}
    		if (j < i)
    		{
    			int k = i;
    			int tmp = a[i];
    			while (k>j)
    			{
    				a[k] = a[k - 1];
    				k--;
    			}
    			a[k] = tmp;
    		}
    	}
    }
    
    void printArray(int *a, size_t n)
    {
    	for (size_t i = 0; i < n; i++)
    	{
    		cout << a[i] << " ";
    	}
    	cout << endl;
    }
    
    int main()
    {
    	//int arr[] = { 1, 3, 5, 7, 0, 2, 9, 4, 6, 8 };
    	int arr[] = { 56, 89, 23, 45, 66 };
    	int n = sizeof(arr) / sizeof(arr[0]);
    	InsertSort(arr, n);
    	cout << "排序后：";
    	printArray(arr, n);
    	system("pause");
    	return 0;
    }

插入排序的运行结果：

![Center][]

[Link 1]: http://baike.sogou.com/lemma/ShowInnerLink.htm?lemmaId=105680&ss_c=ssc.citiao.link
[Center]: /images/20220616/2816f93ff9ff41b8805c72fdad789770.png