插入排序 - zhuxin

插入排序

      一般来说，插入排序都采用in-place在数组上实现。

      具体算法描述如下：
      从第一个元素开始，该元素可以认为已经被排序
      取出下一个元素，在已经排序的元素序列中从后向前扫描
      如果该元素（已排序）大于新元素，将该元素移到下一位置
      重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
      将新元素插入到该位置后
      重复步骤2~5

      如果比较操作的代价比交换操作大的话，可以采用二分查找法来减少比较操作的数目。该算法可以认为是插入排序的一个变种，称为二分查找排序。

/*
2

名称：插入排序
3

最坏时间复杂度（降序）：O(n * n)
4

最好时间复杂度（升序）：O(n)
5

*/
6

#include <iostream>
7

#include <time.h>
8

#include <stdlib.h>
9

using namespace std;
10

void insertSort(int*, int);
11

int main(void)
12

{
13

int n;
14

int *array;
15

srand(time(NULL)); /*void srand(unsigned seed)；*/
16

while (true)
17

{
18

cin >> n;
19

array = new int[n];
20

/*随机生成数组*/
21

for (int i = 0; i < n; ++i)
22

{
23

array[i] = rand() % 100; /*int rand(void)；*/
24

}
25

/*排序前*/
27

for (int i = 0; i < n; ++i)
28

{
29

cout << array[i] << ' ';
30

}
31

cout << endl;
32

/*插入排序*/
34

insertSort(array, n);
35

/*排序后*/
37

for (int i = 0; i < n; ++i)
38

{
39

cout << array[i] << ' ';
40

}
41

cout << endl;
42

delete array;
44

}
45

return 0;
46

}
47

void insertSort(int* array, int length)
48

{
49

for (int i = 1; i < length; ++i)
50

{
51

/*[0 - (i - 1）]已排好序*/
52

if (array[i] < array[i - 1])
53

{
54

int temp = array[i];
55

int j;
56

/*比array[i]大的元素依次后移*/
57

for (j = i - 1; j >= 0 && array[j] > temp; --j)
58

{
59

array[j + 1] = array[j];
61

}
62

/*赋给相应的元素*/
63

array[j + 1] = temp;
64

}
65

}
66

}
67

如果目标是把n个元素的序列升序排列，那么采用插入排序存在最好情况和最坏情况。最好情况就是，序列已经是升序排列了，在这种情况下，需要进行的比较操作需(n-1)次即可。最坏情况就是，序列是降序排列，那么此时需要进行的比较共有n(n-1)/2次。插入排序的赋值操作是比较操作的次数减去(n-1)次。平均来说插入排序算法复杂度为O(n2)。因而，插入排序不适合对于数据量比较大的排序应用。但是，如果需要排序的数据量很小，例如，量级小于千，那么插入排序还是一个不错的选择。插入排序在工业级库中也有着广泛的应用，在STL的sort算法和stdlib的qsort算法中，都将插入排序作为快速排序的补充，用于少量元素的排序（通常为8个或以下）。

posted on 2012-10-21 23:40 zhuxin 阅读(125) 评论(0) 编辑收藏引用所属分类: 排序算法

只有注册用户登录后才能发表评论。
【推荐】100%开源！大型工业跨平台软件C++源码提供，建模，组态！

相关文章: 快速排序冒泡排序插入排序(递归) 选择排序归并排序插入排序

网站导航: 博客园 IT新闻 BlogJava 知识库博问管理

常用链接

留言簿

文章分类

文章档案

搜索

最新评论