C語言常見排序算法之插入排序(直接插入排序,希爾排序)
前言
本期為大家?guī)淼氖浅R娕判蛩惴ㄖ械牟迦肱判?,主要有直接插入排序以及它的升?jí)版——希爾排序,包您一看就會(huì),快來試試吧~
一、直接插入排序
1.1 基本思想
在生活當(dāng)中,這種排序方式處處可見:
在玩撲克牌的時(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)行比較,找到插入位置,原來位置上的數(shù)據(jù)元素順序往后移。
用一組實(shí)例來觀察一下是算法是怎么實(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)出來的的平均時(shí)間復(fù)雜度:O(N^1.3——N^2)。
- 4.穩(wěn)定性:不穩(wěn)定
到此這篇關(guān)于C語言常見排序算法之插入排序(直接插入排序,希爾排序)的文章就介紹到這了,更多相關(guān)C語言插入排序 內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!
相關(guān)文章
C++標(biāo)準(zhǔn)庫(kù)封裝的vector數(shù)組
這篇文章主要介紹了C++標(biāo)準(zhǔn)庫(kù)封裝的vector數(shù)組,vector創(chuàng)建的對(duì)象包含眾多封裝好的函數(shù),想了解其相關(guān)資料的小伙伴可以參考下面文章內(nèi)容,希望對(duì)你的學(xué)習(xí)有所幫助2022-03-03MFC對(duì)話框中實(shí)現(xiàn)走馬燈效果
這篇文章主要為大家詳細(xì)介紹了MFC對(duì)話框中實(shí)現(xiàn)走馬燈效果,文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下2020-05-05C語言實(shí)現(xiàn)圖的遍歷之深度優(yōu)先搜索實(shí)例
這篇文章主要介紹了C語言實(shí)現(xiàn)圖的遍歷之深度優(yōu)先搜索實(shí)例,采用不同的方法實(shí)現(xiàn)了深度優(yōu)先搜索算法,有不錯(cuò)的借鑒價(jià)值,需要的朋友可以參考下2014-09-09VC++實(shí)現(xiàn)添加文件關(guān)聯(lián)的方法示例
這篇文章主要介紹了VC++實(shí)現(xiàn)添加文件關(guān)聯(lián)的方法,涉及VC++針對(duì)注冊(cè)表的寫入與VC事件響應(yīng)相關(guān)操作技巧,需要的朋友可以參考下2017-08-08C++實(shí)現(xiàn)LeetCode(162.求數(shù)組的局部峰值)
這篇文章主要介紹了C++實(shí)現(xiàn)LeetCode(162.求數(shù)組的局部峰值),本篇文章通過簡(jiǎn)要的案例,講解了該項(xiàng)技術(shù)的了解與使用,以下就是詳細(xì)內(nèi)容,需要的朋友可以參考下2021-07-07Qt使用SqlLite實(shí)現(xiàn)權(quán)限管理的示例代碼
本文主要介紹了Qt使用SqlLite實(shí)現(xiàn)權(quán)限管理的示例代碼,管理員針對(duì)不同人員進(jìn)行權(quán)限設(shè)定,具有一定的參考價(jià)值,感興趣的可以了解一下2023-09-09C++使用HTTP庫(kù)和框架輕松發(fā)送HTTP請(qǐng)求
使用C++編程發(fā)送HTTP請(qǐng)求通常需要使用第三方的HTTP庫(kù)或框架,本文主要介紹了C++使用HTTP庫(kù)和框架輕松發(fā)送HTTP請(qǐng)求,感興趣的可以了解一下2023-12-12