c語(yǔ)言遞歸和非遞歸排序怎么實(shí)現(xiàn)

本篇內(nèi)容主要講解“c語(yǔ)言遞歸和非遞歸排序怎么實(shí)現(xiàn)”，感興趣的朋友不妨來看看。本文介紹的方法操作簡(jiǎn)單快捷，實(shí)用性強(qiáng)。下面就讓小編來帶大家學(xué)習(xí)“c語(yǔ)言遞歸和非遞歸排序怎么實(shí)現(xiàn)”吧!

遞歸代碼流程

歸并就是把兩個(gè)或多個(gè)序列合并，這里只介紹二路歸并，就是不斷的把序列分為2組，直到每個(gè)組有一個(gè)元素為止，然后再比較合并，直到合為1個(gè)序列，完成。

非遞歸代碼流程

與遞歸不斷分解數(shù)組相反，非遞歸直接從長(zhǎng)度為1的子序列開始合并，直到全并為1個(gè)整個(gè)序列，復(fù)用了merge函數(shù)

兩者比較

代碼用非遞歸的方式效率更高一些：

空間復(fù)雜度：從O(log2n)變?yōu)?個(gè)臨時(shí)數(shù)組O(n)

時(shí)間復(fù)雜度：少了遞歸的時(shí)間

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

O(nlogn)

代碼（遞歸）

#include <stdio.h>
#include <stdbool.h>

#define MAXSIZE 9

typedef struct {
    int r[MAXSIZE+1]; // first index used as tmp, not real data
    int len;
}SqList;

void swap(SqList *L, int i, int j) {
    int tmp = L->r[i];
    L->r[i] = L->r[j];
    L->r[j] = tmp;
}

void merge(int sr[], int tr[], int s, int m, int t) {
    // 本函數(shù)的任務(wù)就是比對(duì)sr中兩個(gè)分組(s..m, m+1..t)的元素大小并歸并到tr
    int j,k,l;

    j = m + 1; // 第2分組的起始位置
    k = s; // k用于tr數(shù)組中的游標(biāo)與sr中的起始位置對(duì)應(yīng)起來
    while (s<=m && j<=t) {
        if (sr[s] < sr[j]) {
            tr[k++] = sr[s++];
        }
        else {
            tr[k++] = sr[j++];
        }
    }

    // 只要是合并，就肯定至少是2個(gè)序列合并，肯定會(huì)在比對(duì)后剩下1個(gè)未消耗完元素的序列分組
    while (s<=m) {
        tr[k++] = sr[s++];
    }

    while (j<=t) {
        tr[k++] = sr[j++];
    }
}

void msort(int sr[], int tr[], int s, int t) {
    /*
     * 把sr進(jìn)行歸并排序并有序保存到(歸并到)tr中
     */
    int m;
    int tmpr[MAXSIZE+1]; // 每層遞歸的臨時(shí)數(shù)組，存放本次被調(diào)用時(shí)s到t歸并后的下標(biāo)值(位置與首次傳入的L->r相同)

    if (s == t) {
        tr[s] = sr[s]; // 歸并的思想，1個(gè)元素的分組為有序
    }
    else { // 不是1個(gè)元素的分組，繼續(xù)分組
        m = (s+t)/2;
        msort(sr, tmpr, s, m);
        msort(sr, tmpr, m+1, t);
        // 合并tmpr到tr完成本層的排序任務(wù)
        merge(tmpr, tr, s, m, t);
    }
}

void merge_sort(SqList *L) {
    msort(L->r, L->r, 1, L->len); // 因?yàn)樵趍sort中第1個(gè)參數(shù)sr數(shù)組只是讀取，所以這里這樣傳遞沒有問題
}


int main(void) {
    SqList list = {
        {999,50,10,90,30,70,40,80,60,20},
        MAXSIZE
    };

    merge_sort(&list);
    printf("after merge_sort:\n");
    for (int i=0; i<=MAXSIZE; i++) {
        printf("index: %d, value: %d\n",i,list.r[i]);
    }
    return 0;
}

output

?  c gcc sort_merge.c&& ./a.out
after merge_sort:
index: 0, value: 999
index: 1, value: 10
index: 2, value: 20
index: 3, value: 30
index: 4, value: 40
index: 5, value: 50
index: 6, value: 60
index: 7, value: 70
index: 8, value: 80
index: 9, value: 90
 

代碼（非遞歸）

#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>

#define MAXSIZE 9

typedef struct {
    int r[MAXSIZE+1]; // first index used as tmp, not real data
    int len;
}SqList;

void merge(int sr[], int tr[], int s, int m, int t) {
    // 本函數(shù)的任務(wù)就是比對(duì)sr中兩個(gè)分組(s..m, m+1..t)的元素大小并歸并到tr
    int j,k,l;

    j = m + 1; // 第2分組的起始位置
    k = s; // k用于tr數(shù)組中的游標(biāo)與sr中的起始位置對(duì)應(yīng)起來
    while (s<=m && j<=t) {
        if (sr[s] < sr[j]) {
            tr[k++] = sr[s++];
        }
        else {
            tr[k++] = sr[j++];
        }
    }

    // 只要是合并，就肯定至少是2個(gè)序列合并，肯定會(huì)在比對(duì)后剩下1個(gè)未消耗完元素的序列分組
    while (s<=m) {
        tr[k++] = sr[s++];
    }

    while (j<=t) {
        tr[k++] = sr[j++];
    }
}


void merge_pass(int sr[], int tr[], int k, int len) {
    int i=1; // 合并時(shí)的游標(biāo)
    while (i < len-2*k+1) { // 也就是每次循環(huán)后，當(dāng)前所剩余的是否還夠2個(gè)完整子序列
        merge(sr, tr, i, i+k-1, i+2*k-1); //合并本輪掃描到的2個(gè)子序列
        i+=2*k; // 賦值后的i為下一輪2個(gè)子序列的起始位置
    }

    // 下面是掃尾工作，**可能會(huì)**出現(xiàn)2種情況，a. 剩余1～2個(gè)子序列之間的情況, b. 剩余<=1個(gè)子序列的情況
    if (i < len-k+1) {
        merge(sr, tr, i, i+k-1, len);
    }
    else { // 這里加else也可以 如果上面i正好把序列消耗完，則循環(huán)不會(huì)執(zhí)行
        while (i<len) {
            tr[i] = sr[i];
            i++;
        }
    }
}

void merge_sort(SqList *L) {
    int *tr = (int *)malloc(L->len*sizeof(int));
    int k=1;
    /*
     * 循環(huán)k為序列長(zhǎng)度，與遞歸的方式相比，正好反過來，非遞歸方式直接從序列為1開始合并，直到序列不小于待排序的數(shù)組長(zhǎng)度為止
     * 每次循環(huán)都是子序列*4變長(zhǎng)的過程
     */ 
    while (k<L->len) {
        merge_pass(L->r, tr, k, L->len); // 序列1變2
        k++;
        merge_pass(tr, L->r, k, L->len); // 序列2變4
        k++;
    }
}


int main(void) {
    SqList list = {
        {999,50,10,90,30,70,40,80,60,20},
        MAXSIZE
    };

    merge_sort(&list);
    printf("after merge_sort2:\n");
    for (int i=0; i<=MAXSIZE; i++) {
        printf("index: %d, value: %d\n",i,list.r[i]);
    }
    return 0;
}

output

?  c gcc sort_merge_norecursive.c&& ./a.out
after merge_sort2:
index: 0, value: 999
index: 1, value: 10
index: 2, value: 20
index: 3, value: 30
index: 4, value: 40
index: 5, value: 50
index: 6, value: 60
index: 7, value: 70
index: 8, value: 80
index: 9, value: 90

到此，相信大家對(duì)“c語(yǔ)言遞歸和非遞歸排序怎么實(shí)現(xiàn)”有了更深的了解，不妨來實(shí)際操作一番吧！這里是億速云網(wǎng)站，更多相關(guān)內(nèi)容可以進(jìn)入相關(guān)頻道進(jìn)行查詢，關(guān)注我們，繼續(xù)學(xué)習(xí)！