前言

本期為大家?guī)?lái)的是常見(jiàn)排序算法中的插入排序，主要有直接插入排序以及它的升級(jí)版——希爾排序，包您一看就會(huì)，快來(lái)試試吧~

一、直接插入排序

1.1 基本思想

在生活當(dāng)中，這種排序方式處處可見(jiàn)：

在玩撲克牌的時(shí)候我們就會(huì)采用插入排序的思想，當(dāng)我們拿起第二張牌時(shí)，就會(huì)下意識(shí)的與第一張牌進(jìn)行比較，如果比第一張牌小，我們則將牌插入至第一張牌的左邊，反之就插入至右邊（升序）。以圖為例：我們拿起一張7，發(fā)現(xiàn)比最后一張牌10小，自然7與10就要交換位置，交換完成后，發(fā)現(xiàn)7前面的數(shù)字比自己小，就不用交換了，所以就找到7的位置了。

我們會(huì)發(fā)現(xiàn)，在拿起一張牌準(zhǔn)備插入時(shí)，待插入的區(qū)間已經(jīng)是有序的，我們要做的是，插入后使區(qū)間依舊有序。

1.2 算法思想

當(dāng)插入第 i (i>=1)個(gè)元素時(shí)，前面的array[0],a[1]……a[i-1] 已經(jīng)排序好，此時(shí)用a[i]的排序碼與     a[i-1],a[i-2]……進(jìn)行比較，找到插入位置，原來(lái)位置上的數(shù)據(jù)元素順序往后移。

用一組實(shí)例來(lái)觀察一下是算法是怎么實(shí)現(xiàn)的的：

1.3 程序?qū)崿F(xiàn)

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>

//打印數(shù)據(jù)
void Print(int* a,int  n)
{
	for (int i=0;i<n;++i)
	{
		printf("%d ",a[i]);
	}
	printf("\n");
}
 
//直接插入排序
void InsertSort(int *a, int n)//升序
{
	for (int i=0;i<n-1;++i)
	{
		int end = i;
		int tmp = a[end + 1];;
		while (end>=0)
		{
			if (a[end] > tmp)//修改此處符號(hào)即可升序降序切換
			{
				a[end+1] = a[end];
				--end;
			}
			else
			{
				break;
			}
			a[end + 1] =tmp;
		}
	}
	//打印數(shù)據(jù)
	Print(a,n);
}
 
int main()
{
	int a[6] = { 5,2,4,6,1,3 };
	//直接插入排序
	InsertSort(a,sizeof(a)/sizeof(a[0]));
	return 0;
}

1.4 直接插入排序的總結(jié)

• 1.元素集合越接近有序，直接插入排序算法時(shí)間效率越高
• 2.時(shí)間復(fù)雜度：O(N^2)(最壞情況) ，最好情況時(shí)間復(fù)雜度是O(N);
• 3.空間復(fù)雜度：O(1),是一種穩(wěn)定的排序算法
• 4.穩(wěn)定性：穩(wěn)定

二、希爾排序

希爾排序是一種特殊的插入排序，是直接插入排序基礎(chǔ)上的優(yōu)化。

2.1 算法思想

希爾排序又稱為縮小增量法，希爾排序的基本思想是：先選定一個(gè)整數(shù)，把待排序文件中所有記錄分成若干個(gè)組，所有距離為“gap”的記錄分在同一組內(nèi)，并對(duì)每一個(gè)組內(nèi)的記錄進(jìn)行排序。然后，取，重復(fù)上述分組和排序工作。當(dāng)“gap”（間隔）==1，所有記錄在統(tǒng)一組內(nèi)排好序。

• 1.先進(jìn)行預(yù)排序，使數(shù)組接近有序
• 2.直接插入排序

預(yù)排序：分組排，間隔為 gap 是一組，假設(shè) gap ==3;

9 8 7 6 5 4 3 2 1 0,如果將這組數(shù)據(jù)升序排序，使用直接插入排序，算法的復(fù)雜度就是 O(N^2);

每個(gè) gap 間隔的小分組都再進(jìn)行插入排序。

優(yōu)點(diǎn)：大數(shù)，小數(shù)更快的到達(dá)兩端，當(dāng)gap等于1時(shí)，就是直接插入排序，這時(shí)候時(shí)間復(fù)雜度就是大大降低。

2.2 程序?qū)崿F(xiàn)

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
 
//希爾排序
void ShellSort(int* a, int n)//升序
{
	int gap = n;
	while (gap > 1)//當(dāng)gap等于1時(shí)，就是直接插入排序
	{
		gap = gap / 2;
		//把間隔為gap的多組數(shù)據(jù)同時(shí)排序
		for (int i = 0; i < n - gap; i++)
		{
			int end = i;
			int tmp = a[end + gap];
			while (end>=0)
			{
				if (a[end] > tmp)
				{
					a[end + gap] = a[end];
					end -= gap;
				}
				else
				{
					break;
				}
				a[end + gap] = tmp;
			}
		}
	}
	//打印數(shù)據(jù)
	Print(a, n);
}
int main()
{
	int a[10] = { 9,8,7,6,5,4,3,2,1,0 };
	//希爾排序
	ShellSort(a, sizeof(a) / sizeof(a[0]));
	return 0;
}

2.3 希爾排序的特征總結(jié)

• 1.希爾排序是對(duì)直接插入排序的優(yōu)化。
• 2.當(dāng)gap>1時(shí)都是預(yù)排序，目的是讓數(shù)組更接近于有序。當(dāng)gap==1時(shí)，數(shù)組已經(jīng)接近有序，這樣就會(huì)很快。整體而言，可以達(dá)到優(yōu)化的效果。
• 3.希爾排序的時(shí)間復(fù)雜度不好計(jì)算，需要根據(jù)數(shù)據(jù)進(jìn)行推導(dǎo)，推導(dǎo)出來(lái)的的平均時(shí)間復(fù)雜度：O(N^1.3——N^2)。
• 4.穩(wěn)定性：不穩(wěn)定

到此這篇關(guān)于C語(yǔ)言常見(jiàn)排序算法之插入排序(直接插入排序,希爾排序)的文章就介紹到這了,更多相關(guān)C語(yǔ)言插入排序 內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評(píng)論