国产 无码 综合区,色欲AV无码国产永久播放,无码天堂亚洲国产AV,国产日韩欧美女同一区二区

  1. Toy模板網(wǎng)首頁(yè)
  2. >Toy博客

數(shù)據(jù)結(jié)構(gòu)——C語(yǔ)言實(shí)現(xiàn)常見(jiàn)排序(插入排序、希爾排序、選擇排序、堆排序、冒泡排序)

2年前作者：玩鐵的sinZz分類(lèi)：Toy博客閱讀(90)違法舉報(bào)

這篇具有很好參考價(jià)值的文章主要介紹了數(shù)據(jù)結(jié)構(gòu)——C語(yǔ)言實(shí)現(xiàn)常見(jiàn)排序(插入排序、希爾排序、選擇排序、堆排序、冒泡排序)。希望對(duì)大家有所幫助。如果存在錯(cuò)誤或未考慮完全的地方，請(qǐng)大家不吝賜教，您也可以點(diǎn)擊"舉報(bào)違法"按鈕提交疑問(wèn)。

引言：

現(xiàn)在是北京時(shí)間2023年6月23日13點(diǎn)19分，度過(guò)了一個(gè)非常愉快的端午節(jié)。由于剛從學(xué)校回家，一下子伙食強(qiáng)度直升了個(gè)兩三個(gè)檔次。這也導(dǎo)致我的腸胃不堪重負(fù)，我也準(zhǔn)備等會(huì)去健身房消耗一下盈余的熱量?；氐郊遗惆闋敔斪呷松詈蟮碾A段才是我這個(gè)暑假最重要的事情。自從爺爺病重后，起居都需要家人照顧，我不僅感慨歲月奪人吶。興許五六十年后，子孫也能夠在我人生最后的階段陪伴我吧。
數(shù)據(jù)結(jié)構(gòu)——C語(yǔ)言實(shí)現(xiàn)常見(jiàn)排序(插入排序、希爾排序、選擇排序、堆排序、冒泡排序)

排序的概念

所謂排序，就是使一組數(shù)據(jù)，按照其中的某個(gè)或某些關(guān)鍵字的大小，遞增或遞減的排列起來(lái)的操作。在日常生活中處處都有排序，比如學(xué)校的考試中會(huì)有對(duì)成績(jī)進(jìn)行排序、當(dāng)我們購(gòu)物時(shí)會(huì)有對(duì)銷(xiāo)量或價(jià)格等進(jìn)行排序。
合理對(duì)排序穩(wěn)定性做一下介紹，假設(shè)在待排序的數(shù)據(jù)中，存在多個(gè)具有相同的關(guān)鍵字的數(shù)據(jù)，若經(jīng)過(guò)排序，這些記錄的相對(duì)順序保持不變，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，則稱(chēng)這種排 序算法是穩(wěn)定的;否則稱(chēng)為不穩(wěn)定的。

插入排序

思想

插入排序的思想其實(shí)類(lèi)似我們玩撲克牌時(shí)，每次抓牌都會(huì)進(jìn)行一次排序。這里就按升序來(lái)說(shuō)，每一次插入排序都是將要排序的數(shù)據(jù)和它前面的數(shù)據(jù)作比較，當(dāng)需要排序的數(shù)據(jù)比前面小就交換，并將它向前移，比它大的數(shù)據(jù)往后挪，直到前面的數(shù)據(jù)比它小或者排序的數(shù)據(jù)下標(biāo)已經(jīng)小于0就停止單趟排序。
數(shù)據(jù)結(jié)構(gòu)——C語(yǔ)言實(shí)現(xiàn)常見(jiàn)排序(插入排序、希爾排序、選擇排序、堆排序、冒泡排序)

單趟排序代碼實(shí)現(xiàn)

根據(jù)插入排序的思想，我們從1下標(biāo)位置開(kāi)始插入數(shù)據(jù)進(jìn)行排序，所以當(dāng)前一個(gè)數(shù)據(jù)比后一個(gè)數(shù)據(jù)大的時(shí)候，我們就進(jìn)行交換。直到插入的位置小于數(shù)組的有效范圍就停止單趟排序。這樣小的數(shù)就會(huì)往前移動(dòng)，大的數(shù)整體往后挪動(dòng)。

        int end ;//用于表示當(dāng)前數(shù)據(jù)的下標(biāo)
        int tmp ;//插入數(shù)據(jù)的值
        while(end >= 0)
        {
        //前一個(gè)數(shù)比它小就覆蓋
            if(tmp < arr[end])
            {
                arr[end+1] = arr[end];
                end--;
            }
         //否則就結(jié)束單趟排序
            else
            {
                break;
            }
        }

完整代碼實(shí)現(xiàn)

有了單趟排序的實(shí)現(xiàn)，我們根據(jù)整體的思想就可以寫(xiě)出外循環(huán)。即外循環(huán)從1開(kāi)始到n-1結(jié)束。當(dāng)單趟排序結(jié)束時(shí)，需要對(duì)超出數(shù)組范圍的數(shù)重新寫(xiě)回?cái)?shù)組內(nèi)。例如當(dāng)end == -1 時(shí)就要將它寫(xiě)會(huì)0下標(biāo)處。

//插入排序——升序
void InsertSort(int* arr, int n)
{
    for(int i = 1; i < n;i++)
    {
        int end = i - 1 ;
        int tmp = arr[i];
        while(end >= 0)
        {
            if(tmp < arr[end])
            {
                arr[end+1] = arr[end];
                end--;
            }
            else
            {
                break;
            }
        }
        arr[end+1] = tmp;
    }
}

特性總結(jié)

一、當(dāng)數(shù)據(jù)越接近有序插入排序的效率越高，排升序時(shí)，當(dāng)數(shù)據(jù)為升序（最好情況），插入排序的時(shí)間復(fù)雜度為O(N)。因?yàn)樽詈们闆r只需要遍歷n-1次數(shù)據(jù)并進(jìn)行判斷即可。
二、最壞情況下，插入排序的時(shí)間復(fù)雜度為O(N^2)。即排升序時(shí)，當(dāng)數(shù)據(jù)為降序。因?yàn)槊看螁翁伺判蚺矂?dòng)數(shù)據(jù)的時(shí)間復(fù)雜度為O(N)，整體要走N-1趟排序，所以時(shí)間復(fù)雜度為O(N ^ 2)。
三、插入排序的時(shí)間復(fù)雜度為O(N^2),空間復(fù)雜度為O(1)。
四、插入排序是一種穩(wěn)定的排序。排序穩(wěn)定性的定義為排序前后數(shù)組內(nèi)相同元素的相對(duì)位置不變。

希爾排序

思想

希爾排序也稱(chēng)縮小增量排序，思想為取一個(gè)整數(shù)位分組的標(biāo)識(shí)，這里我就用gap來(lái)表示這個(gè)值，將待排的數(shù)據(jù)按照gap步的差距分成多組。并對(duì)這個(gè)多組數(shù)據(jù)進(jìn)行直接插入排序以讓它們?cè)絹?lái)越接近有序，一開(kāi)始gap值比較大，大的數(shù)就會(huì)快速往后挪，小的數(shù)就會(huì)被往前推。隨著gap逐漸變小，數(shù)據(jù)越來(lái)越接近有序，最后當(dāng)gap=1時(shí)，數(shù)據(jù)已經(jīng)接近有序，此時(shí)就會(huì)進(jìn)行直接插入排序。
數(shù)據(jù)結(jié)構(gòu)——C語(yǔ)言實(shí)現(xiàn)常見(jiàn)排序(插入排序、希爾排序、選擇排序、堆排序、冒泡排序)

數(shù)據(jù)結(jié)構(gòu)——C語(yǔ)言實(shí)現(xiàn)常見(jiàn)排序(插入排序、希爾排序、選擇排序、堆排序、冒泡排序)

單趟排序代碼實(shí)現(xiàn)

單趟排序的實(shí)現(xiàn)思路同插入排序，不同的是，單趟排序這里因?yàn)橐纸M，所以是以組間隔gap來(lái)分組進(jìn)行單趟排序，最后一趟當(dāng)gap==1時(shí)，就是插入排序了。

	int end;
	int tmp;
	while(end >= 0)
	{
	    if(tmp < arr[end])
	    {
	        arr[end+gap] = arr[end];
	        end-= gap;
	    }
	    else
	    {
	        break;
	    }
	}

代碼實(shí)現(xiàn)

這里gap的取法有很多種，大部分都是/2或者/3+1取gap值。我這里就以/2為例寫(xiě)。外循環(huán)的控制的邏輯大體來(lái)說(shuō)就是控制gap使區(qū)間局部有序，最后當(dāng)gap==1時(shí)，直接在接近有序的數(shù)組上進(jìn)行插入排序。下面代碼可以參考，具體的寫(xiě)法看個(gè)人喜好，思想上基本都是大差不差的。

//希爾排序——升序
void ShellSort(int* arr, int n)
{
    int gap = n;
    while(gap > 1)
    {
        gap/=2;
        for(int i = 0; i < n-gap;i++)
        {
            int end = i ;
            int tmp = arr[i+gap];
            while(end >= 0)
            {
                if(tmp < arr[end])
                {
                    arr[end+gap] = arr[end];
                    end-= gap;
                }
                else
                {
                    break;
                }
            }
            arr[end+gap] = tmp;
        }
    }
}

特性總結(jié)

一、希爾排序其實(shí)就是對(duì)直接插入排序的優(yōu)化。通過(guò)根據(jù)gap分組先預(yù)排序極大程度的優(yōu)化了直接插入排序最壞情況時(shí)的窘迫狀況，可以快速讓大的數(shù)后挪，小的數(shù)前移。
二、當(dāng)gap大于1時(shí)，都是預(yù)排序，目的是讓數(shù)組更加接近有序，優(yōu)化直接插入排序的次數(shù)。這對(duì)于直接插入排序思想是個(gè)極大程度的優(yōu)化，效率較高。
三、由于gap取值方面并沒(méi)有一個(gè)比較官方統(tǒng)一的數(shù)值，但是必須保證gap最后一次必須是1。所以時(shí)間復(fù)雜度方面并沒(méi)有辦法進(jìn)行一個(gè)標(biāo)準(zhǔn)的定義。這里就引用一下嚴(yán)老師的內(nèi)容來(lái)對(duì)此進(jìn)行一個(gè)比較好的解釋。
數(shù)據(jù)結(jié)構(gòu)——C語(yǔ)言實(shí)現(xiàn)常見(jiàn)排序(插入排序、希爾排序、選擇排序、堆排序、冒泡排序)
希爾排序的時(shí)間復(fù)雜度O(N^1.3)，由此也可以把希爾排序納入O(NLogN)這個(gè)時(shí)間復(fù)雜度量級(jí)的排序當(dāng)中。當(dāng)N越來(lái)越大時(shí)，N ^1.3次方比起NLogN還是又不小的差距
數(shù)據(jù)結(jié)構(gòu)——C語(yǔ)言實(shí)現(xiàn)常見(jiàn)排序(插入排序、希爾排序、選擇排序、堆排序、冒泡排序)
四、希爾排序是不穩(wěn)定的排序，因?yàn)榭赡茉趃ap分組預(yù)排序順序可能會(huì)受到影響。

選擇排序

思想

就是每一次遍歷整個(gè)數(shù)組，求出整個(gè)數(shù)組的最大值/最小值并把它放到合適的位置就完成單趟排序。根據(jù)每一次遍歷數(shù)組都可以求出最大值和最小值，也可以將選擇排序優(yōu)化為一次將最大值和最小值放到合適的位置。不過(guò)需要進(jìn)行特殊判斷避免left和max重疊問(wèn)題，導(dǎo)致交換后，無(wú)法讓max到合適的位置。然后沖復(fù)上述步驟直到區(qū)間內(nèi)只有一個(gè)數(shù)據(jù)，則排序結(jié)束。
數(shù)據(jù)結(jié)構(gòu)——C語(yǔ)言實(shí)現(xiàn)常見(jiàn)排序(插入排序、希爾排序、選擇排序、堆排序、冒泡排序)

單趟排序代碼實(shí)現(xiàn)

遍歷數(shù)組，找出最大和最小值并把它們挪到對(duì)應(yīng)的下標(biāo)位置處。需要注意的是由于同時(shí)找大和找小，所以要避免重疊特殊判斷，否則會(huì)有覆蓋數(shù)據(jù)的情況出現(xiàn)。

 //每一次找出區(qū)間內(nèi)最大和最小的數(shù)
	int mini;
	int maxi;
	for(int i = left + 1; i <= right; i++)
	{
	    if(arr[mini] > arr[i])
	        mini = i;
	    if(arr[maxi] < arr[i])
	        maxi = i;
	}
	//由于同時(shí)找大和找小，所以要避免重疊特殊判斷
	Swap(&arr[left],&arr[mini]);
	if(maxi == left)
	    maxi = mini;
	Swap(&arr[right],&arr[maxi]);

代碼實(shí)現(xiàn)

整體就是從0到n-1區(qū)間逐步往中間縮。當(dāng)left >= right時(shí)，表示沒(méi)有有效區(qū)間了。

//選擇排序
void SelectSort(int* arr, int n)
{
    int left = 0;
    int right = n - 1;
    while(left < right)
    {
        //每一次找出區(qū)間內(nèi)最大和最小的數(shù)
        int mini = left;
        int maxi = left;
        for(int i = left + 1; i <= right; i++)
        {
            if(arr[mini] > arr[i])
                mini = i;
            if(arr[maxi] < arr[i])
                maxi = i;
        }
        //避免重疊特殊判斷
        Swap(&arr[left],&arr[mini]);
        if(maxi == left)
            maxi = mini;
        Swap(&arr[right],&arr[maxi]);
        
        left++;
        right--;
    }
}

特性總結(jié)

一、選擇排序比較容易理解，但是效率實(shí)在太過(guò)低效。通常也不會(huì)用到它來(lái)進(jìn)行排序。
二、它的時(shí)間復(fù)雜度一如既往的穩(wěn)定在O(N^2)，空間復(fù)雜度為O(1)。
三、它是一個(gè)不穩(wěn)定的排序。舉一個(gè)樣例，如果出現(xiàn)最大值重復(fù)的情況，那么本該在前面的最大值會(huì)因?yàn)橄缺唤粨Q到最后，而導(dǎo)致相同值的順序錯(cuò)亂。

堆排序

點(diǎn)擊這里跳轉(zhuǎn)到堆排序介紹，由于前面已經(jīng)介紹過(guò)了這里就不多做贅述。根據(jù)上面介紹的直接選擇排序的介紹不難發(fā)現(xiàn)，其實(shí)堆排序就是對(duì)于直接選擇排序的一種優(yōu)化。不過(guò)這是一種憑借堆這種完全二叉樹(shù)的結(jié)構(gòu)來(lái)建堆提升選大根/小根的效率來(lái)進(jìn)行排序。

代碼實(shí)現(xiàn)

void AdjustDown(int* a, int n, int parent)
{
    int child = parent * 2 + 1;
    while (child < n)
    {
        // 選出左右孩子中大的那一個(gè)
        if (child + 1 < n && a[child + 1] > a[child])
        {
            ++child;
        }
		//判斷父子關(guān)系
        if (a[child] > a[parent])
        {
            Swap(&a[child], &a[parent]);
            //迭代
            parent = child;
            child = parent * 2 + 1;
        }
        else
        {
            break;
        }
    }
}


//堆排序
void HeapSort(int* arr, int n)
{
    //向下調(diào)整建堆
    for (int i = (n - 1 - 1) / 2; i >= 0; --i)
    {
        AdjustDown(arr, n, i);
    }
    //排序：大數(shù)往下沉，然后堆頂向下調(diào)整堆
    int end = n - 1;
    while (end > 0)
    {
        Swap(&arr[end], &arr[0]);
        AdjustDown(arr, end, 0);

        --end;
    }
}

特性總結(jié)

一、使用堆這個(gè)數(shù)據(jù)結(jié)構(gòu)進(jìn)行選樹(shù)，大大提升了效率。
二、堆排序的時(shí)間復(fù)雜度為O(N*LogN)，空間復(fù)雜度為O(1)。
三、堆排序是一種不穩(wěn)定的排序。

冒泡排序

思想

冒泡排序的思想是從第0個(gè)位置開(kāi)始依次和后面的數(shù)據(jù)進(jìn)行比較和交換。以升序?yàn)槔?dāng)前一個(gè)數(shù)比后一個(gè)數(shù)大的時(shí)候，交換兩個(gè)數(shù)位置，直到單趟結(jié)束，最終最大的數(shù)會(huì)出現(xiàn)在它應(yīng)該出現(xiàn)的位置。最壞的情況下需要走n-1趟冒泡排序。

單趟排序代碼實(shí)現(xiàn)

兩兩比較，直到找到單趟內(nèi)最大的值，并讓它到它合適的位置。

  for (int i = 1; i < n; i++)
        {
            if (arr[i - 1] > arr[i])
            {
                Swap(&arr[i - 1], &arr[i]);
            }
        }

代碼實(shí)現(xiàn)

//冒泡排序
void BubbleSort(int* arr, int n)
{
    for (int j = 0; j < n - 1; j++)
    {
        //若有序就跳出循環(huán)
        //優(yōu)化后，最好情況時(shí)間復(fù)雜度為O(N)
        int flag = 0;
        for (int i = 1; i < n-j; i++)
        {
            if (arr[i - 1] > arr[i])
            {
                Swap(&arr[i - 1], &arr[i]);
                flag = 1;
            }
        }
        if (flag == 0)
        {
            break;
        }
    }
}

特性總結(jié)

一、冒泡排序是一個(gè)就有教學(xué)意義的排序算法。
二、冒泡排序的時(shí)間復(fù)雜度為O(N^2)，空間復(fù)雜度為O(1)。
三、冒泡排序是一種穩(wěn)定的排序.文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-496751.html

到了這里，關(guān)于數(shù)據(jù)結(jié)構(gòu)——C語(yǔ)言實(shí)現(xiàn)常見(jiàn)排序(插入排序、希爾排序、選擇排序、堆排序、冒泡排序)的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！

本文來(lái)自互聯(lián)網(wǎng)用戶(hù)投稿，該文觀點(diǎn)僅代表作者本人，不代表本站立場(chǎng)。本站僅提供信息存儲(chǔ)空間服務(wù)，不擁有所有權(quán)，不承擔(dān)相關(guān)法律責(zé)任。如若轉(zhuǎn)載，請(qǐng)注明出處： 如若內(nèi)容造成侵權(quán)/違法違規(guī)/事實(shí)不符，請(qǐng)點(diǎn)擊違法舉報(bào)進(jìn)行投訴反饋，一經(jīng)查實(shí)，立即刪除！

領(lǐng)支付寶紅包贊助服務(wù)器費(fèi)用

相關(guān)文章

覺(jué)得文章有用就打賞一下文章作者

支付寶掃一掃打賞

博客贊助

微信掃一掃打賞

請(qǐng)作者喝杯咖啡吧~博客贊助

支付寶掃一掃領(lǐng)取紅包，優(yōu)惠每天領(lǐng)

二維碼1

領(lǐng)取紅包

二維碼2

領(lǐng)紅包