數(shù)據(jù)結(jié)構(gòu)——排序-創(chuàng)新互聯(lián)

目錄

建昌網(wǎng)站建設(shè)公司成都創(chuàng)新互聯(lián),建昌網(wǎng)站設(shè)計(jì)制作，有大型網(wǎng)站制作公司豐富經(jīng)驗(yàn)。已為建昌近1000家提供企業(yè)網(wǎng)站建設(shè)服務(wù)。企業(yè)網(wǎng)站搭建\成都外貿(mào)網(wǎng)站制作要多少錢，請(qǐng)找那個(gè)售后服務(wù)好的建昌做網(wǎng)站的公司定做！

個(gè)人觀點(diǎn)：

排序的概念：

排序的穩(wěn)定性：

內(nèi)排序與外排序：

概念：

排序用到的結(jié)構(gòu)與函數(shù)：

代碼：

最簡(jiǎn)單排序的實(shí)現(xiàn)：

舉例：

代碼：

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

冒泡排序：

舉例：

代碼：

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

在優(yōu)化：

舉例：

代碼：

簡(jiǎn)單選擇排序：

思想:

代碼:

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

直接插入排序：

舉例：

代碼：

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

希爾排序：

分析：

舉例：

推薦視頻：

代碼：

注意：

堆排序：

堆定義;

舉例：

基本思想：

舉例：

代碼：

歸并排序：

算法思想：

理解圖解：

舉例：

分析一下它的合并操作是如何進(jìn)行的：

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

快速排序：

算法思想：

舉例：

代碼：

個(gè)人觀點(diǎn)：

（僅代表個(gè)人）

對(duì)于我初學(xué)者來講，排序這個(gè)章節(jié)我們注重的思想而不是用法（個(gè)人看法而言，因?yàn)槲宜㈩}量很少，對(duì)我來說sort現(xiàn)在夠用），那么我們就先注重這些算法的內(nèi)容思想。

排序的概念：

排序的穩(wěn)定性：

通俗來講就是相同的關(guān)鍵字，在排序之后，它們的前后關(guān)系不會(huì)變

舉例

內(nèi)排序與外排序： 概念：

內(nèi)排序是在整個(gè)排序過程中，待排序的所有記錄全部被放置在內(nèi)存中。

外排序是由于排序記錄個(gè)數(shù)過多，不能同時(shí)防止在內(nèi)存中，整個(gè)排序過程需要在內(nèi)外存之間多次數(shù)據(jù)交換才能進(jìn)行

對(duì)于內(nèi)排序性能而言：

（1）時(shí)間性能

（2）輔助空間

（3）算法復(fù)雜性

內(nèi)排序分為插入排序、交換排序、選擇排序和歸并排序

排序用到的結(jié)構(gòu)與函數(shù)： 代碼：
#includeusing namespace std;

const int N=1e3+10;
int n;

typedef struct{
    int res[N];
    int len=0;
}Sqlist;

void swaq(Sqlist*L,int i,int j){
    int temp=L->res[i];
    L->res[i]=L->res[j];
    L->res[j]=temp;
}

int main(){
    Sqlist L;
    cin>>n;
    for(int i=1;i>L.res[i];
        L.len++;
    }
    cout<
最簡(jiǎn)單排序的實(shí)現(xiàn)：

它的基本思想就是相鄰兩兩比較，有冒泡思想但不是冒泡排序

舉例：

下標(biāo)從1開始

代碼：
#includeusing namespace std;

const int N=1e3+10;
int n;

typedef struct{
    int res[N];
    int len;
}Sqlist;

void swaq(Sqlist*L,int i,int j){
    int temp=L->res[i];
    L->res[i]=L->res[j];
    L->res[j]=temp;
}

void BubbleSort0(Sqlist*L){
    for(int i=1;i<=L->len;i++){
        for(int j=1;j<=L->len;j++){
            if(L->res[i]>L->res[j])
            swaq(L,i,j);
        }
    }
}

int main(){
    Sqlist L;
    cin>>n;
    for(int i=1;i>L.res[i];
        L.len++;
    }
    for(int i=1;i<=L.len;i++)cout<
時(shí)間復(fù)雜度:

時(shí)間復(fù)雜度高，O(n^2)


冒泡排序： 舉例：

從后往前交換，則必定會(huì)把相對(duì)小的數(shù)向前移動(dòng)，時(shí)間復(fù)雜度提高了

代碼：
#includeusing namespace std;

const int N=1e3+10;
int n;

typedef struct{
    int res[N];
    int len;
}Sqlist;

void swaq(Sqlist*L,int i,int j){
    int temp=L->res[i];
    L->res[i]=L->res[j];
    L->res[j]=temp;
}

void Bubblesort(Sqlist*L){
    for(int i=1;ilen;i++){
        for(int j=L->len-1;j>=i;j--){
            if(L->res[j]>L->res[j+1])
            swaq(L,j,j+1);
        }
    }
}

int main(){
    Sqlist L;
    cin>>n;
    for(int i=1;i>L.res[i];
        L.len++;
    }
    Bubblesort(&L);
    for(int i=1;i<=L.len;i++){
        cout<
時(shí)間復(fù)雜度：

O(n^2)，但是相對(duì)來說總歸有優(yōu)化



在優(yōu)化： 舉例：

代碼：
#includeusing namespace std;

const int N=1e3+10;
int n;

typedef struct{
    int res[N];
    int len;
}Sqlist;

void swaq(Sqlist*L,int i,int j){
    int temp=L->res[i];
    L->res[i]=L->res[j];
    L->res[j]=temp;
}

void Bubblesort(Sqlist*L){
    for(int i=1;ilen;i++){
        bool flag=1;
        for(int j=L->len-1;j>=i;j--){
            if(L->res[j]>L->res[j+1])
            swaq(L,j,j+1);
            flag=0;
        }
        if(flag)
            break;
    }
}

int main(){
    Sqlist L;
    cin>>n;
    for(int i=1;i>L.res[i];
        L.len++;
    }
    Bubblesort(&L);
    for(int i=1;i<=L.len;i++){
        cout<
簡(jiǎn)單選擇排序： 思想:

與冒泡排序差不多，只不過不是遇見小的就交換，而是每次循環(huán)遇到最小的才交換

代碼:
#includeusing namespace std;

const int N=1e3+10;
int n;

typedef struct{
    int res[N];
    int len;
}Sqlist;

void swaq(Sqlist*L,int i,int j){
    int temp=L->res[i];
    L->res[i]=L->res[j];
    L->res[j]=temp;
}

void Selectsort(Sqlist*L){
    int j,mn;
    for(int i=1;ilen;i++){
        mn=i;
        bool flag=0;
        for(j=i+1;j<=L->len;j++){
            if(L->res[mn]>L->res[j]){
                mn=j;
                flag=1;
            }
        }
        if(flag)
            swaq(L,i,mn);
    }
}

int main(){
    Sqlist L;
    cin>>n;
    for(int i=1;i>L.res[i];
        L.len++;
    }
    Selectsort(&L);
    for(int i=1;i<=L.len;i++){
        cout<
時(shí)間復(fù)雜度：

O(n^2)，但是相對(duì)于冒泡排序，總歸有一定的優(yōu)化

直接插入排序： 舉例：

此時(shí)哨兵（L.res[0]）就起到了作用

代碼：
#includeusing namespace std;

const int N=1e3+10;
int n;

typedef struct{
    int res[N];
    int len;
}Sqlist;

void swaq(Sqlist*L,int i,int j){
    int temp=L->res[i];
    L->res[i]=L->res[j];
    L->res[j]=temp;
}

void Insertsort(Sqlist*L){
    int j;
    for(int i=2;i<=L->len;i++){
        if(L->res[i]res[i-1]){
            L->res[0]=L->res[i];
            for(j=i-1;L->res[j]>L->res[0];j--)
                L->res[j+1]=L->res[j];
            L->res[j+1]=L->res[0];
        }
    }
}

int main(){
    Sqlist L;
    cin>>n;
    for(int i=1;i>L.res[i];
        L.len++;
    }
    Insertsort(&L);
    for(int i=1;i<=L.len;i++){
        cout<

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

O(n^2)，但是時(shí)間效率更好點(diǎn)

希爾排序： 分析：

希爾排序是在直接插入排序上的優(yōu)化

直接插入排序的最好情況：{2,3,4,5,6}，時(shí)間復(fù)雜度為O（n）

最壞情況：{6,5,4,3,2}，時(shí)間復(fù)雜度為O（n^2）

希爾排序是將一個(gè)數(shù)組分為若干個(gè)子序列，然后各自排序然后合并，實(shí)現(xiàn)基本有序

基本有序，就是小的關(guān)鍵字基本在前面，大的關(guān)鍵字基本在后面

采用跳躍式分割策略。。。

舉例：

推薦視頻：

排序算法：希爾排序【圖解+代碼】_嗶哩嗶哩_bilibili

代碼：
#includeusing namespace std;

const int N=1e3+10;
int n;

typedef struct{
    int res[N];
    int len;
}Sqlist;

void shellsort(Sqlist*L){
    int i,j,k=0;
    int lon=L->len;
    do{
        lon=lon/3+1;
        for(i=lon+1;i<=L->len;i++){
            if(L->res[i]res[i-lon]){
                L->res[0]=L->res[i];
                for(j=i-lon;j>0&&L->res[0]res[j];j-=lon){
                    L->res[j+lon]=L->res[j];
                }
                L->res[j+lon]=L->res[0];
            }
        }
        
        
    }while(lon>1);
}

int main(){
    Sqlist L;
    cin>>n;
    for(int i=1;i>L.res[i];
        L.len++;
    }
    shellsort(&L);
    for(int i=1;i<=L.len;i++){
        cout<
注意：

增量序列的最后一個(gè)增量必須等于1才行

堆排序： 堆定義;

其實(shí)就是特殊的完全二叉樹

舉例：

大頂堆，所有結(jié)點(diǎn)大于其左右孩子結(jié)點(diǎn)，小頂堆反之

基本思想：

將待排序的序列構(gòu)造成一個(gè)大頂堆。此時(shí)整個(gè)序列的大值就是堆頂?shù)母Y(jié)點(diǎn)

將它移走（其實(shí)就是將其與堆數(shù)組末尾元素交換，此時(shí)末尾元素就是大值），然后將剩余的n-1

個(gè)序列重新構(gòu)造一個(gè)堆，這樣就會(huì)得到n個(gè)元素中的次大值，反復(fù)執(zhí)行，便能得到一個(gè)有序序列

舉例：

（建樹）

代碼：

歸并排序：

算法思想：

是利用歸并的思想實(shí)現(xiàn)的排序方法，通俗理解起來就是

對(duì)于一個(gè)無序的數(shù)組，先讓子序列為1的序列兩兩歸并，然后讓子序列為2的序列兩兩歸并，以此類推

理解圖解：

舉例：

分析一下它的合并操作是如何進(jìn)行的：

舉例：

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

快速排序： 算法思想：

通過一趟排序?qū)⒋庞涗浄指畛蓛刹糠?，其中一部分記錄的關(guān)鍵字均比另一部分記錄的關(guān)鍵字小，然后對(duì)這兩部分繼續(xù)進(jìn)行排序，以達(dá)到整個(gè)序列有序的目的

舉例：

代碼：

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級(jí)流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級(jí)服務(wù)器適合批量采購，新人活動(dòng)首月15元起，快前往官網(wǎng)查看詳情吧

文章標(biāo)題：數(shù)據(jù)結(jié)構(gòu)——排序-創(chuàng)新互聯(lián)
鏈接URL：http://bm7419.com/article24/dsegce.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供電子商務(wù)、關(guān)鍵詞優(yōu)化、網(wǎng)站改版、移動(dòng)網(wǎng)站建設(shè)、軟件開發(fā)、App設(shè)計(jì)

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來源： 創(chuàng)新互聯(lián)

成都網(wǎng)站建設(shè)