玩技术,Geeker
一个原创技术文章分享网站

插入排序

插入排序

没事喜欢看看数据结构和算法,增加自己对数据结构和算法的认识,同时也增加自己的编程基本功。插入排序是排序中比较常见的一种,理解起来非常简单。现在比如有以下数据需要进行排序:

10 3 8 0 6 9 2

当使用插入排序进行升序排序时,排序的步骤是这样的:

10 3 8 0 6 9 2 // 取元素3,去和10进行对比

3 10 8 0 6 9 2 // 由于10比3大,将10向后移动,将3放置在原来10的位置;再取8与前一个元素10进行对比

3 8 10 0 6 9 2 // 同理移动10;然后8再和3比,8大于3,所以不再移动;如此重复下去

……

0 2 3 6 8 9 10

也就是说,我们每一次取一个元素,都要将该元素与之前已经排序好的元素进行比较。

插入排序的最差时间复杂度为O(n^2)。同时,该算法不需要开辟额外的空间,都是在原空间上进行移动操作。

代码实现

#include <iostream>
using namespace std;

void InsertSort(int arr[], int length)
{
     int temp;
     for (int i = 1; i < length; ++i) // 从数组中的第二个元素开始
     {
          temp = arr[i]; // 记录当前的元素
          int j = i - 1;
          while (j >= 0 && temp < arr[j]) // 将当前元素与之前的已经排序好的序列元素进行挨个比较
          {
               arr[j + 1] = arr[j]; // 已经排序好的序列整体向后移动
               --j;
          }
          arr[j + 1] = temp; // 插入当前的元素
     }
}

int main()
{
     int arr[10] = {9, 2, 8, 2, 3, 2, 4, 10, 34, 5};

     InsertSort(arr, 10);

     for (int i = 0; i < 10; ++i)
     {
          cout<<arr[i]<<" ";
     }
     cout<<endl;

     return 0;
}

2014年2月9日 于大连,东软。

打赏

未经允许不得转载:果冻想 » 插入排序

分享到:更多 ()

评论 2

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址
  1. #2

    再来温习一遍

    vast1年前 (2016-08-18)回复
  2. #1

    温故而知新。

    fanhaobai4周前 (09-16)回复

在这里玩技术,享受技术带来的疯狂

捐赠名单关于果冻