文章目錄

• • 第一節(jié)：選擇排序
  • • 1. 選擇排序原理解析
    • 2. 選擇排序代碼實(shí)戰(zhàn)
    • 3. 時(shí)間復(fù)雜度與空間復(fù)雜度
  • 第二節(jié)：堆排序
  • • 1. 堆排序原理解析
    • 2. 堆排序代碼實(shí)戰(zhàn)
    • 3. 時(shí)間復(fù)雜度與空間復(fù)雜度
  • 第三節(jié)：歸并排序
  • • 1. 歸并排序原理解析
    • 2. 歸并排序代碼實(shí)戰(zhàn)
    • 3. 時(shí)間復(fù)雜度與空間復(fù)雜度
  • 第四節(jié)：小結(jié)
  • • 所有排序算法時(shí)間與空間復(fù)雜度匯總

創(chuàng)新互聯(lián)建站是專業(yè)的尚志網(wǎng)站建設(shè)公司，尚志接單;提供成都網(wǎng)站設(shè)計(jì)、網(wǎng)站制作、外貿(mào)營(yíng)銷網(wǎng)站建設(shè),網(wǎng)頁(yè)設(shè)計(jì),網(wǎng)站設(shè)計(jì),建網(wǎng)站,PHP網(wǎng)站建設(shè)等專業(yè)做網(wǎng)站服務(wù);采用PHP框架,可快速的進(jìn)行尚志網(wǎng)站開發(fā)網(wǎng)頁(yè)制作和功能擴(kuò)展;專業(yè)做搜索引擎喜愛的網(wǎng)站,專業(yè)的做網(wǎng)站團(tuán)隊(duì),希望更多企業(yè)前來(lái)合作!第一節(jié)：選擇排序 1. 選擇排序原理解析

選擇排序分為：1.簡(jiǎn)單選擇排序。2.堆排序（重要）。

簡(jiǎn)單選擇排序原理：假設(shè)排序表為L(zhǎng)[1,2,……n]，第i趟排序即從L[i……n]中選擇關(guān)鍵字最小的元素與L(i)交換，每一趟排序可以確定一個(gè)元素的最終位置，這樣經(jīng)過(guò)n-1趟排序就可使得整個(gè)排序表有序。

首先嘉定第0個(gè)元素是最小的，把下標(biāo)0賦給min（min記錄最小的元素的下標(biāo)），內(nèi)層比較時(shí)，從1號(hào)元素一直比較到9號(hào)元素，誰(shuí)更小，就把它的下標(biāo)賦給min，一輪比較結(jié)束后，將min對(duì)應(yīng)的位置的元素與元素i交換。第一輪確認(rèn)2最小，將2與數(shù)組開頭的元素3交換，第二輪我們最初認(rèn)為87最小，經(jīng)過(guò)一輪比較，發(fā)現(xiàn)3最小，將87與3交換。持續(xù)進(jìn)行，最終使數(shù)組有序。

動(dòng)畫演示：
https://www.cs.usfca.edu/~galles/visualization/ComparisonSort.html

2. 選擇排序代碼實(shí)戰(zhàn)

步驟：隨機(jī)10個(gè)元素->打印->選擇排序->打印。

#include#include#includetypedef int ElemType;
typedef struct {
    ElemType *elem; // 整型指針
    int TableLen; // 存儲(chǔ)動(dòng)態(tài)數(shù)組里邊元素的個(gè)數(shù)，相當(dāng)于之前的len
}SSTable;

// 初始化鏈表
void ST_Init(SSTable &ST,int len){
    ST.TableLen=len;
    ST.elem= (ElemType*)malloc(sizeof(ElemType)*ST.TableLen);
    int i;
    srand(time(NULL));// 生成隨機(jī)數(shù)
    for(i=0;i
F:\Computer\Project\practice\17\17.3-selectSort\cmake-build-debug\17_3_selectSort.exe
  5  8 65 13 26 38 40 65 82 97
  5  8 13 26 38 40 65 65 82 97

進(jìn)程已結(jié)束，退出代碼為 0
3. 時(shí)間復(fù)雜度與空間復(fù)雜度
時(shí)間復(fù)雜度O(
    
     
      
       
        
         n
        
        
         2
        
       
      
      
       n^2
      
     
    n2)。
空間復(fù)雜度O(1)。
第二節(jié)：堆排序 
1. 堆排序原理解析
堆（Heap）是計(jì)算機(jī)科學(xué)中的一種特殊的樹狀數(shù)據(jù)結(jié)構(gòu)。若滿足以下特性，則可稱為堆：“給定堆中任意節(jié)點(diǎn)P和C，若P是C的父結(jié)點(diǎn)，則P的值小于等于（或大于等于）C的值。”若父結(jié)點(diǎn)的值恒小于等于子結(jié)點(diǎn)的值，則該堆稱為最小堆（min heap），反之，稱為大堆（max heap）。堆中最頂端的那個(gè)結(jié)點(diǎn)稱為根結(jié)點(diǎn)（root node），根結(jié)點(diǎn)本身沒有父結(jié)點(diǎn)（parent node）。平時(shí)工作中，我們將最小堆稱為小根堆或小頂堆，把大堆稱為大根堆或大頂堆。
假設(shè)我們有3,87,2,93,78,56,61,38,12,40共10個(gè)元素，我們將這10個(gè)元素建成一棵完全二叉樹，這里采用層次建樹法，雖然只有一個(gè)數(shù)組存儲(chǔ)元素，但是我們能將二叉樹中任意一個(gè)位置的元素對(duì)應(yīng)到數(shù)組下標(biāo)上，我們將二叉樹中每個(gè)元素到數(shù)組下標(biāo)的這種數(shù)據(jù)結(jié)構(gòu)稱為堆。比如最后一個(gè)父元素的下標(biāo)是n/2-1，也就是a[4]，對(duì)應(yīng)的值是78?？梢赃@樣記憶：如果父結(jié)點(diǎn)的下標(biāo)是dad，那么父結(jié)點(diǎn)對(duì)應(yīng)的左子結(jié)點(diǎn)的下標(biāo)值是2*dad+1。接著，依次將沒棵子樹都調(diào)整為父結(jié)點(diǎn)大，最終整棵樹將變成一個(gè)大根堆。
動(dòng)畫演示：
https://www.cs.usfca.edu/~galles/visualization/HeapSort.html
2. 堆排序代碼實(shí)戰(zhàn)
堆排序的步驟是首先把堆調(diào)整為大根堆，然后我們交換根部元素也就是A[0]和最后一個(gè)元素，這樣大的元素就放到了數(shù)組最后，接著我們將剩余9個(gè)元素繼續(xù)調(diào)整成大根堆，然后交換A[0]和9個(gè)元素最后一個(gè)，循環(huán)往復(fù)，直到有序。
#include#include#include#includetypedef int ElemType;
typedef struct {
    ElemType *elem; // 整型指針
    int TableLen; // 存儲(chǔ)動(dòng)態(tài)數(shù)組里邊元素的個(gè)數(shù)，相當(dāng)于之前的len
}SSTable;

// 初始化鏈表
void ST_Init(SSTable &ST,int len){
    ST.TableLen=len;
    ST.elem= (ElemType*)malloc(sizeof(ElemType)*ST.TableLen);
    int i;
    srand(time(NULL));// 生成隨機(jī)數(shù)
    for(i=0;i=0;i--){
        AdjustDown(A,i,len);
    }
    swap(A[0],A[len]);// 交換頂部和數(shù)組最后一個(gè)元素
    // 下面的策略是，不斷調(diào)整剩余元素為大根堆，因?yàn)楦看?，所以再次與A[i]交換，相當(dāng)于放數(shù)組后面，循環(huán)往復(fù)
    for(i=len-1;i>0;i--){
        AdjustDown(A,0,i);// 剩余元素調(diào)整為大根堆
        swap(A[0],A[i]);
    }
}
int main() {
    SSTable ST;
    ST_Init(ST,10);
    ElemType A[10]={3,87,2,93,78,56,61,38,12,40};
    memcpy(ST.elem,A, sizeof(A));
    ST_print(ST);
    HeapSort(ST.elem,9); // 所有元素參與排序
    ST_print(ST);
    return 0;
}
F:\Computer\Project\practice\17\17.5-heapSort\cmake-build-debug\17_5_heapSort.exe
  3 87  2 93 78 56 61 38 12 40
  2  3 12 38 40 56 61 78 87 93

進(jìn)程已結(jié)束，退出代碼為 0
3. 時(shí)間復(fù)雜度與空間復(fù)雜度
第三節(jié)：歸并排序 
1. 歸并排序原理解析
如圖所示，我們把每?jī)蓚€(gè)元素歸為一組，進(jìn)行小組內(nèi)排序，然后再次把兩個(gè)有序小組合并為一個(gè)有序小組，不斷進(jìn)行，最終合并為一個(gè)有序數(shù)組。
動(dòng)畫演示：
https://www.cs.usfca.edu/~galles/visualization/ComparisonSort.html
2. 歸并排序代碼實(shí)戰(zhàn)
歸并排序的代碼是采用遞歸思想實(shí)現(xiàn)的。首先，最小下標(biāo)值和大下標(biāo)值相加并除以2，得到中間下標(biāo)值mid，用MergeSort對(duì)low到mid排序，然后用MergeSort對(duì)mid+1到high排序。當(dāng)數(shù)組的前半部分和后半部分都排好序，使用Merge函數(shù)對(duì)兩個(gè)有序數(shù)組進(jìn)行合并。為了提高合并有序數(shù)組效率，在Merge函數(shù)內(nèi)定義了B[N]。首先，我們通過(guò)循環(huán)把數(shù)組A中從low到high的元素全部復(fù)制到B中，這是游標(biāo)i從low開始，游標(biāo)j從mid+1開始，誰(shuí)小就將誰(shuí)放入數(shù)組A，對(duì)其游標(biāo)加1，并在每輪循環(huán)時(shí)對(duì)數(shù)組A的計(jì)數(shù)游標(biāo)k加1。
#include#include#define N 7
typedef int ElemType;
// 49,38,65,97,76,13,27

// 合并數(shù)組
void Merge(ElemType A[],int low,int mid,int high){
    static ElemType B[N]; // 加static的目的是無(wú)論遞歸調(diào)用多少次，都只有一個(gè)B[N]
    int i,j,k;
    for(k=low;k<=high;k++){ // 賦值元素到B中
        B[k]=A[k];
    }
    for(i=low,j=mid+1,k=i;i<=mid&& j<=high;k++){ // 合并兩個(gè)有序數(shù)組
        if(B[i]<=B[j]){
            A[k]=B[i++];
        } else{
            A[k]=B[j++];
        }
    }
    while (i<=mid){ // 如果右剩余，直接放入即可
        A[k++]=B[i++]; // 前一半有剩余的放入
    }
    while (j<=high){
        A[k++]=B[j++];//后一半的有剩余的放入
    }
}
// 歸并排序
void MergeSort(ElemType A[],int low,int high){
    if(low
F:\Computer\Project\practice\17\17.6-mergeSort\cmake-build-debug\17_6_mergeSort.exe
 49 38 65 97 76 13 27
 13 27 38 49 65 76 97

進(jìn)程已結(jié)束，退出代碼為 0
3. 時(shí)間復(fù)雜度與空間復(fù)雜度
第四節(jié)：小結(jié) 
所有排序算法時(shí)間與空間復(fù)雜度匯總
穩(wěn)定性是指排序前后，相等元素位置是否會(huì)被交換。
復(fù)雜性是指代碼編寫的難度。
                
     
你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級(jí)流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級(jí)服務(wù)器適合批量采購(gòu)，新人活動(dòng)首月15元起，快前往官網(wǎng)查看詳情吧
            

                網(wǎng)頁(yè)題目：【408篇】C語(yǔ)言筆記-第十七章（考研必會(huì)的排序算法（下））-創(chuàng)新互聯(lián)
                

                網(wǎng)頁(yè)網(wǎng)址：http://aaarwkj.com/article48/ccooep.html
            
            

                成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供網(wǎng)站營(yíng)銷、品牌網(wǎng)站建設(shè)、電子商務(wù)、網(wǎng)站改版、外貿(mào)網(wǎng)站建設(shè)、動(dòng)態(tài)網(wǎng)站            
            

                廣告
                
            
            

                聲明：本網(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í)需注明來(lái)源：
                創(chuàng)新互聯(lián)