排序算法淺析

1.選擇排序
基本思想:
  • 選擇排序(Selection sort)是一種簡(jiǎn)單直觀(guān)的排序算法衔蹲。它的工作原理如下:首先在未排序序列中找到最小元素,存放到排序序列的起始位置;然后,再?gòu)氖S辔磁判蛟刂欣^續(xù)尋找最小元 素,然后放到排序序列末尾便贵。以此類(lèi)推,直到所有元素均排序完畢。
實(shí)現(xiàn)步驟
  • 第一趟排序在所有待排序的n個(gè)記錄中選出關(guān)鍵字最小的記錄,將它與數(shù)據(jù)表中的第一個(gè)記錄交換位置,使關(guān)鍵字最小的記錄處于數(shù)據(jù)表的最前端;
  • 第二趟在剩下的n-1個(gè)記錄中再選出關(guān)鍵字最 小的記錄,將其與數(shù)據(jù)表中的第二個(gè)記錄交換位置,使關(guān)鍵字次小的記錄處于數(shù)據(jù)表的第二個(gè)位置;
  • 重復(fù)這樣的操作,依次選出數(shù)據(jù)表中關(guān)鍵字第三小、第四小...的元素,將它們分別換到數(shù)據(jù)表的第三佳遂、第四...個(gè)位置上寥袭。
  • 排序共進(jìn)行n-1趟,最終可實(shí)現(xiàn)數(shù)據(jù)表的升序排列路捧。
示例:
    // 已知一個(gè)無(wú)序的數(shù)組,要求對(duì)數(shù)組進(jìn)行排序
    int nums[8] = {99, 12, 88, 34, 5, 44, 12, 100};
    int length = sizeof(nums) / sizeof(nums[0]);
    for (int i = 0; i < length; i++) {
        printf("nums[%i] = %i\n", i, nums[i]);
    }
    
    for (int i = 0; i < length - 1; i++) {
        for (int j = i+1; j < length; j++) {
//            printf("*");
//            printf("i = %i, j = %i\n", i, j);
            if (nums[i] > nums[j]) {
                int temp = nums[i];
                nums[i] = nums[j];
                nums[j] = temp;
            }
        }
    }
    
    printf("-------排序結(jié)束-------\n");
    for (int i = 0; i < length; i++) {
        printf("nums[%i] = %i\n", i, nums[i]);
    }
2.冒泡排序
基本思想
  • 冒泡排序(Bubble Sort,臺(tái)灣譯為:泡沫排序或氣泡排序)是一種簡(jiǎn)單的排序算法传黄。它重復(fù) 地走訪(fǎng)過(guò)要排序的數(shù)列,一次比較兩個(gè)元素,如果他們的順序錯(cuò)誤就把他們交換過(guò)來(lái)杰扫。走訪(fǎng)數(shù)列的工作是重復(fù)地進(jìn)行直到?jīng)]有再需要交換,也就是說(shuō)該數(shù)列已經(jīng)排序完成。這個(gè)算法的名字由來(lái) 是因?yàn)樵叫〉脑貢?huì)經(jīng)由交換慢慢“浮”到數(shù)列的頂端膘掰。

  • 冒泡排序 分為: 大數(shù)下沉 小數(shù)上浮

實(shí)現(xiàn)步驟
  • 1)比較相鄰的元素章姓。如果第一個(gè)比第二個(gè)大,就交換他們兩個(gè)。
  • 2)對(duì)每一對(duì)相鄰元素作同樣的工作,從開(kāi)始第一對(duì)到結(jié)尾的最后一對(duì)识埋。在這一點(diǎn),最后的元素應(yīng) 該會(huì)是最大的數(shù)凡伊。
  • 3)針對(duì)所有的元素重復(fù)以上的步驟,除了最后一個(gè)。
  • 4)持續(xù)每次對(duì)越來(lái)越少的元素重復(fù)上面的步驟,直到?jīng)]有任何一對(duì)數(shù)字需要比較
示例:
 int nums[6] = {99, 12, 88, 34, 5, 7};
    int length = sizeof(nums) / sizeof(nums[0]);
    for (int i = 0; i < length; i++) {
        printf("nums[%i] = %i\n", i, nums[i]);
    }
    for (int i = 0; i < length - 1; i++) {
        for (int j = 0; j < length - 1 - i; j++) {
            printf("*");
            printf("%i == %i\n", j, j+1);
            if (nums[j] > nums[j + 1]) {
                int temp = nums[j];
                nums[j] = nums[j + 1];
                nums[j + 1] = temp;
            }
        }
    }
    printf("------排序結(jié)束----\n");
    for (int i = 0; i < length; i++) {
        printf("nums[%i] = %i\n", i, nums[i]);
    }
3.折半查找
基本思想
  • 在有序表中,取中間元素作為比較對(duì)象,若給定值與中間元素的要查找的數(shù)相等,則查找成功;若給定值小于中間元素的要查找的數(shù),則在中間元素的左半?yún)^(qū)繼續(xù)查找;
  • 若給定值大于中間元素的要查找的數(shù),則在中間元素的右半?yún)^(qū)繼續(xù)查找窒舟。不斷重復(fù)上述查找過(guò)程,直到查找成功,或所查找的區(qū)域無(wú)數(shù)據(jù)元素,查找失敗
實(shí)現(xiàn)步驟
  • 在有序表中,取中間元素作為比較對(duì)象,若給定值與中間元素的要查找的數(shù)相等,則查找成功;
  • 若給定值小于中間元素的要查找的數(shù),則在中間元素的左半?yún)^(qū)繼續(xù)查找;
  • 若給定值大于中間元素的要查找的數(shù),則在中間元素的右半?yún)^(qū)繼續(xù)查找系忙。不斷重復(fù)上述查找過(guò) 程,直到查找成功,或所查找的區(qū)域無(wú)數(shù)據(jù)元素,查找失敗。

示例:

#include <stdio.h>
#include <time.h>

int findKey(int nums[], int key, int length);
int findKey2(int nums[], int length, int key);
int findKey3(int nums[], int length, int key);

int main(int argc, const char * argv[]) {
    // 現(xiàn)在已知一個(gè)有序的數(shù)組, 和一個(gè)key. 要求從數(shù)組中找到key對(duì)應(yīng)的索引的位置
    // 對(duì)該方法進(jìn)行封裝, 要求找到就返回對(duì)應(yīng)的索引, 找不到就返回-1
    int nums[500000] = {1, 3, 5, 7, 9, [499999] = 99};
    int key = 99;
    int length = sizeof(nums) / sizeof(nums[0]);
    
    /*
     // 消耗了多少1181毫秒
    clock_t startTime = clock();
    int index =  findKey(nums, key, length);
    clock_t endTime = clock();
    printf("消耗了多少%lu毫秒\n", endTime - startTime);
    printf("index = %i\n", index);
     */
    
    // 消耗了多少1毫秒
    clock_t startTime = clock();
//    int index = findKey2(nums, length, key);
    // 消耗了多少2毫秒
    int index = findKey3(nums, length, key);
    clock_t endTime = clock();
    printf("消耗了多少%lu毫秒\n", endTime - startTime);
    printf("index = %i\n", index);
    
    return 0;
}

int findKey3(int nums[], int length, int key)
{
    int min, max, mid;
    min = 0;
    max = length - 1;
    
    // 只要還在我們的范圍內(nèi)就需要查找
    while (min <= max) {
        // 計(jì)算中間值
        mid = (min  + max) / 2;
        if (key > nums[mid]) {
            min = mid + 1;
        }else if (key < nums[mid])
        {
            max = mid - 1;
        }else
        {
            return mid;
        }
        
    }
    return -1;
}

int findKey2(int nums[], int length, int key)
{
    int min, max, mid;
    min = 0;
    max = length - 1;
    mid = (min + max) / 2;
    
    while (key != nums[mid]) {
        // 判斷如果要找的值, 大于了取出的值, 那么min要改變
        if (key > nums[mid]) {
            min = mid + 1;
        // 判斷如果要找的值, 小雨了取出的值, 那么max要改變
        }else if (key < nums[mid])
        {
            max = mid - 1;
        }
        
        // 超出范圍, 數(shù)組中沒(méi)有需要查找的值
        if (min > max) {
            return -1;
        }
        // 每次改變完min和max都需要重新計(jì)算mid
        mid = (min + max) / 2;
    }
//    printf("aaaaaa\n");
    
    return mid;

}

int findKey(int nums[], int key, int length)
{
    for (int i = 0; i < length; i++) {
        if (nums[i] == key) {
//            printf("%i\n", i);
            return i;
        }
    }
    return -1;
}
附:排序和冒泡方法封裝
// 冒泡排序
void bubbleSort(int nums[], int length)
{
    for (int i = 0; i < length - 1; i++) {
        for (int j = 0; j < length - 1 - i; j++) {
            if (nums[j] > nums[j + 1]) {
                swap(nums, j, j+1);
            }
        }
    }
}

// 選擇排序
void selectSort(int nums[], int length)
{
    for (int i = 0; i < length - 1; i++) {
        for (int j = i+1; j < length; j++) {
            if (nums[i] > nums[j]) {
                swap(nums, i, j);
            }
        }
    }

}
// 交換兩個(gè)數(shù)的值
void swap(int nums[], int i, int j)
{
    int temp = nums[i];
    nums[i] = nums[j];
    nums[j] = temp;
}
最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
  • 序言:七十年代末惠豺,一起剝皮案震驚了整個(gè)濱河市银还,隨后出現(xiàn)的幾起案子风宁,更是在濱河造成了極大的恐慌,老刑警劉巖蛹疯,帶你破解...
    沈念sama閱讀 218,451評(píng)論 6 506
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件戒财,死亡現(xiàn)場(chǎng)離奇詭異,居然都是意外死亡捺弦,警方通過(guò)查閱死者的電腦和手機(jī)饮寞,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 93,172評(píng)論 3 394
  • 文/潘曉璐 我一進(jìn)店門(mén),熙熙樓的掌柜王于貴愁眉苦臉地迎上來(lái)列吼,“玉大人骂际,你說(shuō)我怎么就攤上這事「曰叮” “怎么了歉铝?”我有些...
    開(kāi)封第一講書(shū)人閱讀 164,782評(píng)論 0 354
  • 文/不壞的土叔 我叫張陵,是天一觀(guān)的道長(zhǎng)凑耻。 經(jīng)常有香客問(wèn)我太示,道長(zhǎng),這世上最難降的妖魔是什么香浩? 我笑而不...
    開(kāi)封第一講書(shū)人閱讀 58,709評(píng)論 1 294
  • 正文 為了忘掉前任类缤,我火速辦了婚禮,結(jié)果婚禮上邻吭,老公的妹妹穿的比我還像新娘餐弱。我一直安慰自己,他們只是感情好囱晴,可當(dāng)我...
    茶點(diǎn)故事閱讀 67,733評(píng)論 6 392
  • 文/花漫 我一把揭開(kāi)白布膏蚓。 她就那樣靜靜地躺著,像睡著了一般畸写。 火紅的嫁衣襯著肌膚如雪驮瞧。 梳的紋絲不亂的頭發(fā)上,一...
    開(kāi)封第一講書(shū)人閱讀 51,578評(píng)論 1 305
  • 那天枯芬,我揣著相機(jī)與錄音论笔,去河邊找鬼。 笑死千所,一個(gè)胖子當(dāng)著我的面吹牛狂魔,可吹牛的內(nèi)容都是我干的。 我是一名探鬼主播淫痰,決...
    沈念sama閱讀 40,320評(píng)論 3 418
  • 文/蒼蘭香墨 我猛地睜開(kāi)眼最楷,長(zhǎng)吁一口氣:“原來(lái)是場(chǎng)噩夢(mèng)啊……” “哼!你這毒婦竟也來(lái)了?” 一聲冷哼從身側(cè)響起管嬉,我...
    開(kāi)封第一講書(shū)人閱讀 39,241評(píng)論 0 276
  • 序言:老撾萬(wàn)榮一對(duì)情侶失蹤,失蹤者是張志新(化名)和其女友劉穎朗鸠,沒(méi)想到半個(gè)月后蚯撩,有當(dāng)?shù)厝嗽跇?shù)林里發(fā)現(xiàn)了一具尸體,經(jīng)...
    沈念sama閱讀 45,686評(píng)論 1 314
  • 正文 獨(dú)居荒郊野嶺守林人離奇死亡烛占,尸身上長(zhǎng)有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 37,878評(píng)論 3 336
  • 正文 我和宋清朗相戀三年胎挎,在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片忆家。...
    茶點(diǎn)故事閱讀 39,992評(píng)論 1 348
  • 序言:一個(gè)原本活蹦亂跳的男人離奇死亡犹菇,死狀恐怖,靈堂內(nèi)的尸體忽然破棺而出芽卿,到底是詐尸還是另有隱情揭芍,我是刑警寧澤,帶...
    沈念sama閱讀 35,715評(píng)論 5 346
  • 正文 年R本政府宣布卸例,位于F島的核電站称杨,受9級(jí)特大地震影響,放射性物質(zhì)發(fā)生泄漏筷转。R本人自食惡果不足惜姑原,卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 41,336評(píng)論 3 330
  • 文/蒙蒙 一、第九天 我趴在偏房一處隱蔽的房頂上張望呜舒。 院中可真熱鬧锭汛,春花似錦、人聲如沸袭蝗。這莊子的主人今日做“春日...
    開(kāi)封第一講書(shū)人閱讀 31,912評(píng)論 0 22
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽(yáng)到腥。三九已至眨八,卻和暖如春,著一層夾襖步出監(jiān)牢的瞬間左电,已是汗流浹背廉侧。 一陣腳步聲響...
    開(kāi)封第一講書(shū)人閱讀 33,040評(píng)論 1 270
  • 我被黑心中介騙來(lái)泰國(guó)打工, 沒(méi)想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留篓足,地道東北人段誊。 一個(gè)月前我還...
    沈念sama閱讀 48,173評(píng)論 3 370
  • 正文 我出身青樓,卻偏偏與公主長(zhǎng)得像栈拖,于是被迫代替她去往敵國(guó)和親连舍。 傳聞我的和親對(duì)象是個(gè)殘疾皇子,可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 44,947評(píng)論 2 355

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