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

插入排序

程序员文章站 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;
}
相关标签: 插入排序