一区二区三区在线-一区二区三区亚洲视频-一区二区三区亚洲-一区二区三区午夜-一区二区三区四区在线视频-一区二区三区四区在线免费观看

服務(wù)器之家:專(zhuān)注于服務(wù)器技術(shù)及軟件下載分享
分類(lèi)導(dǎo)航

PHP教程|ASP.NET教程|Java教程|ASP教程|編程技術(shù)|正則表達(dá)式|C/C++|IOS|C#|Swift|Android|VB|R語(yǔ)言|JavaScript|易語(yǔ)言|vb.net|

服務(wù)器之家 - 編程語(yǔ)言 - C/C++ - C語(yǔ)言 八大排序算法的過(guò)程圖解及實(shí)現(xiàn)代碼

C語(yǔ)言 八大排序算法的過(guò)程圖解及實(shí)現(xiàn)代碼

2022-03-08 15:29夢(mèng)鄉(xiāng)回雪 C/C++

排序是數(shù)據(jù)結(jié)構(gòu)中很重要的一章,本文主要為大家介紹了常用的八個(gè)排序算法(插入,希爾,選擇,堆排,冒泡,快排,歸并,計(jì)數(shù))的過(guò)程及代碼實(shí)現(xiàn),需要的朋友可以參考一下

前言

排序是數(shù)據(jù)結(jié)構(gòu)中很重要的一章,先介紹幾個(gè)基本概念。

  • 排序穩(wěn)定性:多個(gè)具有相同的關(guān)鍵字的記錄,若經(jīng)過(guò)排序,這些記錄的相對(duì)次
  • 序保持不變,即在原序列中,r[i]=r[j],且r[i]在r[j]之前,而在排序后的序列中,r[i]仍在r[j]之前,則稱(chēng)這種排序算法是穩(wěn)定的;否則稱(chēng)為不穩(wěn)定的。
  • 內(nèi)部排序:數(shù)據(jù)元素全部放在內(nèi)存中的排序。
  • 外部排序:數(shù)據(jù)元素太多不能同時(shí)放在內(nèi)存中,根據(jù)排序過(guò)程的要求不能在內(nèi)外存之間移動(dòng)數(shù)據(jù)的排序。

一、插入排序

時(shí)間復(fù)雜度

最壞:-----------o(n^2)

最好:-----------o(n)

平均:-----------o(n^2)

空間復(fù)雜度

o(1)

穩(wěn)定性:穩(wěn)定

-『 插入排序 』:顧名思義就是把每一個(gè)數(shù)插入到有序數(shù)組中對(duì)應(yīng)的位置。

就相當(dāng)于你玩撲克牌的過(guò)程,抓來(lái)一張牌,就放在對(duì)應(yī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)位置上的元素順序后移

C語(yǔ)言 八大排序算法的過(guò)程圖解及實(shí)現(xiàn)代碼

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

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
void insertsort(int* a, int n)
{
    for (int i = 0; i < n - 1; i++)
    {
        int x = a[end+1];//x為待排序的值
        int end = i;//從end開(kāi)始往前和x依次比較
 
        while (end >= 0)
        {
            if (a[end] > x)//只要當(dāng)前的值大于x繼續(xù)往前找
            {
                a[end+1] = a[end];
                end--;
            }
            else
            {
                break;//跳出循環(huán)說(shuō)明a[end] <= x
            }
        }
        a[end + 1] = x;//跳出循環(huán)說(shuō)明a[end] <= x,需要把x插入到end前邊
    }
}

那么我們可以看到,越是接近有序的數(shù)組,插入排序的效率越高(有序時(shí)對(duì)于任何一個(gè)數(shù)只需要和前邊的數(shù)比較一次)。

二、希爾排序

時(shí)間復(fù)雜度

o(n^(1.3—2))

空間復(fù)雜度

o(1)

穩(wěn)定性:穩(wěn)定

『 希爾排序 』(shell's sort)是插入排序的一種又稱(chēng)“縮小增量排序”(diminishing increment sort),是直接插入排序算法的一種更高效的改進(jìn)版本。希爾排序是非穩(wěn)定排序算法。該方法因 d.l.shell 于 1959 年提出而得名。

該方法實(shí)質(zhì)上是一種『 分組插入 』方法,因?yàn)椴迦肱判驅(qū)τ诮咏行虻臄?shù)組排序效率非常高,那么希爾提出:

算法先將要排序的一組數(shù)按某個(gè)增量d分成若干組,每組中記錄的下標(biāo)相差d.對(duì)每組中全部元素進(jìn)行排序,然后再用一個(gè)較小的增量對(duì)它進(jìn)行分組,在每組中再進(jìn)行排序。當(dāng)增量減到1時(shí),整個(gè)要排序的數(shù)被分成一組,排序完成。

一般的初次取序列的一半為增量,以后每次減半,直到增量為1。

并且插入排序可以看成分組是1的希爾排序。動(dòng)圖如下:

C語(yǔ)言 八大排序算法的過(guò)程圖解及實(shí)現(xiàn)代碼

因?yàn)椴迦肱判蚩梢钥醋鰃ap==1的希爾排序,因此只需要改變插入排序中for循環(huán)的增量控制排序即可。

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

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
void shellsort(int* a, int n)
{
    //按gap分組進(jìn)行預(yù)排序
    int gap = n;
    while (gap>1)
    {
        //gap = gap / 2;
        gap = gap / 3 + 1;//這里分組選每次折半或者/3都可以
 
        for (int j = 0; j < gap; j++)//gap個(gè)組
            for (int i = j; i < n - gap; i+=gap)//每個(gè)組從j開(kāi)始每個(gè)增量gap
            {
                int end = i;
                int x = a[end + gap];
                while (end >= 0)
                {
                    if (a[end] > x)
                    {
                        a[end + gap] = a[end];
                        end -= gap;
                    }
                    else
                    {
                        break;
                    }
                }
                a[end + gap] = x;
            }
    }
}

關(guān)于希爾排序時(shí)間復(fù)雜度證明比較復(fù)雜,取決于gap怎么取,如果按照knuth提出的/3,來(lái)取是o(n^(1.25)- 1.6*o(n^1.25).

希爾排序的特性總結(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ù)中給出的希爾排序的時(shí)間復(fù)雜度都不固定

三、選擇排序

時(shí)間復(fù)雜度

最壞:-----------o(n^2)

最好:-----------o(n^2)

平均:-----------o(n^2)

空間復(fù)雜度

o(1)

穩(wěn)定性:不穩(wěn)定

『 基本思想 』:

每一次從待排序的數(shù)據(jù)元素中選出最?。ɑ蜃畲螅┑囊粋€(gè)元素,存放在序列的起始(末尾)位置,直到全部待排序的數(shù)據(jù)元素排完 。如圖:

C語(yǔ)言 八大排序算法的過(guò)程圖解及實(shí)現(xiàn)代碼

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

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void selectsort(int* a, int n)
{
    int begin = 0;
    int end = n - 1;
    int mini = begin;//記錄最小值下標(biāo)
    while (begin<end)
    {
        for (int i = begin; i < end; i++)
        {
            if (a[i] < a[mini])
            {
                mini = i;//更新最小值下標(biāo)
            }
        }
        swap(&a[mini],&a[begin]);//把最小值放到左邊
        ++begin;//左邊對(duì)應(yīng)起始位置++
    }
}

直接選擇排序思考非常好理解,但是效率不是很好。實(shí)際中很少使用。

四、堆排序

時(shí)間復(fù)雜度

最壞:-----------o(n * logn)

最壞:-----------o(n * logn)

平均:-----------o(n*logn)

空間復(fù)雜度

o(1)

堆排序(heapsort)是指利用堆積樹(shù)(堆)這種數(shù)據(jù)結(jié)構(gòu)所設(shè)計(jì)的一種排序算法,它是選擇排序的一種。它是通過(guò)堆來(lái)進(jìn)行選擇數(shù)據(jù)。需要注意的是排升序要建大堆,排降序建小堆。

具體可見(jiàn)另一篇文章堆排序和topk問(wèn)題

動(dòng)圖:

C語(yǔ)言 八大排序算法的過(guò)程圖解及實(shí)現(xiàn)代碼

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

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
void swap(int* px,int* py)
{
    int t = (*px);
    (*px) = (*py);
     (*py)= t ;
}
void adjustdown(int* a, int n, int parent)
{
    int child = parent * 2 + 1;
    while (child < n)
    {
        if (child + 1 < n && a[child + 1] > a[child])
        {
            child++;
        }
        if (a[child] > a[parent])
        {
            swap(&a[child], &a[parent]);
            parent = child;
            child = parent * 2 + 1;
        }
        else
        {
            break;
        }
    }
 
}
void heapsort(int* a, int n)
{
    for (int i = (n - 1 - 1) / 2; i >= 0; i--)
    {
        adjustdown(a, n, i);
    }
    for (int i = n - 1; i > 0; i--)
    {
        swap(&a[0], &a[i]);
        adjustdown(a, i, 0);
    }
}

五、冒泡排序

時(shí)間復(fù)雜度

最壞:-----------o(n^2)

最好:-----------o(n)

平均:-----------o(n^2)

空間復(fù)雜度

o(1)

『 冒泡排序 』是大家最熟悉的也是最容易理解的排序,如下圖:

C語(yǔ)言 八大排序算法的過(guò)程圖解及實(shí)現(xiàn)代碼

『 冒泡排序基本思想 』就是每一次將相鄰的數(shù)據(jù)進(jìn)行『 兩兩比較 』,選出最大的依次比較送到右邊,那么最右邊就是最大值,而左邊留下的自然就是小的(排升序)

-『 冒泡排序 』需要兩層循環(huán)

『 內(nèi)層循環(huán) 』表示一次冒泡,也就是兩兩比較先選出最大的放到最右邊,同時(shí)注意每一次冒泡選出最大元素,那么兩兩比較次數(shù)-1(下一次不用比較選好的最右邊)

『 外層循環(huán) 』控制的是冒泡的次數(shù)(假設(shè)數(shù)組n 個(gè)元素)也就是n-1次冒泡選出n-1個(gè)最大的元素

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

初版代碼如下:

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//初版:
void swap(int* px, int* py)
{
    int t = (*px);
    *px = (*py);
    (*py) = t;
}
void bubblesort(int* a, int n)
{
    for (int i = 0; i < n-1; i++)//外層循環(huán)
    {
        for (int j = 0; j < n-1-i; j++)
        {
            if(a[j]>a[j+1])
                swap(&a[j],& a[j + 1]);//交換
            flag = 1;
        }  
    }
}

時(shí)間復(fù)雜度分析:每一次比較次數(shù)是n-1,n-2,n-3***1.因此是n(n-1)/2

但是這種寫(xiě)法還是有缺陷,時(shí)間復(fù)雜度永遠(yuǎn)是o(n^2) , 對(duì)于一個(gè)已經(jīng)排好序的數(shù)組來(lái)說(shuō),還是需要n^2的復(fù)雜度,但對(duì)于有序的數(shù)組,每一次冒泡都不會(huì)進(jìn)行交換因?yàn)橛行颍虼巳绻灰魏我淮蚊芭葜袥](méi)有數(shù)據(jù)交換就證明數(shù)組有序了。時(shí)間復(fù)雜度最好也可以達(dá)到0(n)。

代碼優(yōu)化如下:

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
//優(yōu)化:
void bubblesort(int* a, int n)
{
    for (int i = 0; i < n-1; i++)
    {
        int flag = 0;
        for (int j = 0; j < n-1-i; j++)
        {
            if(a[j]>a[j+1])
            swap(&a[j],& a[j + 1]);
            flag = 1;
        }
        if (flag == 0)
            break;
 
    }
}

六、快排排序

時(shí)間復(fù)雜度

最壞:-----------o(n^2)

最好:-----------o(logn)

平均:-----------o(logn)

空間復(fù)雜度

o(logn)

『 快速排序 』是hoare于1962年提出的一種二叉樹(shù)結(jié)構(gòu)的交換排序方法,其『 基本思想 』為:任取待排序元素序列中的某元素作為『 基準(zhǔn)值 』,按照該排序碼將待排序集合分割成兩子序列,左子序列中所有元素均小于基準(zhǔn)值,右子序列中所有元素均大于基準(zhǔn)值,然后最左右子序列重復(fù)該過(guò)程,直到所有元素都排列在相應(yīng)位置上為止。如圖:

C語(yǔ)言 八大排序算法的過(guò)程圖解及實(shí)現(xiàn)代碼

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

遞歸寫(xiě)法:

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// 假設(shè)按照升序?qū)數(shù)組中[left, right)區(qū)間中的元素進(jìn)行排序
void quicksort(int* a, int left, int right) {
     if(right >= left )
        return;//遞歸截止條件
     
     // 按照基準(zhǔn)值對(duì)a數(shù)組的 [left, right]區(qū)間中的元素進(jìn)行劃分
     int keyi= partion(a, left, right);
     
     // 劃分成功后以keyi為邊界形成了左右兩部分 [left, keyi-1] 和 [keyi+1, right]
     // 遞歸排[left, keyi-1]
     quicksort(a, left, keyi-1);
     
     // 遞歸排[keyi+1, right]
     quicksort(a, keyi+1, right);
}

遞歸框架寫(xiě)完了接下來(lái)就差partion函數(shù)的實(shí)現(xiàn)也就是快排的靈魂,去每一次找基準(zhǔn)值。那么一共有三種寫(xiě)法如下:

hoare版本

C語(yǔ)言 八大排序算法的過(guò)程圖解及實(shí)現(xiàn)代碼

1.首先就是要找基準(zhǔn)值,這里你可以選最左邊或最右邊的值(圖中是6)

2.兩個(gè)指針指向頭(這里選左為基準(zhǔn)值,頭指針指向第二個(gè))和尾,基準(zhǔn)值選左,則右指針先走,反之左指針先走。

3.左指針找到比基準(zhǔn)值大的停下,右指針找比基準(zhǔn)值小的停下,交換左右指針指向值

4.重復(fù)2.3動(dòng)作,直到左右指針相遇,交換左指針值和基準(zhǔn)值

C語(yǔ)言 八大排序算法的過(guò)程圖解及實(shí)現(xiàn)代碼

左值為基準(zhǔn),右指針先走找比6小的:

C語(yǔ)言 八大排序算法的過(guò)程圖解及實(shí)現(xiàn)代碼

左值為基準(zhǔn),右指針先走找比6小的:

C語(yǔ)言 八大排序算法的過(guò)程圖解及實(shí)現(xiàn)代碼

交換:

C語(yǔ)言 八大排序算法的過(guò)程圖解及實(shí)現(xiàn)代碼

C語(yǔ)言 八大排序算法的過(guò)程圖解及實(shí)現(xiàn)代碼

最終效果:相遇交換左指針和基準(zhǔn)值,保證了6的左邊都比6小,右邊比6大。

C語(yǔ)言 八大排序算法的過(guò)程圖解及實(shí)現(xiàn)代碼

并且除此之外,由于我們看到這種算法類(lèi)似于二叉樹(shù)的思想排好中間再排左右子樹(shù),因此我要保證選取的隨機(jī)值盡量位與中位數(shù)。所以我們采取三數(shù)取中的方法。(選取最左值最右最中間的數(shù)的中位數(shù))效率是可以提升5%到10%的。

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
//三數(shù)取中
int getmidindex(int* a, int left, int right)
{
    //int mid = (left + right) / 2;
    //int mid = left + (right - left) / 2;
    int mid = left + ((right - left)>>1);
    if (a[left] < a[mid])
    {
        if (a[mid] < a[right])
        {
            return mid;
 
        }
        else if (a[left] > a[right])
        {
            return left;
        }
        else
        {
            return right;
        }
    }
    else//a[left] > a[mid]
    {
        if (a[mid] > a[right])
        {
            return mid;
 
        }
        else if (a[left] < a[right])
        {
            return left;
        }
        else
        {
            return right;
        }
    }
 
}
int partion(int* a, int left,int right)
{
    int mini = getmidindex(a, left, right);
    swap(&a[mini], &a[left]);
    
    int keyi = left;
    while (left < right)
    {
        while (left < right && a[right] >= a[keyi])
        {
            right--;
        }
        while (left < right && a[left] <= a[keyi])
        {
            left++;
        }
        swap(&a[left], &a[right]);
    }swap(&a[left], &a[keyi]);
    return left;
}

挖坑法

挖坑法就是對(duì)hoare版本的一種變形,過(guò)程如下:

初始如下:先保存基準(zhǔn)值,基準(zhǔn)值形成一個(gè)坑位!

C語(yǔ)言 八大排序算法的過(guò)程圖解及實(shí)現(xiàn)代碼

左為基準(zhǔn),右指針先走,找到小的送到坑位,那么此刻右指針形成了新的坑位

C語(yǔ)言 八大排序算法的過(guò)程圖解及實(shí)現(xiàn)代碼

左指針出動(dòng),找到大的繼續(xù)送到坑位,左指針形成了新的坑位

C語(yǔ)言 八大排序算法的過(guò)程圖解及實(shí)現(xiàn)代碼

C語(yǔ)言 八大排序算法的過(guò)程圖解及實(shí)現(xiàn)代碼

C語(yǔ)言 八大排序算法的過(guò)程圖解及實(shí)現(xiàn)代碼

C語(yǔ)言 八大排序算法的過(guò)程圖解及實(shí)現(xiàn)代碼

指針相遇,把6寫(xiě)入。也保證左邊比6小,右邊比6大。代碼如下:

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
//挖坑法
int partion2(int* a, int left, int right)
{
    int mini = getmidindex(a, left, right);
    swap(&a[mini], &a[left]);
 
    int key = a[left];
    int pivot = left;
    while (left < right)
    {
        //右邊先找小
        while (left< right && a[right] >= key)
        {
            --right;
        }
        a[pivot] = a[right];
        pivot = right;
        while (left < right && a[left] <= key)
        {
            ++left;
        }
        a[pivot] = a[left];
        pivot = left;
    }
    a[pivot] = key;
    return pivot;
}

前后指針版本

顧名思義,使用兩個(gè)指針,這里選取左為基準(zhǔn)值為例,兩個(gè)指針從左開(kāi)始出發(fā)一個(gè)cur,一個(gè)prev。

要求:

cur指針先走,一旦找到比基準(zhǔn)值小的就停下,++prev,并交換。

cur指針一直到頭為止,最后交換prev指向值和基準(zhǔn)值

C語(yǔ)言 八大排序算法的過(guò)程圖解及實(shí)現(xiàn)代碼

C語(yǔ)言 八大排序算法的過(guò)程圖解及實(shí)現(xiàn)代碼

C語(yǔ)言 八大排序算法的過(guò)程圖解及實(shí)現(xiàn)代碼

1和2都比6小cur走一步停一步,prev++并交換,指向相等。

cur越過(guò)7和9去找小的3,此時(shí)停下,prev++指向7交換。(我們注意到prev和cur不等時(shí)prev永遠(yuǎn)是去找大的,cur是找小的,因此交換就做到把cur指向的小的往前扔,大的往后仍,)

C語(yǔ)言 八大排序算法的過(guò)程圖解及實(shí)現(xiàn)代碼

C語(yǔ)言 八大排序算法的過(guò)程圖解及實(shí)現(xiàn)代碼

C語(yǔ)言 八大排序算法的過(guò)程圖解及實(shí)現(xiàn)代碼

C語(yǔ)言 八大排序算法的過(guò)程圖解及實(shí)現(xiàn)代碼

整個(gè)過(guò)程如上,代碼:

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//前后指針?lè)?/code>
int partion3(int* a, int left, int right)
{
    int mini = getmidindex(a, left, right);
    swap(&a[mini], &a[left]);
    int prev = left, cur = left+1;
    int keyi = left;
    while (cur<=right)
    {
        if (a[cur] < a[keyi] && ++prev !=cur)
        {
            swap(&a[prev], &a[cur]);
        }
        cur++;
    }
    swap(&a[prev], &a[keyi]);
    return prev;
}

小結(jié)

遞歸版本三種方法如上,但是遞歸畢竟有缺陷,就是需要不斷開(kāi)辟棧幀,當(dāng)數(shù)據(jù)量超過(guò)10w以上時(shí)就會(huì)有棧溢出的風(fēng)險(xiǎn)。

并且遞歸類(lèi)似二叉樹(shù)的結(jié)構(gòu)越往下遞歸調(diào)用越多,棧幀翻倍開(kāi)辟,因此我們還可以去優(yōu)化一下,就是當(dāng)遞歸到左右區(qū)間比較小時(shí),我們?nèi)タ刂剖O碌呐判蛴脛e的排序來(lái)代替它。

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//優(yōu)化:
void quicksort(int* a, int left, int right)
{
    if (left >= right)
        return;
    if (right - left + 1 < 10)
    {
        //小區(qū)間優(yōu)化
        insertsort(a + left , right - left + 1);
    }
    else
    {
        int keyi = partion3(a, left, right);
        quicksort(a, left, keyi - 1);
        quicksort(a, keyi + 1, right);
    }
    
}

非遞歸:

非遞歸版本就是改變了快排的框架,用一個(gè)棧和循環(huán)來(lái)代替遞歸實(shí)現(xiàn)。依次將左右下標(biāo)入棧出棧(出棧之前排序)來(lái)模擬遞歸。

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
void quicksortnonr(int* a, int left, int right)
{
    stack st;//定義一個(gè)棧
    stackinit(&st);//初始化
    stackpush(&st, left);//左下標(biāo)入棧
    stackpush(&st, right);//右下標(biāo)入棧
    while (stackempty(&st)!=0)
    {
        int end = stacktop(&st);//獲取棧頂元素即后入棧的右下標(biāo)
        stackpop(&st);//出棧
 
        int begin = stacktop(&st);//獲取棧頂元素即先入棧的左下標(biāo)
        stackpop(&st);//出棧
 
        int keyi = partion3(a, begin, end);
        if (keyi + 1 < end)//相當(dāng)于遞歸左半部分
        {
            stackpush(&st, keyi + 1);
            stackpush(&st, right);
        }
        if (keyi - 1 > begin)//相當(dāng)于遞歸右半部分
        {
            stackpush(&st, keyi - 1);
            stackpush(&st, begin);
        }
 
    }
}

七、歸并排序

時(shí)間復(fù)雜度

最壞:-----------o(nlogn)

最好:-----------o(nlogn)

平均:-----------o(nlogn)

空間復(fù)雜度

o(n)

穩(wěn)定性:穩(wěn)定

基本思想:

歸并排序(merge-sort)是建立在歸并操作上的一種有效的排序算法,該算法是采用分治法(divide andconquer)的一個(gè)非常典型的應(yīng)用。將已有序的子序列合并,得到完全有序的序列;即先使每個(gè)子序列有序,再使子序列段間有序。若將兩個(gè)有序表合并成一個(gè)有序表,稱(chēng)為二路歸并。 動(dòng)圖演示:

C語(yǔ)言 八大排序算法的過(guò)程圖解及實(shí)現(xiàn)代碼

歸并的思想就是把先假設(shè)數(shù)組分成兩個(gè)有序,對(duì)其進(jìn)行篩選排序,如上圖:

但是問(wèn)題來(lái)了我們?cè)趺幢WC數(shù)組是有序的?因此就要求我們從小區(qū)間開(kāi)始對(duì)數(shù)組歸并排序,對(duì)于上圖中的數(shù)據(jù),先對(duì)開(kāi)始3和3歸并,小的先進(jìn)入到tmp數(shù)組,因此前兩個(gè)就是有序,再對(duì),5和6歸并,5,6有序后,在歸并3,3,5,6……以此類(lèi)推

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

遞歸寫(xiě)法

框架:

?
1
2
3
4
5
6
7
8
9
10
11
void mergesort(int* a,int n)
{
    int* tmp = (int*)malloc(sizeof(int) * n);//開(kāi)辟n個(gè)大小數(shù)組
    if (tmp == null)
    {
        exit(-1);
    }
    _mergesort(a, 0, n - 1, tmp);//進(jìn)行歸并操作
    free(tmp);
    tmp = null;
}

歸并排序:

運(yùn)用遞歸先不斷縮小偏序區(qū)間,在遞歸層層退出時(shí)一遍退出,一邊對(duì)不斷回大的區(qū)間歸并排序:

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
void _mergesort(int* a, int left, int right,int* tmp)
{
    if (left >= right)
    {
        return;//遞歸截止條件left >= right區(qū)間中數(shù)的個(gè)數(shù)<=0個(gè)
    }
    int mid = left + (right - left) / 2;//取中
 
    _mergesort(a, left, mid, tmp);//對(duì)左區(qū)間遞歸
    _mergesort(a, mid+1, right, tmp);//對(duì)右區(qū)間遞歸
 
    int begin1 = left, end1 = mid;//左區(qū)間
    int begin2 = mid+1, end2 = right;//右區(qū)間
    int i = left;
    while (begin1 <= end1 && begin2 <= end2)
    {
        if (a[begin1] < a[begin2])
        {
            tmp[i++] = a[begin1++];
        }
        else
        {
            tmp[i++] = a[begin2++];
        }
    }
    while (begin1 <= end1 )
    {
        tmp[i++] = a[begin1++];
    }
    while (begin2 <= end2)
    {
        tmp[i++] = a[begin2++];
    }
    for (size_t i = left; i <= right; i++)
    {
        a[i] = tmp[i];//把排好序[left,right]的tmp賦值給原數(shù)組
    }
}

非遞歸

非遞歸的不同就是需要手動(dòng)控制區(qū)間大小,也就是不斷2倍擴(kuò)大區(qū)間歸并。

但是還需要注意就是當(dāng)下標(biāo)是奇數(shù),無(wú)法分成整數(shù)個(gè)組的時(shí)候,需要考慮剩余的數(shù),以及是否越界的問(wèn)題

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
void mergesortnonr(int* a, int n)
{
    int* tmp = (int*)malloc(sizeof(int) * n);
    if (tmp == null)
    {
        exit(-1);
    }
    int gap = 1;
    while (gap < n)
    {
        for (int i = 0; i < n; i += 2 * gap)
        {
            //[i][i+gap-1] [i+gap][i+2*gap-1]
            int begin1 = i, end1 = i + gap-1;
            int begin2 = i + gap, end2 = i + 2 * gap - 1;
            int index = i;
 
 
            if (end1 >= n || begin2 >= n)
            {
                break;
            }
            if (end2 >= n)
            {
                end2 = n - 1;
            }
 
 
 
            while (begin1<=end1 && begin2<=end2)
            {
                if (a[begin1] <= a[begin2])
                {
                    tmp[index++] = a[begin1++];
                }
                else
                {
                    tmp[index++] = a[begin2++];
                }
            }
            while (begin1 <= end1)
            {
                tmp[index++] = a[begin1++];
            }
            while (begin2 <= end2)
            {
                tmp[index++] = a[begin2++];
            }
            //控制越界問(wèn)題三種情況
            if (end1 >= n)
            {
                end1 = n - 1;
            }
            if (end1 >= n)
            {
                end1 = n - 1;
            }
            if (end1 >= n)
            {
                end1 = n - 1;
            }
 
            for (int j = i; j <= end2; j++)
            {
                a[j] = tmp[j];
            }
        }
 
        
        gap *= 2;
    }
    
    free(tmp);
    tmp = null;
 
}

八、計(jì)數(shù)排序

時(shí)間復(fù)雜度

最壞:-----------o(max(n,范圍))

最好:-----------o(max(n,范圍))

平均:-----------o(max(n,范圍))

空間復(fù)雜度

o(范圍)

穩(wěn)定性:不穩(wěn)定

思想:計(jì)數(shù)排序又稱(chēng)為鴿巢原理,是對(duì)哈希直接定址法的變形應(yīng)用。 操作步驟:

  1. 統(tǒng)計(jì)相同元素出現(xiàn)次數(shù)
  2. 根據(jù)統(tǒng)計(jì)的結(jié)果將序列回收到原來(lái)的序列中

動(dòng)圖如下:

C語(yǔ)言 八大排序算法的過(guò)程圖解及實(shí)現(xiàn)代碼

類(lèi)似桶排序的思想,如上圖,先開(kāi)辟數(shù)組統(tǒng)計(jì)數(shù)組中某一個(gè)數(shù)出現(xiàn)的次數(shù),比如2出現(xiàn)1次,3出現(xiàn)兩次,那么我們直接按順序讀入開(kāi)辟的數(shù)組,在原數(shù)組寫(xiě)1一個(gè)2,兩個(gè)3以此類(lèi)推……

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
void countsort(int* a, int n)
{
    int max=a[0], min= a[0];
    for (int i = 0; i < n; i++)
    {
        if (a[i] > max)
        {
            max = a[i];
        }
        if (a[i] < min)
        {
            min = a[i];
        }
    }
    int range = max - min + 1;
    int* count = (int*)malloc(sizeof(int) * range);
    memset(count, 0, sizeof(int)*range);
    for (int i = 0; i < n; i++)
    {
        count[a[i] - min]++;
    }
    int j = 0;
    for (int i = 0; i < range; i++)
    {
        while (count[i]--)
        {
            a[j++] = i + min;
        }
    }
}

計(jì)數(shù)排序的特性總結(jié):

計(jì)數(shù)排序在數(shù)據(jù)范圍集中時(shí),效率很高,但是適用范圍及場(chǎng)景有限。

九、各種排序總結(jié)比較

1. 復(fù)雜度總結(jié)

C語(yǔ)言 八大排序算法的過(guò)程圖解及實(shí)現(xiàn)代碼

2. 性質(zhì)分類(lèi)

C語(yǔ)言 八大排序算法的過(guò)程圖解及實(shí)現(xiàn)代碼

 以上就是c語(yǔ)言 八大排序算法的過(guò)程圖解及實(shí)現(xiàn)代碼的詳細(xì)內(nèi)容,更多關(guān)于c語(yǔ)言八大排序算法的資料請(qǐng)關(guān)注服務(wù)器之家其它相關(guān)文章!

原文鏈接:https://blog.csdn.net/weixin_51484780/article/details/121628023

延伸 · 閱讀

精彩推薦
主站蜘蛛池模板: 亚洲精品福利一区二区在线观看 | 午夜久久免费视频 | 成人影院视频 | 免费一级欧美片在线观看 | 国产乱码一卡二卡3卡四卡 国产乱插 | 精品一区二区三区 不卡高清 | 91久久精品青青草原伊人 | 牛牛色婷婷在线视频播放 | 免费看男人狂躁女人 | 天天舔天天操天天干 | 天天曰| 91人成网站色www | 欧美成人免费观看bbb | 亚洲天堂网站在线 | 精品久久久久亚洲 | 国产亚洲综合精品一区二区三区 | 亚洲精品久久中文字幕 | 性派对videos18party | 日本大巴车强thepro | 亚洲乱码一区二区三区国产精品 | 亚洲AV无码国产精品色午夜情 | 单亲乱l仑在线观看免费观看 | 被肉日常np高h | 任你操视频在线观看 | 特黄特a级特别特级特毛片 特黄a级三级三级野战 | 免费在线观看中文字幕 | 丁香久久婷婷 | 四虎影视4hutv最新地址在线 | 97国产蝌蚪视频在线观看 | 五月天淫 | 操姓| 欧美成人禁片在线观看俄罗斯 | 好湿好紧太硬了我太爽了网站 | 99热网址 | 欧美国产在线视频 | 欧美在线视频 一区二区 | 九九99热| 国产一区在线免费观看 | 免费成人在线观看视频 | 成年人在线观看免费视频 | 隔壁老王国产精品福利 |