<kbd id="daqct"></kbd>

  • <nav id="daqct"></nav>
    <wbr id="daqct"><pre id="daqct"></pre></wbr>
    <wbr id="daqct"></wbr>
    <form id="daqct"><th id="daqct"></th></form>
    更多課程 選擇中心

    C/C++培訓
    達內IT學院

    400-111-8989

    C++培訓中-簡單,堆排序的講解

    • 發布:C++培訓
    • 來源:網絡
    • 時間:2019-01-15 13:17

    在C++編程的工作中,排序應該是常見的操作了,雖然在項目開發中需要我們手動實現的幾率很小,但畢竟語言類庫中都有很多種關于排序算法的實現。對于這方面的提升對我們C++程序開發者來說還有多有益處的。那今天說到的淺談數據結構-選擇排序(簡單、堆排序),也是小編在C++培訓課程的筆記中整理所出,希望對大家有所幫助!那我接下來看下一下!

    選擇排序:每趟從待排序的記錄中選出關鍵字最小的記錄,順序放在已排序的記錄序列末尾,直到全部排序結束為止。

    選擇排序正如定義所講,在數組查詢出最小值,然后放在此次循環開始位置(前一次循環已經獲取比它更小的值放在前面)。

    簡單選擇排序就是單純的從數組中一次一次循環獲取到最小值,放到循環位置。而堆排序正如名字,是從一個堆中選擇,然后放在堆的循環開始位置,所以重點就是如何爭取獲取堆(分組)。

    一、簡單選擇排序

    1、算法思想

    C++培訓中-簡單,堆排序的講解

    正如圖上所示,每次選擇最小值,然后放在本次循環的開始位置。

    2、代碼

    //選擇排序
    
    void SortAlgorithm::SelectSort(pSqlList pList)
    
    {
    
    int i,j,min;
    
    printf("開始驗證選擇排序");
    
    //選擇排序和低級冒泡排序很像,關鍵就是在比較時,低級冒泡進行數據交換,而選擇排序進行記錄,最后只交換一次
    
    for (i =0;i<pList->length;i++)
    
    {
    
    min = i;
    
    for(j = pList->length-1;j>=i;j--)
    
    {
    
    //注意數組坐標,千萬別溢出
    
    if (pList->SqlArray[min] > pList->SqlArray[j])
    
    {
    
    min = j;
    
    }
    
    }
    
    //最后進行交換,先選擇最小的,最后一次交換
    
    swap(pList,i,min);
    
    PrintSqlList(pList);
    
    }
    
    }
    
    

    簡單選擇排序算法海華絲比較簡單,關鍵點就是遍歷尋找最小記錄,然后入循環開始位置進行交換。

    二、堆排序

    1、堆排序概念

    堆排序是首先引入完全二叉樹的概念,就是構建完全二叉樹,前提是完全二叉樹是有特點的,也就是大根堆和小根堆。

    C++培訓中-簡單,堆排序的講解

    上圖是完全二叉樹,在完全二叉樹中有幾個性質:

    設當前元素在數組中以R[i]表示,那么,

    (1) 它的左孩子結點是:R[2*i+1];

    (2) 它的右孩子結點是:R[2*i+2];

    (3) 它的父結點是:R[(i-1)/2];

    (4) R[i] <= R[2*i+1] 且 R[i] <= R[2i+2]。

    大根堆:每個結點的關鍵字都不小于其孩子結點的關鍵字。

    小根堆:每個結點的關鍵字都不大于其孩子結點的關鍵字。

    2、算法思想

    (1)根據初始數組去構造初始堆,默認是大根堆(構建一個完全二叉樹,保證所有的父結點都比它的孩子結點數值大)。

    (2)每次交換第一個和最后一個元素,輸出最后一個元素(最大值),然后把剩下元素重新調整為大根堆。

    上述算法是個循環操作,先構建,然后交換輸出,最后調整余下的為大根堆,其實就是尋找最大值,其實只需要左右兩個結點,那個比較大,就獲取那個,所以調整堆排序也是比較簡單,就是比較左右結點,獲取最大值

    第一步:構建大根堆

    C++培訓中-簡單,堆排序的講解

    第二步、輸出、調整

    C++培訓中-簡單,堆排序的講解

    3、代碼


    ////堆排序
    
    void SortAlgorithm::HeapSort(pSqlList pList)
    
    {
    
    //循環構建堆
    
    for (int i = pList->length/2;i>0;i--)
    
    {
    
    AdjustHeap(pList,i,pList->length-1);
    
    }
    
    PrintSqlList(pList);
    
    for (int i = pList->length-1;i>1;i--)
    
    {
    
    //循環輸出根節點,同時再次調整為大根堆
    
    swap(pList,1,i); //根節點位于最前面,也就是1,這樣就將1最大值,放在數組后面了
    
    AdjustHeap(pList,1,i-1);
    
    PrintSqlList(pList);
    
    }
    
    }
    
    inline void SortAlgorithm::AdjustHeap(pSqlList pList,int start,int length)
    
    {
    
    int temp = pList->SqlArray[start]; //這是分支節點,然后比較它的分支節點,也就是2i
    
    for (int i = 2*start;i<length;i = i*2)
    
    {
    
    //獲取左右結點中比較大的值的坐標
    
    if (i<length && pList->SqlArray[i] < pList->SqlArray[i+1])
    
    {
    
    i++;
    
    }
    
    //如果根節點本來就大,無序調整
    
    if (temp > pList->SqlArray[i])
    
    {
    
    break;
    
    }
    
    //交換值,將左右結點大值放在根節點
    
    pList->SqlArray[start] = pList->SqlArray[i];
    
    start = i;
    
    }
    
    //將開始需要比較的值,放在最后交換出的位置上
    
    pList->SqlArray[start] = temp;
    
    }
    

     

    4、代碼分析

    程序中一開始構建,調整大根堆,最大值是length/2,因為從完全二叉樹的概念上分析:

    C++培訓中-簡單,堆排序的講解

    在上圖中大根堆的建立,就是調整前四個元素的位置,就是放再分支節點上還是葉子結點上,所以只要輸入4即可。

    C++培訓中-簡單,堆排序的講解

    一開始大根堆,發現是90在最前面。

    首先,將位于第一位(根節點樹最大),然后和最后一位交換,然后調整前8位(第九位已經是最大了)。

    然后,再講獲取到的80,和最后一位(第九位,第十已經不需交換),然后調整前7位,當然都是從1開始了。

    最后經過一次次循環調整,完成算法的排序。

    其中關鍵的思想是獲取調整堆排序,比如一開始90和20交換后,20位于第一位置;此時20和左右結點中的較大值80交換,關鍵是后續繼續拿20和后面左右結點比較,直到break,也就是找到比它小的,跳出,然后賦值。

    三、性能分析

    1、簡單選擇排序

    從簡單選擇排序的過程來看,它最大的特點就是交換移動數據次數相當少,這樣也就節約了相應的時間。分析它的時間復雜度,無論最好最差的情況,其比較次數都是一樣多,第i趟排序需要進行n-i次關鍵字的比較,此時需要n-1 +...+1 = n(n - 1)/2次。而對于交換次數而言,當最好的時候,交換次數為0,最差的時候,也就初始降序時,交換次數為n-1次。總的時間復雜度依然為O(n2)。

    盡管簡單選擇排序與冒泡排序同為O(n2),但簡單選擇排序的性能上還是要優于冒泡排序的。

    2、堆排序

    堆排序是一種不穩定的排序方法。

    因為在堆的調整過程中,關鍵字進行比較和交換所走的是該結點到葉子結點的一條路徑。

    在程序運行時主要消耗在初始化構建堆和重建堆的反復刷選上。在初始化構建堆時,是從非終結點開始,其實比較兩次,本來時n/2,這樣最多對n/2進行兩次比較工作,所以初始化構建大根堆是O(n)。

    在調整構建堆時,第i次構建樹logI(根據完全二叉樹性質),需要遍歷N-1記錄,所以時間復雜度是O(nlogn)

    以上盡是數據結構-選擇排序(簡單、堆排序)的進本講解內容,達內C++培訓班新一期又在招生中哦,同學們如果有興趣歡迎你們的垂詢。

    免責聲明:內容和圖片源自網絡,版權歸原作者所有,如有侵犯您的原創版權請告知,我們將盡快刪除相關內容

    預約申請免費試聽課

    填寫下面表單即可預約申請免費試聽!怕錢不夠?可就業掙錢后再付學費! 怕學不會?助教全程陪讀,隨時解惑!擔心就業?一地學習,可全國推薦就業!

    上一篇:C++制作經典游戲拳皇97
    下一篇:C++開發中auto的講解教程

    C語言創建windows窗口實例

    C++回調函數是什么?

    C++ shared_ptr和動態數組

    C語言有哪些關鍵詞,C語言44個關鍵詞大全

    • 掃碼領取資料

      回復關鍵字:視頻資料

      免費領取 達內課程視頻學習資料

    • 視頻學習QQ群

      添加QQ群:1143617948

      免費領取達內課程視頻學習資料

    Copyright ? 2021 Tedu.cn All Rights Reserved 京ICP備08000853號-56 京公網安備 11010802029508號 達內時代科技集團有限公司 版權所有

    選擇城市和中心
    黑龍江省

    吉林省

    河北省

    湖南省

    貴州省

    云南省

    廣西省

    海南省

    欧美三级片,白洁外传,第四色播日韩AV第一页,啪啪免费观看大全av 百度 好搜 搜狗
    <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <文本链> <文本链> <文本链> <文本链> <文本链> <文本链>