欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

3.插入排序

程序员文章站 2022-07-08 14:50:51
...

基本思路:扑克牌的摸牌、理牌。

基本操作:将一个记录插入到已经排好序的有序表中,得到一个新的、记录数增1的有序表。

可做优化,找插入位置时采用折半查找。


1、算法步骤

(1)将待排序序列第一个元素看做一个有序序列,把第二个元素到最后一个元素当成是未排序序列。

(2)从头到尾依次扫描未排序序列,将扫描到的每个元素插入有序序列的适当位置。(如果待插入的元素与有序序列中的某个元素相等,则将待插入元素插入到相等元素的后面。)

2、动画演示

3.插入排序

 3、最佳、最坏情况

最好情况:顺序T = O(3.插入排序)

最坏情况:逆序T = O(3.插入排序)

定理1:任意N个不同元素,组成的序列平均具有3.插入排序个逆序对。

定理2:任何仅以交换相邻元素来排序的算法,其平均时间复杂度为3.插入排序

意味着:要提高算法效率,必须:每次交换相隔较远的2个元素。在此基础上就有了希尔排序

4、C++代码实现

#include<iostream>
using namespace std;
template <typename T>

void Insertion_Sort(T A[], int N)
{
	for(int p = 1; p < N; p++)
	{
		int tmp = A[p];//摸数
		for(int i = p; i > 0 && A[i-1] > tmp; i--)
			A[i] = A[i-1];/*移出空位,主意执行完移位后i会减一,所以i指向空位*/
		A[i] = tmp;//新数落位
	}
}
int main()
{
	int arr[] = {154,486,12,846,21,50,4,89,64,11};
	int len = sizeof(arr)/sizeof(arr[0]);
	Insertion_Sort(arr, len);

	for(int i =0; i < len; i++)
		cout<<arr[i]<<' ';
	cout<<endl;
	return 0;
}