掌握七大排序（1）---直接插入排序和希爾排序-創(chuàng)新互聯(lián)

💞 💞人是不能太閑的，閑久了，努力一下就以為是拼命。

目前創(chuàng)新互聯(lián)已為1000多家的企業(yè)提供了網(wǎng)站建設(shè)、域名、雅安服務(wù)器托管、網(wǎng)站托管、企業(yè)網(wǎng)站設(shè)計(jì)、南海網(wǎng)站維護(hù)等服務(wù)，公司將堅(jiān)持客戶導(dǎo)向、應(yīng)用為本的策略，正道將秉承"和諧、參與、激情"的文化，與客戶和合作伙伴齊心協(xié)力一起成長(zhǎng)，共同發(fā)展。

目錄

• • • 一.排序的概念及其運(yùn)用
  • 1.排序的概念
  • 2.排序的應(yīng)用
  • 3.常見(jiàn)的排序算法
  • • 二.直接插入排序
  • 1.基本思想
  • 2.代碼展示
  • 3.總結(jié)
  • • 三.希爾排序
  • 1.基本思想
  • 2.代碼展示
  • 3.總結(jié)

一.排序的概念及其運(yùn)用 1.排序的概念

排序：所謂排序，就是使一串記錄，按照其中的某個(gè)或某些關(guān)鍵字的大小，遞增或遞減的排列起來(lái)的操作。
穩(wěn)定性：假定在待排序的記錄序列中，存在多個(gè)具有相同的關(guān)鍵字的記錄，若經(jīng)過(guò)排序，這些記錄的相對(duì)次序保持不變，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，則稱這種排序算法是穩(wěn)定的；否則稱為不穩(wěn)定的。
內(nèi)部排序：數(shù)據(jù)元素全部放在內(nèi)存中的排序。
外部排序：數(shù)據(jù)元素太多不能同時(shí)放在內(nèi)存中，根據(jù)排序過(guò)程的要求不能在內(nèi)外存之間移動(dòng)數(shù)據(jù)的排序。

2.排序的應(yīng)用

排序的應(yīng)用可以說(shuō)貫穿我們生活的很多地方
購(gòu)物的時(shí)候，我們可以選擇綜合排序，銷量排序，評(píng)論數(shù)排序，新品排序，價(jià)格排序等等，以此來(lái)找到適合自己的商品。

3.常見(jiàn)的排序算法

本次主要介紹插入排序中的直接插入排序和希爾排序。

二.直接插入排序 1.基本思想

直接插入排序是一種簡(jiǎn)單的插入排序法，其基本思想是：
把待排序的記錄按其關(guān)鍵碼值的大小逐個(gè)插入到一個(gè)已經(jīng)排好序的有序序列中，直到所有的記錄插入完為止，得到一個(gè)新的有序序列 。
實(shí)際中我們玩撲克牌時(shí)，就用了插入排序的思想

下面是選擇排序的動(dòng)畫演示圖，方便大家理解。
當(dāng)插入第i(i>=1)個(gè)元素時(shí)，前面的array[0],array[1],…,array[i-1]已經(jīng)排好序，此時(shí)用array[i]的排序碼與
array[i-1],array[i-2],…的排序碼順序進(jìn)行比較，找到插入位置即將array[i]插入，原來(lái)位置上的元素順序后移。

2.代碼展示

在搞定排序的整個(gè)過(guò)程前，我們先搞定排序的單趟。（以從小到大排序?yàn)槔?br />直接插入排序需要保證：要插入數(shù)字的前面是已經(jīng)有序的序列即：當(dāng)插入第i(i>=1)個(gè)元素時(shí)，前面的array[0],array[1],…,array[i-1]已經(jīng)排好序
函數(shù)需要三個(gè)形參：
1.指向數(shù)組的指針，
2.數(shù)組的個(gè)數(shù)
3.要插入數(shù)字的大小

void InsertSort2(int* a, int n,int x)
{int end = n - 1;
		int tmp = x;
		while (end >= 0)
		{	if (a[end] >tmp)
			{		a[end + 1] = a[end];
				end--;
			}
			else
			{		break;
			}

		}
		a[end + 1] = tmp;

}

下面我們運(yùn)行一下看看對(duì)不對(duì)

可以看出來(lái)，沒(méi)有問(wèn)題。

下面我們開始寫排序的整個(gè)過(guò)程，我們需要在外層再加一個(gè)循環(huán)。
（第一次循環(huán)把最第一個(gè)數(shù)當(dāng)作一個(gè)有序數(shù)組，對(duì)數(shù)組第二個(gè)數(shù)進(jìn)行插入）
（第二次循環(huán)把前兩個(gè)數(shù)當(dāng)作一個(gè)有序數(shù)組，對(duì)數(shù)組第三個(gè)數(shù)進(jì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)
			{		a[end + 1] = a[end];
				end--;
			}
			else
			{		break;
			}

		}
		a[end + 1] = tmp;
	}


}

循環(huán)結(jié)束條件為i< n - 1.。 n -1是數(shù)組最后一個(gè)元素，i< n會(huì)引發(fā)數(shù)組的訪問(wèn)越界。

我們看看運(yùn)行結(jié)果如何

沒(méi)有問(wèn)題

3.總結(jié)

**直接插入排序的特性總結(jié)：

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

三.希爾排序

通過(guò)之前的總結(jié)我們知道，直接插入排序最壞的時(shí)間復(fù)雜度情況是O(N^2)。元素集合越接近有序，直接插入排序算法的時(shí)間效率越高，因此直接插入排序?qū)o(wú)序，逆序的排序耗時(shí)很大。
為了解決這個(gè)情況，我們的唐納德·希爾大佬發(fā)明了希爾排序。他是對(duì)直接插入排序的一種更高效的改進(jìn)版本。

1.基本思想

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

下面是動(dòng)圖演示

2.代碼展示

void ShellSort(int* a, int n)
{//預(yù)排序
	int gap = n;
	while (gap >1)
	{gap = gap / 3 + 1;
		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;
		}
	}
	}

測(cè)試：

沒(méi)有問(wèn)題。

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)化的效果。我們實(shí)現(xiàn)后可以進(jìn)行性能測(cè)試的對(duì)比。
3. 希爾排序的時(shí)間復(fù)雜度不好計(jì)算，因?yàn)間ap的取值方法很多，導(dǎo)致很難去計(jì)算，因此在好些樹中給出的希爾排序的時(shí)間復(fù)雜度都不固定：
   
   
4. 穩(wěn)定性：不穩(wěn)定

完結(jié)。。。

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級(jí)流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級(jí)服務(wù)器適合批量采購(gòu)，新人活動(dòng)首月15元起，快前往官網(wǎng)查看詳情吧

文章名稱：掌握七大排序（1）---直接插入排序和希爾排序-創(chuàng)新互聯(lián)
網(wǎng)站網(wǎng)址：http://muchs.cn/article16/dddegg.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供全網(wǎng)營(yíng)銷推廣、微信小程序、建站公司、動(dòng)態(tài)網(wǎng)站、響應(yīng)式網(wǎng)站、網(wǎng)站導(dǎo)航

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來(lái)源： 創(chuàng)新互聯(lián)