浅谈数据结构排序算法中的直接插入排序

2020-02-18

数据结构中的排序算法有：插入类排序、交换类排序、选择排序、堆排序、归并排序、桶排序。而插入类排序包括：直接插入排序、折半插入排序、希尔排序。

直接插入排序（稳定的排序）

原理步骤：

1）首先：取一个元素（一般为第一个元素）

2）其次，把这个元素当成是一个有序的序列（即：元素个位为一的有序序列）

3）然后，将剩下的元素依次插入到当前的这个有序序列的对应位置上

注：下列两种方法都是从小到大排序

方法一：建立哨兵（A[0]为哨兵，类似于中介变量，用于暂存元素值）

#include <iostream>

using namespace std;

#define  ElemType int

int A[] = {10,3,11,7,6};//A[0]为哨兵，其值无效，即：只对A[1]-A[4]进行排序
int n =4;//对除了A[0]元素以为的A[1]-A[4]进行排序

void InsertSort(ElemType A[], int n)//直接插入排序执行函数
{
	int i, j;
	for (i = 2;i <= n;i++)
	//i=2：第一个元素A[1]当成是有序序列，所以从第二个元素A[2]开始进行循环插入
	//i <= n：A[0]为哨兵，从A[2]到A[n-1]进行排序
	//注：n是扣除A[0]后数组内元素的个数，即：数组内元素个数为：n+1
		if (A[i] < A[i - 1])//如果当前元素比上一个位置的元素的值还小
		{
			A[0] = A[i];//那就先将该值先寄放在哨兵那边（即：A[0]）
			for (j = i - 1;A[0] < A[j];j--)//当寄放在哨兵的值比当前位置的元素值小的时候，继续向前查找
				A[j + 1] = A[j];//向前查找的同时，把那些比哨兵值大的元素都依次向后挪动一个位置
			A[j + 1] = A[0];//直到找到合适的位置位置后，才将哨兵值放在对应的位置上
		}
   //接着对下一个位置的元素继续执行直接插入排序，直到所有元素都插入到对应位置后才跳出当前for循环
}

int main()
{
	cout << "哨兵为A[0]，其值无效，仅用于暂存数值，A[0]初值为："<<A[0]<<endl;//该位置A[0]为哨兵，其内值无效，相当于是个中间变量，用于数值的暂时存放。
	InsertSort(A, n);//调用直接插入排序算法
	cout << "数组A[]的最终排序为：";
	for(int z=1;z<=n;z++)//A[1]开始显示直到A[n]；A[]元素个数为n+1，其中A[0]无效
		cout << A[z]<<"  ";//输出数组排序结果
}

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

空间复杂度：O(1) 注：哨兵A[0]（常数个空间）

方法二：设定一个中间变量temp（主流）

#include <iostream>

using namespace std;

#define  ElemType int

int A[] = { 10,3,11,7,6 };
int n = 5;//A[]中有5个元素，或者在主函数内写n=size(A);从而获取数组A[]的大小
void  InsertSort(ElemType A[], int n)//直接插入排序执行函数
{
	int i, j;
	ElemType temp;//定义中间变量temp，用于暂存数组元素的值
	for (i = 1;i < n;i++)//从A[1]开始进行循环，直到整个数组循环一遍，A[0]默认为已经排号了位置
	{
		temp = A[i];//把当前数组的元素值先暂存在temp中
		j = i - 1;//从已经插入完成的有序序列的最末尾开始向前进行寻找适合的插入位置
		while (temp < A[j] && j >= 0)
		//进入while循环，直到满足找到合适的插入位置或者是已经找遍了整个有序序列（当前有序序列的值都比该temp暂存的值大）
		{
			A[j + 1] = A[j];//把已经排好的有序序列都向后挪动一个位置
			j--;
		}
		A[j + 1] = temp;//找到对应位置，执行插入
		//注：因为while循环最后执行j--；所以多件减了一个位置，因此当前的正确插入位置为A[j+1]
	}

}

int main()
{
    InsertSort(A, n);//调用直接插入排序算法
    cout << "数组A[]的最终排序为：";
    for(int x=0;x<n;x++)//显示A[0]-A[n-1]
        cout << A[x]<<"  ";//输出数组排序结果
}

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

空间复杂度：O(1) 注：中间变量temp（常数个空间）`