内排序——插入排序—直接插入(稳定)—希尔(不稳定)

一、排序

排序是计算机程序中的一种重要操作，功能是将一个任意的数据序列，重新排列为一个有序的序列。

1.排序的分类：

(1) 内排序：待排序记录存放在计算机内存中进行的排序过程，之后的排序方法都属于内排序。

(2) 外排序：待排序记录较多，需要利用到外存。

2.排序的数据分类：

(1) 存放在地址连续的一组存储单元中——顺序存储结构(常采用)

(2) 存放在静态链表

(3) 存放在地址连续的一组存储单元中，还有记录存储位置的地址向量

二、插入排序

1.直接插入排序

(1) 算法思想：中心思想——将一个记录插入到已排好序的有序表中。现有一任意数据序列arr，首先将第一个元素arr[0]看作是已排序序列，从第二个元素以后便是待排序序列，将arr[1]插入到已排序序列中合适的位置上，那么arr[0]~arr[1]便是已排序序列，再将arr[2]插入其中，以此类推...

(2) 图片解释：

                                    

               

                                     

                          

                                      

         

                                      

直到得到一个升序序列：

                                      

(3) 总体思想：

                                     

(4) 代码实现：

void insertSort(int arr[], int len)
{
	int i;//未排序序列带排序的元素下标
	int j;//已排序序列最大元素的下标
	int temp;
	for (i = 1; i < len; ++i)
	{
		temp = arr[i];
		for (j = i - 1; j >= 0 && arr[j] > temp; --j)
		{
			arr[j + 1] = arr[j];
		}
		arr[j + 1] = temp;
	}
}

      直接插入排序的时间复杂度为O(n2)，而当待排序序列为“正序”时，时间复杂度提高至O(n)。直接插入排序在n值(数据的个数)很小时效率很高，鉴于这个对直接插入排序进行改进得到另一种插入排序——希尔算法。

2. 希尔排序

(1) 算法思想：

希尔排序是直接插入排序的优化版，在后者的基础上减少       ，提高了排序的效率。

先将数组按照某个增量分割为若干个序列，将每个子序列中的第一个元素看作为“已排序序列”，对子序列后面的“待排序序列”进行直接插入排序，使得这些子序列内部有序，再减少增量，分割上次得到的数据，操作同上.....待整个序列中的记录“基本有序”时，最后对全体记录进行增量为1的直接插入排序，得到已排序数据。

希尔排序中的“若干个序列”是指：将相隔某个“增量”的记录组成一个子序列。

例如，当增量为5时：

相同颜色的线两端连接的两个元素，组成了一个子序列。上图一共有10个元素，增量为5时，一共有5个子序列。

(2) 图形：

1.增量——5

得排序结果：

增量——3：

得排序结果：

增量——1：

(3) 希尔排序需要注意的方面：

希尔排序的时间复杂度是它所取“增量”序列的函数，并没有一种最好的增量序列，增量序列的取法非常多。

一般地，选取的增量序列需要遵循：

1. 增量序列中的值没有除1之外的公因子

2. 最后一个增量值为1

(4) 代码实现：

void shell(int arr[], int len, int dk)
{
	int i, j;
	int temp;
	for (i = dk; i < len; ++i)
	{
		temp = arr[i];
		for (j = i - dk; j >= 0 && arr[j] > temp; j -= dk)
		{
			arr[j + dk] = arr[j];
		}
		arr[j + dk] = temp;
	}
}
void shellSort(int arr[], int arrlen, int dka[], int dkalen)
{
	for (int i = 0; i < dkalen; ++i)
	{
		shell(arr, arrlen, dka[i]);
	}
}

希尔排序的时间复杂度为O(n)，并且它并不稳定。