3.插入排序
程序员文章站
2022-07-08 14:50:51
...
基本思路:扑克牌的摸牌、理牌。
基本操作:将一个记录插入到已经排好序的有序表中,得到一个新的、记录数增1的有序表。
可做优化,找插入位置时采用折半查找。
1、算法步骤
(1)将待排序序列第一个元素看做一个有序序列,把第二个元素到最后一个元素当成是未排序序列。
(2)从头到尾依次扫描未排序序列,将扫描到的每个元素插入有序序列的适当位置。(如果待插入的元素与有序序列中的某个元素相等,则将待插入元素插入到相等元素的后面。)
2、动画演示
3、最佳、最坏情况
最好情况:顺序T = O()
最坏情况:逆序T = O()
定理1:任意N个不同元素,组成的序列平均具有个逆序对。
定理2:任何仅以交换相邻元素来排序的算法,其平均时间复杂度为
意味着:要提高算法效率,必须:每次交换相隔较远的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;
}