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

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

目錄

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

一.排序的概念及其運用 1.排序的概念

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

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

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

3.常見的排序算法

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

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

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

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

2.代碼展示

在搞定排序的整個過程前，我們先搞定排序的單趟。（以從小到大排序為例）
直接插入排序需要保證：要插入數(shù)字的前面是已經(jīng)有序的序列即：當(dāng)插入第i(i>=1)個元素時，前面的array[0],array[1],…,array[i-1]已經(jīng)排好序
函數(shù)需要三個形參：
1.指向數(shù)組的指針，
2.數(shù)組的個數(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;

}

下面我們運行一下看看對不對

可以看出來，沒有問題。

下面我們開始寫排序的整個過程，我們需要在外層再加一個循環(huán)。
（第一次循環(huán)把最第一個數(shù)當(dāng)作一個有序數(shù)組，對數(shù)組第二個數(shù)進(jìn)行插入）
（第二次循環(huán)把前兩個數(shù)當(dāng)作一個有序數(shù)組，對數(shù)組第三個數(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ù)組最后一個元素，i< n會引發(fā)數(shù)組的訪問越界。

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

沒有問題

3.總結(jié)

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

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

三.希爾排序

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

1.基本思想

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

下面是動圖演示

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;
		}
	}
	}

測試：

沒有問題。

3.總結(jié)

1. 希爾排序是對直接插入排序的優(yōu)化。
2. 當(dāng)gap >1時都是預(yù)排序，目的是讓數(shù)組更接近于有序。當(dāng)gap == 1時，數(shù)組已經(jīng)接近有序的了，這樣就會很快。這樣整體而言，可以達(dá)到優(yōu)化的效果。我們實現(xiàn)后可以進(jìn)行性能測試的對比。
3. 希爾排序的時間復(fù)雜度不好計算，因為gap的取值方法很多，導(dǎo)致很難去計算，因此在好些樹中給出的希爾排序的時間復(fù)雜度都不固定：
   
   
4. 穩(wěn)定性：不穩(wěn)定

完結(jié)。。。

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

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

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

廣告

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