欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

C語言常見排序算法之插入排序(直接插入排序,希爾排序)

 更新時(shí)間:2022年07月14日 09:35:41   投稿:hqx  
這篇文章介紹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ù)組

    這篇文章主要介紹了C++標(biāo)準(zhǔn)庫(kù)封裝的vector數(shù)組,vector創(chuàng)建的對(duì)象包含眾多封裝好的函數(shù),想了解其相關(guān)資料的小伙伴可以參考下面文章內(nèi)容,希望對(duì)你的學(xué)習(xí)有所幫助
    2022-03-03
  • MFC對(duì)話框中實(shí)現(xiàn)走馬燈效果

    MFC對(duì)話框中實(shí)現(xiàn)走馬燈效果

    這篇文章主要為大家詳細(xì)介紹了MFC對(duì)話框中實(shí)現(xiàn)走馬燈效果,文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下
    2020-05-05
  • c語言獲取文件大小的示例

    c語言獲取文件大小的示例

    在C語言中測(cè)試文件的大小,主要使用二個(gè)標(biāo)準(zhǔn)函數(shù),下面是使用示例,需要的朋友可以參考下
    2014-02-02
  • C語言實(shí)現(xiàn)圖的遍歷之深度優(yōu)先搜索實(shí)例

    C語言實(shí)現(xiàn)圖的遍歷之深度優(yōu)先搜索實(shí)例

    這篇文章主要介紹了C語言實(shí)現(xiàn)圖的遍歷之深度優(yōu)先搜索實(shí)例,采用不同的方法實(shí)現(xiàn)了深度優(yōu)先搜索算法,有不錯(cuò)的借鑒價(jià)值,需要的朋友可以參考下
    2014-09-09
  • VC++實(shí)現(xiàn)添加文件關(guān)聯(lián)的方法示例

    VC++實(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-08
  • C++通信新特性協(xié)程詳細(xì)介紹

    C++通信新特性協(xié)程詳細(xì)介紹

    這篇文章主要給大家分享得是C++的特性協(xié)程Coroutine,下面文章內(nèi)容我們將來具體介紹什么是協(xié)程,協(xié)程得好處等知識(shí)點(diǎn),需要的朋友可以參考一下
    2022-10-10
  • C語言技巧提升之回調(diào)函數(shù)的掌握

    C語言技巧提升之回調(diào)函數(shù)的掌握

    這篇文章主要為大家詳細(xì)介紹一下C語言中回調(diào)函數(shù)的用法教程,文中的示例代碼講解詳細(xì),對(duì)我們學(xué)習(xí)C語言有一定幫助,需要的可以參考一下
    2022-12-12
  • C++實(shí)現(xiàn)LeetCode(162.求數(shù)組的局部峰值)

    C++實(shí)現(xiàn)LeetCode(162.求數(shù)組的局部峰值)

    這篇文章主要介紹了C++實(shí)現(xiàn)LeetCode(162.求數(shù)組的局部峰值),本篇文章通過簡(jiǎn)要的案例,講解了該項(xiàng)技術(shù)的了解與使用,以下就是詳細(xì)內(nèi)容,需要的朋友可以參考下
    2021-07-07
  • Qt使用SqlLite實(shí)現(xiàn)權(quán)限管理的示例代碼

    Qt使用SqlLite實(shí)現(xiàn)權(quán)限管理的示例代碼

    本文主要介紹了Qt使用SqlLite實(shí)現(xiàn)權(quán)限管理的示例代碼,管理員針對(duì)不同人員進(jìn)行權(quán)限設(shè)定,具有一定的參考價(jià)值,感興趣的可以了解一下
    2023-09-09
  • C++使用HTTP庫(kù)和框架輕松發(fā)送HTTP請(qǐng)求

    C++使用HTTP庫(kù)和框架輕松發(fā)送HTTP請(qǐng)求

    使用C++編程發(fā)送HTTP請(qǐng)求通常需要使用第三方的HTTP庫(kù)或框架,本文主要介紹了C++使用HTTP庫(kù)和框架輕松發(fā)送HTTP請(qǐng)求,感興趣的可以了解一下
    2023-12-12

最新評(píng)論