插入排序-排序算法

发布时间:2024年01月10日

前言

在玩斗地主的时候,你是如何理牌的?

当我们手中没扑克牌时,不管抓的是什么牌,都是放到手里。其他时候拿到一张牌,是从右向左找一个位置:右边是大于这张牌,左边是小于等于这张牌或者左边没有牌。而插入排序的思想就是这个。

插入排序

插入排序:它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。在实现上,通常采用in-place排序(即只需用到O(1)的额外空间的排序),因为在从后向前扫描的过程中,需要反复把已排序的元素逐步向后挪位,为新元素提供插入空间。

具体描述如下:

1.从第一个元素开始,该元素可以认为已经被排序;

2.取出下一个元素,在已经排序的元素序列中从后向前扫描;

3.如果该元素(己排序)大于新元素,将该元素移到下一位置;
重复步骤3,直到找到己排序的元素小于或者等于新元素的位置。

4.将新元素插入到该位置;

重复步骤2~5

例子

下面提供一个例子直观地展示前面的概念,以这一组数据:18,14,10,19,1,3 为例。

1.首先从第一个元素 18 开始考虑,因为只有一个,认为已经有序(有序序列用橙色表示)。

2.选取下一个元素 14 保存起来,并让 14 所在的位置空出来,在有序的序列中从后往前遍历。

3.元素 18 大于新元素 14 ,将元素 18 向后移动。

4.元素 18 前已经没有元素了,将刚刚保存的元素 14 放到空位。这样,14这个新元素就加入了有序序列。

5.选取下一个元素 10 保存起来,并让10所在的位置空出,在有序的序列中从后向前扫描。

6.元素 18 大于 10 , 18 向后移一位。

7.元素 14 大于 10,14向后移动。

8.元素 14 前已经没有数了,将刚刚保存下来的元素 10?放到空位中。这样,有序序列又加入了一个数 10。

9.选取下一个元素 19 保存起来,让其所在位置空出,在有序序列中由后到前比较。

10.不断比较,直到找到小于等于新元素的位置,恰好第一次比较就找到了 18 ,把 19 放入空位。

……

这样重复地比较、挪位,放入位置。就能得到有序的整个数组。

代码

也许上面这个过程你能明白,可是代码才是解决问题的。

#include <iostream>
using namespace std;


void InsertSort(int arr[], int left, int right)
{
	int current = 0; // 保存要插入的元素的值(新元素)
	int preindex = 0; // 指向有序序列中的数

	for (int i = left + 1; i <= right; i++)
	{
		current = arr[i];
		preindex = i - 1;
		while (preindex >= left && arr[preindex] > current)
		{
			arr[preindex + 1] = arr[preindex];
			preindex--;
		} //循环结束后就找到了合适的位置的前一个位置

		arr[preindex + 1] = current;
	}

}


int main(void)
{
	int arr[] = { 18,14,10,19,1,3 };
	int len = sizeof(arr) / sizeof(arr[0]);

	InsertSort(arr, 0, len - 1);

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

文章来源:https://blog.csdn.net/qq_66805048/article/details/135507821
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。