算法设计-插入排序（C++）

一、算法原理

插入排序是一种简单直观的排序算法，它的工作原理是将未排序数据插入到已排序序列的合适位置。具体来说，插入排序将数组分为已排序和未排序两部分，初始时已排序部分只有数组的第一个元素，然后依次从未排序部分取出元素，将其插入到已排序部分的合适位置，直到整个数组都被排序。

二、详细代码

#include<iostream>
using namespace std;

int InsertSort(int arr[], int size)
{
	
	int x, i;
	for( int j = 1; j < size; j++)
	{
		x = arr[j];
		i = j - 1;
		while( i >= 0 && x < arr[i])
		{
			arr[i+1] = arr[i];
			i = i - 1;
		}
		arr[i+1] = x;
	}
	for(int s = 0; s < size; s++)
	{
		
		cout<<arr[s]; 
	}
	cout<<endl;
}


int main()
{
	int size;
	std::cout<<"Enter size:";
	std::cin>>size;
	int* arr =new int[size];

	for(int i = 0;i<size;i++)
	{
		cout<<"arr element:";
		cin>>arr[i]; 
	}
InsertSort(arr,size);
delete[] arr;
return 0;

}

三、详细解释

• 排序过程：

  1. 外层循环：for( int j = 1; j < size; j++)，从数组的第二个元素开始（索引为 1），依次将未排序部分的元素插入到已排序部分。
  2. 保存当前元素：x = arr[j];，将当前要插入的元素保存到变量 x 中。
  3. 内层循环：while( i >= 0 && x < arr[i])，从已排序部分的最后一个元素开始，向前比较，如果当前元素 x 小于已排序部分的元素 arr[i]，则将 arr[i] 向后移动一位，即 arr[i+1] = arr[i];，并将 i 减 1。
  4. 插入元素：当找到合适的位置后，将当前元素 x 插入到该位置，即 arr[i+1] = x;。

• 输出排序结果：

  • 使用 for 循环遍历数组，并使用 cout 输出每个元素，最后换行。

复杂度分析

• 时间复杂度：插入排序的平均时间复杂度和最坏时间复杂度都是O(n2) ，其中n 是数组的大小。在最好情况下，即数组已经有序时，时间复杂度为O(n) 。
• 空间复杂度：插入排序只需要常数级的额外空间，因此空间复杂度为 O(1)。