插入排序
程序员文章站
2022-06-04 18:06:30
...
0. 简述
插入排序(Insertion Sort)是一种简单直观且稳定的排序算法。
它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。
插入排序和冒泡排序一样,也有一种优化算法,叫做拆半插入。
1. 算法步骤
1、将待排序序列第一个元素看做一个有序序列,把第二个元素到最后一个元素当成是未排序序列。
2、从头到尾依次扫描未排序序列,将扫描到的每个元素插入有序序列的适当位置。(如果待插入的元素与有序序列中的某个元素相等,则将待插入元素插入到相等元素的后面。)
2. 动图演示
3. C++代码实现
#include <iostream>
using namespace std;
template<typename T>
void Insertion_Sort(T arr[], int len)
{
int i, j;
for (i = 1; i < len; i++)//外循环
{
T m = arr[i];
j = i - 1;
//判断条件没有j>=0也可以成功的原因是arr[-1]这个地址中的随机数为负数
while ((j >= 0) && (m < arr[j]))//如果取出的arr[i]小,那么就一直往前找,并将大于它的往后移
{
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = m;//比arr[j]大,那么就在arr[j+1]插入
}
}
int main()
{
int arri[] = { 61, 17, 29, 22, 34, 60, 72, 21, 50, 1, 62 };
int len = (int) sizeof(arri) / sizeof(*arri);
Insertion_Sort(arri, len);
for (int i = 0; i < len; i++)
cout << arri[i] << ' ';
cout << endl;
float arrf[] = { 17.5, 19.1, 0.6, 1.9, 10.5, 12.4, 3.8, 19.7, 1.5, 25.4, 28.6, 4.4, 23.8, 5.4 };
len = (float) sizeof(arrf) / sizeof(*arrf);
Insertion_Sort(arrf, len);
for (int i = 0; i < len; i++)
cout << arrf[i] << ' ' << endl;
return 0;
}
下一篇: 古月居 ROS 21 讲