數(shù)據(jù)結(jié)構(gòu)與算法學(xué)習(xí)-常見的排序算法

排序可以分為2類:

  • 內(nèi)排序:是在排序整個過程中,待排序的所有記錄全部被放置在內(nèi)存中;
  • 外排序:由于排序的記錄個數(shù)太多,不能同時放置在內(nèi)存,整個排序過程需要在內(nèi)外存之間多次交換數(shù)據(jù)才能進行;
    排序代碼準備:
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0

typedef int Status;

//1.排序算法數(shù)據(jù)結(jié)構(gòu)設(shè)計
//用于要排序數(shù)組個數(shù)最大值氧苍,可根據(jù)需要修改
#define MAXSIZE 10000
typedef struct
{
    //用于存儲要排序數(shù)組,r[0]用作哨兵或臨時變量
    int r[MAXSIZE+1];
    //用于記錄順序表的長度
    int length;
}SqList;


//2.排序常用交換函數(shù)實現(xiàn)
//交換L中數(shù)組r的下標為i和j的值
void swap(SqList *L,int i,int j)
{
    int temp=L->r[i];
    L->r[i]=L->r[j];
    L->r[j]=temp;
}

//3.數(shù)組打印
void print(SqList L)
{
    int i;
    for(i=1;i<L.length;i++)
        printf("%d,",L.r[i]);
    printf("%d",L.r[i]);
    printf("\n");
}

冒泡排序

冒泡排序(Bubble Sort) 一種交換排序,它的基本思想就是: 兩兩比較相鄰的記錄的關(guān)鍵字,如果反序則交換,直到?jīng)]有反序的記錄為?侮邀。
代碼實現(xiàn):

void BubbleSort2(SqList *L){
    int i,j;
    //flag用作標記
    Status flag = TRUE;
    
    //i從[1,L->length) 遍歷;
    //如果flag為False退出循環(huán). 表示已經(jīng)出現(xiàn)過一次j從L->Length-1 到 i的過程,都沒有交換的狀態(tài);
    for (i = 1; i < L->length && flag; i++) {
        
        //flag 每次都初始化為FALSE
        flag = FALSE;
        
        for (j = L->length-1; j>=i; j--) {
            
            if(L->r[j] > L->r[j+1]){
            //交換L->r[j]和L->r[j+1]值;
            swap(L, j, j+1);
            //如果有任何數(shù)據(jù)的交換動作,則將flag改為true;
            flag=TRUE;
            }
        }
    }
}

簡單選擇排序

簡單排序算法(Simple Selection Sort) 就是通過n-i次關(guān)鍵詞比較,從n-i+1個記錄中找出關(guān)鍵 字最小的記錄,并和第i(1<=i<=n) 個記錄進行交換.

void SelectSort(SqList *L){
    
    int i,j,min;

    for (i = 1; i < L->length; i++) {
        //① 將當(dāng)前下標假設(shè)為最小值的下標
        min = i;
        //② 循環(huán)比較i之后的所有數(shù)據(jù)
        for (j = i+1; j <= L->length; j++) {
            //③ 如果有小于當(dāng)前最小值的關(guān)鍵字,將此關(guān)鍵字的下標賦值給min
            if (L->r[min] > L->r[j]) {
                min = j;
            }
        }
        
        //④ 如果min不等于i,說明找到了最小值,則交換2個位置下的關(guān)鍵字
        if(i!=min)
            swap(L, i, min);
    }
}

直接插?入排序

直接插入排序算法(Stright Insertion Sort)的基本操作是將一個記錄插入到已經(jīng)排好序的有序表中,從而得到一個新的,記錄數(shù)增1的有序表;
代碼實現(xiàn):

void InsertSort(SqList *L){
    int i,j;
    //L->r[0] 哨兵 可以把temp改為L->r[0]
    int temp=0;
    
    //假設(shè)排序的序列集是{0,5,4,3,6,2};
    //i從2開始的意思是我們假設(shè)5已經(jīng)放好了. 后面的牌(4,3,6,2)是插入到它的左側(cè)或者右側(cè)
    for(i=2;i<=L->length;i++)
    {
        //需將L->r[i]插入有序子表
        if (L->r[i]<L->r[i-1])
        {
            //設(shè)置哨兵 可以把temp改為L->r[0]
            temp = L->r[i];
            for(j=i-1;L->r[j]>temp;j--)
                    //記錄后移
                    L->r[j+1]=L->r[j];
            
            //插入到正確位置 可以把temp改為L->r[0]
            L->r[j+1]=temp;
        }
    }
}

希爾排序

希爾排序思想: 希爾排序是把記錄按下標的一定增量分組谒府,對每組使用直接插入排序算法排序;隨著增量逐漸減少诚卸,每組包含的關(guān)鍵詞越來越多芜繁,當(dāng)增量減至1時鳍咱,整個序列恰被分成 一組纽什,算法便終止.
代碼實現(xiàn):

void shellSort(SqList *L){
    int i,j;
    int increment = L->length;
    
    //0,9,1,5,8,3,7,4,6,2
    //① 當(dāng)increment 為1時,表示希爾排序結(jié)束
    do{
        //② 增量序列
        increment = increment/3+1;
        //③ i的待插入序列數(shù)據(jù) [increment+1 , length]
        for (i = increment+1; i <= L->length; i++) {
            //④ 如果r[i] 小于它的序列組元素則進行插入排序,例如3和9. 3比9小,所以需要將3與9的位置交換
            if (L->r[i] < L->r[i-increment]) {
                //⑤ 將需要插入的L->r[i]暫時存儲在L->r[0].和插入排序的temp 是一個概念;
                L->r[0] = L->r[i];
                
                //⑥ 記錄后移
                for (j = i-increment; j > 0 && L->r[0]<L->r[j]; j-=increment) {
                    L->r[j+increment] = L->r[j];
                }
                
                //⑦ 將L->r[0]插入到L->r[j+increment]的位置上;
                L->r[j+increment] = L->r[0];
            }
        }
    }while (increment > 1);
}

堆排序

堆排序(Heap Sort) 就是利用堆(假設(shè)我們選擇大頂堆)進行排序的算法.它的基本思想:

  • 1將待排序的序列構(gòu)成一個大頂堆,此時,整個序列的最大值就堆頂?shù)母Y(jié)點,將 它移走(其實就是將其與堆數(shù)組的末尾元素交換, 此時末尾元素就是最大值);
  • 2然后將剩余的n-1個序列列重新構(gòu)成一個隊,這樣就會得到n個元素的次大值, 如此重復(fù)執(zhí)行,就能得到一個有序列了
    代碼實現(xiàn):
//大頂堆調(diào)整函數(shù);
/*
 條件: 在L.r[s...m] 記錄中除了下標s對應(yīng)的關(guān)鍵字L.r[s]不符合大頂堆定義,其他均滿足;
 結(jié)果: 調(diào)整L.r[s]的關(guān)鍵字,使得L->r[s...m]這個范圍內(nèi)符合大頂堆定義.
 */
void HeapAjust(SqList *L,int s,int m){
    
    int temp,j;
    //① 將L->r[s] 存儲到temp ,方便后面的交換過程;
    temp = L->r[s];
    
    //② j 為什么從2*s 開始進行循環(huán),以及它的遞增條件為什么是j*2
    //因為這是顆完全二叉樹,而s也是非葉子根結(jié)點. 所以它的左孩子一定是2*s,而右孩子則是2s+1;(二叉樹性質(zhì)5)
    for (j = 2 * s; j <=m; j*=2) {
        
        //③ 判斷j是否是最后一個結(jié)點, 并且找到左右孩子中最大的結(jié)點;
        //如果左孩子小于右孩子,那么j++; 否則不自增1. 因為它本身就比右孩子大;
        if(j < m && L->r[j] < L->r[j+1])
            ++j;
        
        //④ 比較當(dāng)前的temp 是不是比較左右孩子大; 如果大則表示我們已經(jīng)構(gòu)建成大頂堆了;
        if(temp >= L->r[j])
            break;
        
        //⑤ 將L->[j] 的值賦值給非葉子根結(jié)點
        L->r[s] = L->r[j];
        //⑥ 將s指向j; 因為此時L.r[4] = 60, L.r[8]=60. 那我們需要記錄這8的索引信息.等退出循環(huán)時,能夠把temp值30 覆蓋到L.r[8] = 30. 這樣才實現(xiàn)了30與60的交換;
        s = j;
    }
    
    //⑦ 將L->r[s] = temp. 其實就是把L.r[8] = L.r[4] 進行交換;
    L->r[s] = temp;
}


//10.堆排序--對順序表進行堆排序
void HeapSort(SqList *L){
    int i;
   
    //1.將現(xiàn)在待排序的序列構(gòu)建成一個大頂堆;
    //將L構(gòu)建成一個大頂堆;
    //i為什么是從length/2.因為在對大頂堆的調(diào)整其實是對非葉子的根結(jié)點調(diào)整.
    for(i=L->length/2; i>0;i--){
        HeapAjust(L, i, L->length);
    }
    
    
    //2.逐步將每個最大的值根結(jié)點與末尾元素進行交換,并且再調(diào)整成大頂堆
    for(i = L->length; i > 1; i--){
        
        //① 將堆頂記錄與當(dāng)前未經(jīng)排序子序列的最后一個記錄進行交換;
        swap(L, 1, i);
        //② 將L->r[1...i-1]重新調(diào)整成大頂堆;
        HeapAjust(L, 1, i-1);
    }
}
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
  • 序言:七十年代末措嵌,一起剝皮案震驚了整個濱河市,隨后出現(xiàn)的幾起案子芦缰,更是在濱河造成了極大的恐慌企巢,老刑警劉巖,帶你破解...
    沈念sama閱讀 222,681評論 6 517
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件让蕾,死亡現(xiàn)場離奇詭異浪规,居然都是意外死亡,警方通過查閱死者的電腦和手機探孝,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 95,205評論 3 399
  • 文/潘曉璐 我一進店門笋婿,熙熙樓的掌柜王于貴愁眉苦臉地迎上來,“玉大人再姑,你說我怎么就攤上這事萌抵。” “怎么了元镀?”我有些...
    開封第一講書人閱讀 169,421評論 0 362
  • 文/不壞的土叔 我叫張陵绍填,是天一觀的道長。 經(jīng)常有香客問我栖疑,道長讨永,這世上最難降的妖魔是什么? 我笑而不...
    開封第一講書人閱讀 60,114評論 1 300
  • 正文 為了忘掉前任遇革,我火速辦了婚禮卿闹,結(jié)果婚禮上揭糕,老公的妹妹穿的比我還像新娘。我一直安慰自己锻霎,他們只是感情好著角,可當(dāng)我...
    茶點故事閱讀 69,116評論 6 398
  • 文/花漫 我一把揭開白布。 她就那樣靜靜地躺著旋恼,像睡著了一般吏口。 火紅的嫁衣襯著肌膚如雪。 梳的紋絲不亂的頭發(fā)上冰更,一...
    開封第一講書人閱讀 52,713評論 1 312
  • 那天产徊,我揣著相機與錄音,去河邊找鬼蜀细。 笑死舟铜,一個胖子當(dāng)著我的面吹牛,可吹牛的內(nèi)容都是我干的奠衔。 我是一名探鬼主播谆刨,決...
    沈念sama閱讀 41,170評論 3 422
  • 文/蒼蘭香墨 我猛地睜開眼,長吁一口氣:“原來是場噩夢啊……” “哼归斤!你這毒婦竟也來了痴荐?” 一聲冷哼從身側(cè)響起,我...
    開封第一講書人閱讀 40,116評論 0 277
  • 序言:老撾萬榮一對情侶失蹤官册,失蹤者是張志新(化名)和其女友劉穎生兆,沒想到半個月后,有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體膝宁,經(jīng)...
    沈念sama閱讀 46,651評論 1 320
  • 正文 獨居荒郊野嶺守林人離奇死亡鸦难,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點故事閱讀 38,714評論 3 342
  • 正文 我和宋清朗相戀三年,在試婚紗的時候發(fā)現(xiàn)自己被綠了员淫。 大學(xué)時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片合蔽。...
    茶點故事閱讀 40,865評論 1 353
  • 序言:一個原本活蹦亂跳的男人離奇死亡,死狀恐怖介返,靈堂內(nèi)的尸體忽然破棺而出拴事,到底是詐尸還是另有隱情,我是刑警寧澤圣蝎,帶...
    沈念sama閱讀 36,527評論 5 351
  • 正文 年R本政府宣布刃宵,位于F島的核電站,受9級特大地震影響徘公,放射性物質(zhì)發(fā)生泄漏牲证。R本人自食惡果不足惜,卻給世界環(huán)境...
    茶點故事閱讀 42,211評論 3 336
  • 文/蒙蒙 一关面、第九天 我趴在偏房一處隱蔽的房頂上張望坦袍。 院中可真熱鬧十厢,春花似錦、人聲如沸捂齐。這莊子的主人今日做“春日...
    開封第一講書人閱讀 32,699評論 0 25
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽奠宜。三九已至筛武,卻和暖如春,著一層夾襖步出監(jiān)牢的瞬間挎塌,已是汗流浹背。 一陣腳步聲響...
    開封第一講書人閱讀 33,814評論 1 274
  • 我被黑心中介騙來泰國打工内边, 沒想到剛下飛機就差點兒被人妖公主榨干…… 1. 我叫王不留榴都,地道東北人。 一個月前我還...
    沈念sama閱讀 49,299評論 3 379
  • 正文 我出身青樓漠其,卻偏偏與公主長得像嘴高,于是被迫代替她去往敵國和親。 傳聞我的和親對象是個殘疾皇子和屎,可洞房花燭夜當(dāng)晚...
    茶點故事閱讀 45,870評論 2 361