下列所有排序都默认是升序，从小到大。

插入排序

有一个已经有序的数据序列，要求在这个已经排好的数据序列中插入一个数，但要求插入后此数据序列仍然有序，这个时候就要用到一种新的排序方法——插入排序法,插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中，从而得到一个新的、个数加一的有序数据，算法适用于少量数据的排序，时间复杂度为O(n^2)。是稳定的排序方法。插入算法把要排序的数组分成两部分：第一部分包含了这个数组的所有元素，但将最后一个元素除外（让数组多一个空间才有插入的位置），而第二部分就只包含这一个元素（即待插入元素）。在第一部分排序完成后，再将这个最后元素插入到已排好序的第一部分中。

直接插入排序

插入排序的过程

插入排序就像有的人打扑克一样，每次摸起来一张牌后，在手中已经排序好的扑克中插入当前摸起的这张牌。问题的关键点就是：如何在已经排好序的序列中，找到当前元素该插入的位置。

当序列中只有一个元素时，不需要排序，因为一个元素已经有序。

现在来考虑有多个元素的过程：

循环内：

我们可以先把当前把插入的元素先保存起来，然后分别将刚才保存起来的元素与有序序列中的每一个元素比较，那么比较到什么时候才停下来？

a. 出现一个比保存的元素小的元素（saveNum < array[ i ] ）；

b.以序队列已经比较完毕（i >=0 ）。

因为以序队列的范围是从 0 .. 当前插入元素位置 -1 ， 所以我们需要一个循环来完成比较和搬迁元素。

当循环条件不满足时，即找到插入位置。直接插入即可。

参考代码：

void InsertSort(int* array, int size)
{
	if (array == NULL || size <= 0)
		return;

	// 从数组第二个元素开始处理，因为一个元素已经有序
	for (int i = 1; i < size; i++)
	{
		int temp = array[i];
		int end = i - 1;
		
		// 插入array[i] 到已序序列中 array[0.. i-1]
		while (end >= 0 && temp < array[end])
		{
			array[end + 1] = array[end];
			end--;
		}

		// 插入 array[i]
		array[end + 1] = temp;
	}
}

// 打印数组
void PrintfArray(string info , int* array, int size)
{
	cout << info << ":";
	for (int i = 0; i < size - 1; ++i)
		cout << array[i] << " ";
	cout << endl;
}

int main()
{
	int array[] = {5, 9, 1, 6, 2, 4, 7, 8, 0 , 2, 0};
	int size = sizeof(array) / sizeof(array[0]);
	PrintfArray("排序前", array, size);
	InsertSort(array, size);
	PrintfArray("排序后", array, size);
	return 0;
}

二分插入排序

void InsertSort_Binary(int * array, int size)
{
	if (array == NULL || size <= 0)
		return;

	for (int i = 1; i < size; ++i)
	{
		
		int temp = array[i];

		int left = 0;     // 有序序列的左边界
		int right = i - 1;// 有序序列的右边界

		while (left <= right)
		{
			int mid = (left + right) / 2;
			// 注意这里的 等号，为了保证算法的稳定性（相同关键字排序前后位置不会变）
			// 所以也需要向后移动
			if (array[mid] <= temp)
				left = mid + 1;
			else if (array[mid] > temp)
				right = mid - 1;
			
		}

		// 搬移数据， 上面循环结束后，left的位置就是插入位置
		// 需要将从left 到 当前插入元素的前一个位置都搬移一个位置
		for (int j = i - 1; j >= left; --j)
		{
			array[j + 1] = array[j];
		}
		array[left] = temp;
	}
}

希尔排序

void ShellSort(int*array , int size)
{
	int gap = 3;
	while (gap > 0)
	{
		for (int idx = gap; idx < size; idx += gap)
		{
			int temp = array[idx];

			int end = idx - gap;
			while (end >= 0 && array[end] > temp)
			{
				array[end + gap] = array[end];
				end -= gap;
			}
			array[end + gap] = temp;
		}
		gap--;
	}
}

最后

以上就是高贵纸鹤为你收集整理的排序算法之直接插入排序、二分插入排序和希尔排序插入排序直接插入排序二分插入排序希尔排序的全部内容，希望文章能够帮你解决排序算法之直接插入排序、二分插入排序和希尔排序插入排序直接插入排序二分插入排序希尔排序所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。