插入排序

简介: 在待排序的元素中,假设前n-1个元素已有序,现将第n个元素插入到前面已经排好的序列中,使得前n个元素有序。按照此法对所有元素进行插入,直到整个序列有序。  但我们并不能确定待排元素中究竟哪一部分是有序的,所以我们一开始只能认为第一个元素是有序的,依次将其后面的元素插入到这个有序序列中来,直到整个序列有序为止。

步骤:


1.从第一个元素开始,该元素可以认为已经被排序

2.取下一个元素tem,从已排序的元素序列从后往前扫描

3.如果该元素大于tem,则将该元素移到下一位

4.重复步骤3,直到找到已排序元素中小于等于tem的元素

5.tem插入到该元素的后面,如果已排序所有元素都大于tem,则将tem插入到下标为0的位置

6.重复步骤2~5

思路:

 在待排序的元素中,假设前n-1个元素已有序,现将第n个元素插入到前面已经排好的序列中,使得前n个元素有序。按照此法对所有元素进行插入,直到整个序列有序。

 但我们并不能确定待排元素中究竟哪一部分是有序的,所以我们一开始只能认为第一个元素是有序的,依次将其后面的元素插入到这个有序序列中来,直到整个序列有序为止

void InsertSort(int* arr, int n)
{
  for (int i = 0; i < n - 1; ++i)
  {
    //记录有序序列最后一个元素的下标
    int end = i;
    //待插入的元素
    int tem = arr[end + 1];
    //单趟排
    while (end >= 0)
    {
      //比插入的数大就向后移
      if (tem < arr[end])
      {
        arr[end + 1] = arr[end];
        end--;
      }
      //比插入的数小,跳出循环
      else
      {
        break;
      }
    }
    //tem放到比插入的数小的数的后面
    arr[end  + 1] = tem;
    //代码执行到此位置有两种情况:
    //1.待插入元素找到应插入位置(break跳出循环到此)
    //2.待插入元素比当前有序序列中的所有元素都小(while循环结束后到此)
  }
}
相关文章
|
29天前
|
搜索推荐 算法 C语言
插入排序
插入排序是一种简单直观的排序算法,通过构建有序序列,将未排序的数据逐个插入到已排序序列中的适当位置。该算法采用in-place排序,只需常数级额外空间。示例代码展示了如何使用C语言实现插入排序,并对一个整数数组进行排序。
26 6
|
6月前
|
算法 搜索推荐 Java
插入排序就是这么容易
插入排序就是这么容易
33 0
|
7月前
|
搜索推荐 C++
C++插入排序的实现
C++插入排序的实现
|
7月前
|
存储 搜索推荐 算法
插入排序(一)——直接插入排序与希尔排序
插入排序(一)——直接插入排序与希尔排序
51 1
|
7月前
|
搜索推荐 算法 测试技术
排序算法:插入排序(直接插入排序、希尔排序)
排序算法:插入排序(直接插入排序、希尔排序)
76 0
|
搜索推荐
17 插入排序
17 插入排序
38 0
插入排序与希尔排序
插入排序与希尔排序
54 0
|
搜索推荐 测试技术 C++
【插入排序】直接插入排序 与 希尔排序
【插入排序】直接插入排序 与 希尔排序
|
算法
插入排序之直接插入排序
一、基本思想: 依次将每个记录(无序表)插入到一个已排好序的有序表中,得到一个新的,记录增加1的有序表;
|
人工智能 算法 搜索推荐
常见排序算法之插入排序——直接插入排序、希尔排序
哈喽大家好,我是保护小周ღ,本期为大家带来的是常见排序算法中的插入排序,主要有直接插入排序以及它的升级版——希尔排序,包您一看就会,快来试试吧~
164 0
常见排序算法之插入排序——直接插入排序、希尔排序