排序 插入排序

插入排序

    插入排序的基本思想为逐个考察每个待排序元素，将每一个新元素插入到前面已经排好序的序列中适当的位置上，使得新序列仍然是一个有序序列。 插入排序可分为直接插入排序和希尔排序。

1.直接插入排序

介绍：直接插入排序是一种最简单的排序方法，它的基本操作是将一个记录插入到已排好序的有序表中，从而得到一个新的、记录数增加1的有序表。

　步骤：

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

程序实现：

             1
            void InsertSort(int* _array, int _arraySize)
 2{
 3     assert(_array&&_arraySize > 0);//参数判断 4 5for (int i = 1;i < _arraySize;++i)//从数组第二个数开始插入 6    {
 7for (int j = i - 1;j >= 0;--j)
 8        {
 9if (_array[j] > _array[j + 1])//从后进行插入10            {
11                 swap(_array[j], _array[j+1]);
12            }
13else//(_array[j] <= _array[j+1])
14//进行优化,说明前面数据均小于_array[j+1]直接跳出循环15break;
16        }
17    }
18return;
19 }

效率分析：

算法稳定性：稳定

　　时间复杂度：O(n^2)

　　空间复杂度：O(1)

2.希尔排序

　　介绍：希尔排序又称"缩小增量排序"，它的基本思想是 先将整个待排序分割成1若干子序列分别进行直接插入排序，待整个序列"基本有序"时，再对全体进行一次直接插入排序。希尔排序实质上是一种分组直接插入排序然后逐步合并的过程，其在时间效率上较直接插入排序有较大改进。

　步骤：

http://www.tyut.edu.cn/kecheng1/site01/suanfayanshi/shell_sort.asp

　　　通过上述网址可彻底了解希尔排序的步骤。

　程序实现：

             1
            void ShellSort(int* _array,int _arraySize)
 2{
 3     assert(_array&&_arraySize > 0);
 4int gap = _arraySize;
 5while (gap > 1)
 6    {
 7         gap = gap / 3 + 1;//设置希尔排序增量，保证最后一次排序时gap为1即直接插入排序 8 9for (int i = gap;i < _arraySize;i += gap)//从数组第gap个元素开始10        {
11for (int j = i - gap;j >= 0;j -= gap)
12            {
13if (_array[j] > _array[j + gap])
14                {
15                     swap(_array[j], _array[j + gap]);
16                }
17elseif (gap == 1)//在最后直接插入排序时进行优化18break;
19            }
20        }
21    }
22return;
23 }

　　效率分析：

算法稳定性：不稳定

　　 时间复杂度：O(n^1.3)

　　 空间复杂度：O(1)

原文：http://www.cnblogs.com/lyl-312/p/5517685.html