排序之直接插入排序

深藏阁楼爱情的钟 2022-05-24 23:04 225阅读 0赞

> # 直接插入排序简介 #

直接[插入排序][Link 1]（Straight Insertion Sort）是一种最简单的排序方法，其基本操作是将一条记录插入到已排好的有序表中，从而得到一个新的、记录数量增1的有序表。

> # 直接插入排序基本思想 #

每一趟将一个待排序的记录，按其关键字的大小插入到已经排好序的一组记录的适当位置上，直到所有待排序记录全部插入为止。 \[1\]

待排序记录 R1，R2，… ，Rn–1, Rn

第一步：R1

第二步：(R1 ), R2

第三步：(R1 , R2), R3

……

第 j 步：(R1，R2，… ，Rj–1), Rj

……

第 n 步: (R1，R2，… ，Rn–1), Rn．

> # 时间复杂度 #

假如是排序好的数列，则只需遍历一次便可结束排序，所以最优时间复杂度是O(n)

假如是完全混乱的数列，每个数都要插最大位，则需要遍历近乎n\*n次，最坏时间复杂度是O(n\*n)

#include <iostream>
    #include <cstdlib>
    #include <ctime>
    using namespace std;
    
    void StraightInsertSort(int num[],int N)
    {
    	for(int i = 1; i < N; i++)		 			//从第二个数进行直接插入排序 
    	{
    		int j = i;
    		while(j > 0 && num[j] < num[j-1])		 //将i位置的数插入到它该去的位置 
    		{
    			int temp = num[j];
    			num[j] = num[j-1];
    			num[j-1] = temp;
    			j--;
    		}
    	}
    }
    
    void print(int num[], int N)
    {
    	int i = 0;
    	while(i < N)	cout << num[i++] << " ";
    	
    	cout << endl;
    }
    
    int main()
    {
    	srand((unsigned)time(NULL));
    	int N;
    	while(cin >> N)
    	{
    		int num[N];
    		for(int i = 0; i < N; i++)			//生成N个随机数 
    		{
    			num[i] = rand() % 65536;
    		}
    		print(num,N);						//打印排序前数列 
    		StraightInsertSort(num,N);			//进行直接插入排序 
    		print(num,N);						//打印排序后数列 
    	}
    	
    	return 0;
    }

[Link 1]: https://baike.baidu.com/item/%E6%8F%92%E5%85%A5%E6%8E%92%E5%BA%8F