排序算法講解及代碼實(shí)現(xiàn)

共用方法

/**
 交換元素位置

 @param element1 元素指針
 @param element2 元素指針
 */
void swapElement(int *element1 , int *element2)//交換元素位置
{
    int temp = *element1;
    *element1 = *element2;
    *element2 = temp;
}
/**
 打印數(shù)組元素

 @param array 排序后的數(shù)組指針
 @param count 數(shù)組長(zhǎng)度
 */
void printArray(int *array, int count){

    for (int i = 0; i<count; i++) {
        
        NSLog(@"第%d個(gè)元素為 : %d", i, *(array + i));
    }
}


1. 插入排序

思路:從數(shù)組中選中目標(biāo)元素(一般從第二個(gè)元素開(kāi)始)敛劝,依次和前面的數(shù)對(duì)比,邊比對(duì)邊移動(dòng)數(shù)據(jù)元素位置绊序,當(dāng)找到合適的位置硕舆,插入目標(biāo)元素≈韫可以想象成整理麻將牌的步驟抚官。

/**
 算法     最優(yōu)復(fù)雜度   最差復(fù)雜度   平均復(fù)雜度   穩(wěn)定性    輔助存儲(chǔ)
 插入排序    O(n)       O(n2)       O(n2)    穩(wěn)定    O(1)

 @param array 待排序數(shù)組
 @param count 數(shù)組長(zhǎng)度
 @return 排序后的數(shù)組
 */
int * insertSort(int array[], int count){

    for (int i = 1; i<count; i++) {
        
        int j;
        int target = array[i];//目標(biāo)元素
        
        for (j = i; j>0 && target<array[j-1]; j--) {//結(jié)束條件
            
            array[j] = array[j-1];//比對(duì)不合適移動(dòng)元素位置
        }
        array[j] = target;//插入目標(biāo)元素
        
    }
    return array;
}

2. shell排序

思路:shell排序是對(duì)插入排序的優(yōu)化,首先對(duì)數(shù)組進(jìn)行跳躍式分組阶捆,一般選擇數(shù)組長(zhǎng)度除以2(即:count/2)得到跳躍的步數(shù)凌节,對(duì)生成的子數(shù)組進(jìn)行排序。每次循環(huán)洒试,步數(shù)/2,結(jié)束條件為步數(shù)<=1;此時(shí)的數(shù)組已經(jīng)大致有序倍奢,最后使用插入排序。

/**
 算法     最優(yōu)復(fù)雜度   最差復(fù)雜度   平均復(fù)雜度   穩(wěn)定性     輔助存儲(chǔ)
 shell排序O(n^1.3)   O(n^1.3)    O(n^1.3)    不穩(wěn)定     O(1)

 @param array 待排序數(shù)組
 @param count 數(shù)組長(zhǎng)度
 @return 排序后的數(shù)組
 */
int * shellSort(int array[], int count){

    int step = count / 2;
    while (step>=1) { //判定結(jié)束條件
        
        for (int i = 0; i<step; i++) {//判定走多少趟
            
            int j = 1;
            while (i + step * j < count) {//子數(shù)組的結(jié)束條件
                
                if (array[i + step * (j-1)]>array[i + step * j]) {//交換子數(shù)組位置
                    
                   swapElement(&array[i + step * (j-1)], &array[i + step * j]);
                }
                j++;
            }
        }
        step = step / 2;
    }
    return insertSort(array, count);//調(diào)用插入排序
}

3. 選擇排序

思路:假定第一個(gè)元素為最小元素垒棋,同時(shí)作為目標(biāo)元素卒煞,用目標(biāo)元素和后面的元素進(jìn)行對(duì)比,如果大于捕犬,則記錄索引跷坝,同時(shí)修改目標(biāo)元素酵镜,遍歷結(jié)束也就可以拿到最小值的索引,之后和起始位置的進(jìn)行交換柴钻。for循環(huán)控制流淮韭,控制跳過(guò)排序過(guò)得元素。

/**
 算法     最優(yōu)復(fù)雜度   最差復(fù)雜度   平均復(fù)雜度   穩(wěn)定性     輔助存儲(chǔ)
 選擇排序    O(n2)      O(n2)       O(n2)       不穩(wěn)定     O(1)

 @param array 待排序數(shù)組
 @param count 數(shù)組長(zhǎng)度
 @return 排序后的數(shù)組
 */
int * selectSort(int array[], int count){
    
    for (int i = 0; i < count; i++) {
        
        int index = i;
        
        for (int j = i; j < count-1; j++) {
            
            if (array[j+1]<array[index]) {//設(shè)置哨兵贴届,記錄每次循環(huán)最小的靠粪。思路:默認(rèn)第一個(gè)值為哨兵和后面的數(shù)以此比較,如果小于哨兵毫蚓,記錄索引占键,修改哨兵始終是最小的數(shù),和后邊的比對(duì)元潘。最后獲取到就是此次遍歷的最小值畔乙,和數(shù)組中的遍歷起始位置交換,從下一個(gè)位置接著下一次循環(huán)翩概,直到跳出循環(huán)牲距,數(shù)組排序結(jié)束,從小到大排序钥庇。
                index = j+1;//記錄索引
            }
        }
       swapElement(&array[i], &array[index]);
    }
    return array;
}

4. 堆排序

思路:堆排序是選擇排序的改進(jìn)算法牍鞠,不再是一步一步選擇,而是根據(jù)二叉樹(shù)的特性评姨,每次篩選子二叉樹(shù)难述。篩選完成時(shí),將根元素和最后一個(gè)元素交換吐句。之后迭代篩選胁后,每次元素個(gè)數(shù)減一,直到剩余元素為一時(shí)蕴侧,排序完成择同。

/**
 算法     最優(yōu)復(fù)雜度   最差復(fù)雜度   平均復(fù)雜度   穩(wěn)定性     輔助存儲(chǔ)
 堆排序   O(nlogn)   O(nlogn)    O(nlogn)    不穩(wěn)定     O(1)
 
 @param array 待排序數(shù)組
 @param count 數(shù)組長(zhǎng)度
 @return 排序后的數(shù)組
 */
int * heapSort(int array[], int count){
    
    for (int i = count / 2; i > 0; i--) {// 構(gòu)造大頂堆
        
        heapAdjust(array, i, count);
    }
    
    for (int i = count - 1; i >= 1; i--) {
        
        swapElement(&array[i], &array[0]); // 交換根結(jié)點(diǎn)與最末節(jié)點(diǎn)
        
        heapAdjust(array, 0, i-1);// 剩余的n-1個(gè)元素再次建立大頂堆
    }
    return array;
}

void heapAdjust(int array[], int i, int count)
{
    int j, temp;
    temp = array[i];
    j = 2 * i;
    while(j <= count-1) {
        if (j < count && array[j+1] > array[j]) j++; // 找出較大的子節(jié)點(diǎn)
        
        if (array[j] <= temp) break; // 如果較大的子節(jié)點(diǎn)比父節(jié)點(diǎn)小, 直接返回
        
        array[i] = array[j]; // 設(shè)置父節(jié)點(diǎn)為較大子節(jié)點(diǎn)
        i = j; // 記錄調(diào)整后父節(jié)點(diǎn)的位置
        j *= 2; // 調(diào)整需要遍歷的子節(jié)點(diǎn)
    }
    array[i] = temp;
}

5. 冒泡排序

思路:每次比較相鄰的兩個(gè)數(shù),如果前一個(gè)數(shù)比后一個(gè)數(shù)大净宵,交換兩個(gè)數(shù)的位置,一趟遍歷完成裹纳,大數(shù)已下沉到末尾择葡,下次遍歷只需要遍歷到大數(shù)前一位即可,跳出循環(huán)時(shí)剃氧,已經(jīng)是有序數(shù)組敏储,從小到大。同理也可以從大到小朋鞍。

/**
 算法     最優(yōu)復(fù)雜度   最差復(fù)雜度   平均復(fù)雜度   穩(wěn)定性     輔助存儲(chǔ)
 冒泡排序  O(n)        O(n2)       O(n2)       穩(wěn)定     O(1)

 @param array 待排序數(shù)組
 @param count 數(shù)組長(zhǎng)度
 @return 排序后的數(shù)組
 */
int * bubblingSort(int array[], int count){
    
    for (int i = 0; i < count; i++) {//控制多少趟
        
        for (int j = 0; j<count-i-1; j++) {//控制交換次數(shù)
            
            if (array[j]>array[j+1]) {//比較相鄰兩個(gè)元素
                swapElement(&array[j+1], &array[j]);//交換元素
            }
        }
    }
    return array;
}

6. 快速排序

思路:快速排序是冒泡排序的改進(jìn)算法已添,采用遞歸分治思想妥箕。設(shè)置一個(gè)目標(biāo)元素,建立左右兩個(gè)索引元素更舞,如果目標(biāo)元素是第一個(gè)元素畦幢,從右邊查找,同時(shí)遞減右索引缆蝉,直到遇到比目標(biāo)元素小的值宇葱,和目標(biāo)元素交換,接著和左邊的元素比較刊头,直到遇到大于目標(biāo)元素黍瞧,和目標(biāo)元素交換。也就是目標(biāo)元素依次在左右來(lái)回交換原杂,直到左右索引相同印颤。之后遞歸調(diào)用,設(shè)置一個(gè)邊界條件穿肄,即可完成排序年局。

/**
 算法     最優(yōu)復(fù)雜度   最差復(fù)雜度   平均復(fù)雜度   穩(wěn)定性
 快速排序  O(n)        O(n2)      O(logn)     不穩(wěn)定
 
 @param array 待排序數(shù)組
 @param left  左邊界
 @param right 右邊界
 @return 排序后的數(shù)組
 */
int * quickSort(int array[], int left, int right){

    if (left>=right) {//遞歸結(jié)束條件
        return NULL;
    }
    int i = left;
    int j = right;
    int key = array[left];
    
    while (i<j) {//單次排序結(jié)束條件
        
        while (i<j && array[j] >= key) {//小數(shù)向左交換條件
            j--;
        }
        swapElement(&array[i], &array[j]);//交換元素
        while (i<j && array[i] <= key) {//大數(shù)向右交換條件
            i++;
        }
        swapElement(&array[i], &array[j]);//交換元素
    }
    quickSort(array, left, i - 1);//遞歸左分支
    quickSort(array, i+1 , right);//遞歸右分支
    return array;
}

demo下載地址

我的上一篇炫酷的懸停交互視圖

最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
  • 序言:七十年代末,一起剝皮案震驚了整個(gè)濱河市被碗,隨后出現(xiàn)的幾起案子某宪,更是在濱河造成了極大的恐慌,老刑警劉巖锐朴,帶你破解...
    沈念sama閱讀 223,126評(píng)論 6 520
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件兴喂,死亡現(xiàn)場(chǎng)離奇詭異,居然都是意外死亡焚志,警方通過(guò)查閱死者的電腦和手機(jī)衣迷,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 95,421評(píng)論 3 400
  • 文/潘曉璐 我一進(jìn)店門(mén),熙熙樓的掌柜王于貴愁眉苦臉地迎上來(lái)酱酬,“玉大人壶谒,你說(shuō)我怎么就攤上這事∩殴粒” “怎么了汗菜?”我有些...
    開(kāi)封第一講書(shū)人閱讀 169,941評(píng)論 0 366
  • 文/不壞的土叔 我叫張陵,是天一觀的道長(zhǎng)挑社。 經(jīng)常有香客問(wèn)我陨界,道長(zhǎng),這世上最難降的妖魔是什么痛阻? 我笑而不...
    開(kāi)封第一講書(shū)人閱讀 60,294評(píng)論 1 300
  • 正文 為了忘掉前任菌瘪,我火速辦了婚禮,結(jié)果婚禮上阱当,老公的妹妹穿的比我還像新娘俏扩。我一直安慰自己糜工,他們只是感情好,可當(dāng)我...
    茶點(diǎn)故事閱讀 69,295評(píng)論 6 398
  • 文/花漫 我一把揭開(kāi)白布录淡。 她就那樣靜靜地躺著捌木,像睡著了一般。 火紅的嫁衣襯著肌膚如雪赁咙。 梳的紋絲不亂的頭發(fā)上钮莲,一...
    開(kāi)封第一講書(shū)人閱讀 52,874評(píng)論 1 314
  • 那天,我揣著相機(jī)與錄音彼水,去河邊找鬼崔拥。 笑死,一個(gè)胖子當(dāng)著我的面吹牛凤覆,可吹牛的內(nèi)容都是我干的链瓦。 我是一名探鬼主播,決...
    沈念sama閱讀 41,285評(píng)論 3 424
  • 文/蒼蘭香墨 我猛地睜開(kāi)眼盯桦,長(zhǎng)吁一口氣:“原來(lái)是場(chǎng)噩夢(mèng)啊……” “哼慈俯!你這毒婦竟也來(lái)了?” 一聲冷哼從身側(cè)響起拥峦,我...
    開(kāi)封第一講書(shū)人閱讀 40,249評(píng)論 0 277
  • 序言:老撾萬(wàn)榮一對(duì)情侶失蹤贴膘,失蹤者是張志新(化名)和其女友劉穎,沒(méi)想到半個(gè)月后略号,有當(dāng)?shù)厝嗽跇?shù)林里發(fā)現(xiàn)了一具尸體刑峡,經(jīng)...
    沈念sama閱讀 46,760評(píng)論 1 321
  • 正文 獨(dú)居荒郊野嶺守林人離奇死亡,尸身上長(zhǎng)有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 38,840評(píng)論 3 343
  • 正文 我和宋清朗相戀三年玄柠,在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了突梦。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片。...
    茶點(diǎn)故事閱讀 40,973評(píng)論 1 354
  • 序言:一個(gè)原本活蹦亂跳的男人離奇死亡羽利,死狀恐怖宫患,靈堂內(nèi)的尸體忽然破棺而出,到底是詐尸還是另有隱情这弧,我是刑警寧澤娃闲,帶...
    沈念sama閱讀 36,631評(píng)論 5 351
  • 正文 年R本政府宣布,位于F島的核電站匾浪,受9級(jí)特大地震影響畜吊,放射性物質(zhì)發(fā)生泄漏。R本人自食惡果不足惜户矢,卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 42,315評(píng)論 3 336
  • 文/蒙蒙 一、第九天 我趴在偏房一處隱蔽的房頂上張望殉疼。 院中可真熱鬧梯浪,春花似錦捌年、人聲如沸。這莊子的主人今日做“春日...
    開(kāi)封第一講書(shū)人閱讀 32,797評(píng)論 0 25
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽(yáng)。三九已至虏劲,卻和暖如春托酸,著一層夾襖步出監(jiān)牢的瞬間,已是汗流浹背柒巫。 一陣腳步聲響...
    開(kāi)封第一講書(shū)人閱讀 33,926評(píng)論 1 275
  • 我被黑心中介騙來(lái)泰國(guó)打工励堡, 沒(méi)想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留,地道東北人堡掏。 一個(gè)月前我還...
    沈念sama閱讀 49,431評(píng)論 3 379
  • 正文 我出身青樓应结,卻偏偏與公主長(zhǎng)得像,于是被迫代替她去往敵國(guó)和親泉唁。 傳聞我的和親對(duì)象是個(gè)殘疾皇子鹅龄,可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 45,982評(píng)論 2 361

推薦閱讀更多精彩內(nèi)容

  • 該系列文章主要是記錄下自己暑假這段時(shí)間的學(xué)習(xí)筆記,暑期也在實(shí)習(xí)亭畜,抽空學(xué)了很多扮休,每個(gè)方面的知識(shí)我都會(huì)另起一篇博客去記...
    Yanci516閱讀 12,231評(píng)論 6 19
  • 排序的基本概念 在計(jì)算機(jī)程序開(kāi)發(fā)過(guò)程中,經(jīng)常需要一組數(shù)據(jù)元素(或記錄)按某個(gè)關(guān)鍵字進(jìn)行排序拴鸵,排序完成的序列可用于快...
    Jack921閱讀 1,438評(píng)論 1 4
  • 總認(rèn)為以德報(bào)怨是一種美德宝踪,不管別人怎么樣侨糟,我要讓自己?jiǎn)栃臒o(wú)愧。 如果對(duì)每一個(gè)對(duì)你好的或者對(duì)你不好的人都是一...
    文佳newway閱讀 339評(píng)論 0 0
  • 什么是 Docker瘩燥?翻譯一下意思是:碼頭工人秕重,搬東西的。那計(jì)算機(jī)世界里 Docker 又代表什么意思呢厉膀?看下官方...
    野塵lxw閱讀 434評(píng)論 0 2