久久久精品一区ed2k-女人被男人叉到高潮的视频-中文字幕乱码一区久久麻豆樱花-俄罗斯熟妇真实视频

【408篇】C語言筆記-第十七章（考研必會的排序算法（下））-創(chuàng)新互聯(lián)

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

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

選擇排序分為：1.簡單選擇排序。2.堆排序（重要）。

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

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

動畫演示：
https://www.cs.usfca.edu/~galles/visualization/ComparisonSort.html

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

步驟：隨機10個元素->打印->選擇排序->打印。

#include#include#includetypedef int ElemType;
typedef struct {
    ElemType *elem; // 整型指針
    int TableLen; // 存儲動態(tài)數(shù)組里邊元素的個數(shù)，相當于之前的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));// 生成隨機數(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

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

進程已結(jié)束，退出代碼為 0
3. 時間復雜度與空間復雜度
第三節(jié)：歸并排序 
1. 歸并排序原理解析
如圖所示，我們把每兩個元素歸為一組，進行小組內(nèi)排序，然后再次把兩個有序小組合并為一個有序小組，不斷進行，最終合并為一個有序數(shù)組。
動畫演示：
https://www.cs.usfca.edu/~galles/visualization/ComparisonSort.html
2. 歸并排序代碼實戰(zhàn)
歸并排序的代碼是采用遞歸思想實現(xiàn)的。首先，最小下標值和大下標值相加并除以2，得到中間下標值mid，用MergeSort對low到mid排序，然后用MergeSort對mid+1到high排序。當數(shù)組的前半部分和后半部分都排好序，使用Merge函數(shù)對兩個有序數(shù)組進行合并。為了提高合并有序數(shù)組效率，在Merge函數(shù)內(nèi)定義了B[N]。首先，我們通過循環(huán)把數(shù)組A中從low到high的元素全部復制到B中，這是游標i從low開始，游標j從mid+1開始，誰小就將誰放入數(shù)組A，對其游標加1，并在每輪循環(huán)時對數(shù)組A的計數(shù)游標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的目的是無論遞歸調(diào)用多少次，都只有一個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++){ // 合并兩個有序數(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

進程已結(jié)束，退出代碼為 0
3. 時間復雜度與空間復雜度
第四節(jié)：小結(jié) 
所有排序算法時間與空間復雜度匯總
穩(wěn)定性是指排序前后，相等元素位置是否會被交換。
復雜性是指代碼編寫的難度。

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

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

                網(wǎng)頁網(wǎng)址：http://sd-ha.com/article48/ccooep.html
            

            

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

            

                廣告
                
            

            

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