各種排序算法整理

本文主要對(duì)七種排序算法做宏觀上的總結(jié),沒(méi)有死扣代碼細(xì)節(jié)阻荒,意在充分理解各種排序算法的思想挠锥。

排序算法關(guān)系示意圖

I、 上帝視角看排序

排序算法常出現(xiàn)在各種面試題中侨赡,對(duì)于算法時(shí)間空間復(fù)雜度的分析蓖租,穩(wěn)定性要求等都需要靈活掌握。

1.1 冒泡排序

基本思想:兩兩比較相鄰的關(guān)鍵字羊壹,如果反序則交換蓖宦。

時(shí)間復(fù)雜度:最好是O(n),最壞的情況是O(n^2)稠茂。

改進(jìn)思路
1、設(shè)置標(biāo)志位情妖,明顯如果有一趟沒(méi)有發(fā)生交換(flag=false)睬关,說(shuō)明已經(jīng)有序;
2毡证、記錄下一輪下來(lái)標(biāo)記的最后位置电爹,下次從頭部遍歷到這個(gè)位置就OK。

1.2 簡(jiǎn)單選擇排序

基本思想:通過(guò)n-i次關(guān)鍵字之間的比較料睛,從n-i+1個(gè)元素中選擇關(guān)鍵字最小的元素丐箩,并和第i(1<=i<=n)個(gè)元素交換。

時(shí)間復(fù)雜度:為O(n^2)恤煞,但簡(jiǎn)單選擇排序的性能略?xún)?yōu)于冒泡排序屎勘。

1.3 直接插入排序

基本思想: 將一個(gè)元素插入到已經(jīng)排好序的有序表中,從而得到一個(gè)新的居扒,元素?cái)?shù)新增1的有序表挑秉。

時(shí)間復(fù)雜度:為O(n^2),但是比冒泡排序和選擇排序的性能要更好一些苔货。

1.4 希爾排序

基本思想:先將整個(gè)待排序元素序列分割成若干個(gè)序列(由相隔某個(gè)“增量”的元素組成)犀概,分別進(jìn)行直接插入排序,然后依次縮減增量在進(jìn)行排序夜惭,待整個(gè)序列中元素基本有序(增量足夠幸鲈睢)時(shí),在對(duì)全體元素進(jìn)行一次直接插入排序(增量為1)诈茧。

時(shí)間復(fù)雜度:其時(shí)間復(fù)雜度為O(n^1.5)产喉。

1.5 歸并排序

基本思想:假設(shè)初始序列含有n個(gè)元素,則可以看成n個(gè)有序的子序列,每個(gè)子序列長(zhǎng)度為1曾沈,然后兩兩歸并这嚣,得到(不小于n/2的最小整數(shù))個(gè)長(zhǎng)度為2或1的有序子序列,然后在兩兩歸并塞俱,...如此重復(fù)姐帚,直到得到一個(gè)長(zhǎng)度為n的有序序列為止。

時(shí)間復(fù)雜度:時(shí)間復(fù)雜度為O(nlgn)障涯,空間復(fù)雜度為O(n+lgn)罐旗,如果非遞歸實(shí)現(xiàn)歸并,則避免了遞歸時(shí)深度為lgn的椢ǖ空間九秀,空間復(fù)雜度為O(n)。

1.6 堆排序

關(guān)于堆排序的詳細(xì)說(shuō)明見(jiàn)wenmingxing 堆排序初探

時(shí)間復(fù)雜度:堆排序的時(shí)間復(fù)雜度為O(nlgn)粘我。

1.7 快速排序

關(guān)于快速排序的詳細(xì)說(shuō)明見(jiàn)wenmingxing 深入理解快排

時(shí)間復(fù)雜度:快排的時(shí)間復(fù)雜度為O(nlgn)鼓蜒。

II、七種排序算法比較

排序算法比較

III征字、參考代碼

下面參考代碼中沒(méi)有堆排序和快速排序的代碼友酱,可以見(jiàn)上面的鏈接文章。

#include<iostream>
using namespace std;

void swap1(int *left, int *right)
{
    int temp = *left;
    *left = *right;
    *right = temp;
}

void swap2(int &left, int &right)
{
    int temp = left;
    left = right;
    right = left;
}

void swap3(int &left, int &right)
{
    if (&left != &right) 
    {
        left ^= right;
        right ^= left;
        left ^= right;
    }
}

/*****************************************************************/
/* 冒泡排序時(shí)間復(fù)雜度最好的情況為O(n),最壞的情況是O(n^2)
* 基本思想是:兩兩比較相鄰記錄的關(guān)鍵字,如果反序則交換 */

void BubbleSort1(int arr[], int num)
{
    int i, j;
    for (i = 0; i < num; i++)
    {
        for (j = 1; j < num - i; j++)
        {
            if (arr[j - 1] > arr[j])
                swap1(&arr[j - 1], &arr[j]);
        }
    }
}

// 改進(jìn)思路:設(shè)置標(biāo)志位柔纵,明顯如果有一趟沒(méi)有發(fā)生交換(flag = flase)缔杉,說(shuō)明排序已經(jīng)完成.
void BubbleSort2(int arr[], int num)
{
    int k = num;
    int j;
    bool flag = true;
    while (flag)
    {
        flag = false;
        for (j = 1; j < k; j++)
        {
            if (arr[j - 1] > arr[j])
            {
                swap1(&arr[j - 1], &arr[j]);
                flag = true;
            }
        }
        k--;
    }
}
//改進(jìn)思路:記錄一輪下來(lái)標(biāo)記的最后位置,下次從頭部遍歷到這個(gè)位置就Ok
void BubbleSort3(int arr[], int num)
{
    int k, j;
    int flag = num;
    while (flag > 0)
    {
        k = flag;
        flag = 0;
        for (j = 1; j < k; j++)
        {
            if (arr[j - 1] > arr[j])
            {
                swap1(&arr[j - 1], &arr[j]);
                flag = j;
            }
        }
    }
}
/*************************************************************************/

/**************************************************************************/
/*插入排序: 將一個(gè)記錄插入到已經(jīng)排好序的有序表中, 從而得到一個(gè)新的,記錄數(shù)增1的有序表
* 時(shí)間復(fù)雜度也為O(n^2), 比冒泡法和選擇排序的性能要更好一些 */

void InsertionSort(int arr[], int num)
{
    int temp;
    int i, j;
    for (i = 1; i < num; i++)
    {
        temp = arr[i];
        for (j = i; j > 0 && arr[j - 1] > temp; j--)
            arr[j] = arr[j - 1];
        arr[j] = temp;
    }
}

/****************************************************************************/

/*希爾排序:先將整個(gè)待排元素序列分割成若干子序列(由相隔某個(gè)“增量”的元素組成的)分別進(jìn)行
直接插入排序搁料,然后依次縮減增量再進(jìn)行排序或详,待整個(gè)序列中的元素基本有序(增量足夠小)時(shí)郭计,
再對(duì)全體元素進(jìn)行一次直接插入排序(增量為1)霸琴。其時(shí)間復(fù)雜度為O(n^3/2),要好于直接插入排序的O(n^2) */
void ShellSort(int *arr, int N)
{
    int i, j, increment;
    int tmp;
    for (increment = N / 2; increment > 0; increment /= 2)
    {
        for (i = increment; i < N; i++)
        {
            tmp = arr[i];
            for (j = i; j >= increment; j -= increment)
            {
                if (arr[j - increment] > tmp)
                    arr[j] = arr[j - increment];
                else
                    break;
            }
            arr[j] = tmp;
        }

    }
}

/**************************************************************************/

/* 簡(jiǎn)單選擇排序(simple selection sort) 就是通過(guò)n-i次關(guān)鍵字之間的比較,從n-i+1
* 個(gè)記錄中選擇關(guān)鍵字最小的記錄,并和第i(1<=i<=n)個(gè)記錄交換之
* 盡管與冒泡排序同為O(n^2),但簡(jiǎn)單選擇排序的性能要略?xún)?yōu)于冒泡排序 */

void SelectSort(int arr[], int num)
{
    int i, j, Mindex;
    for (i = 0; i < num; i++)
    {
        Mindex = i;
        for (j = i + 1; j < num; j++)
        {
            if (arr[j] < arr[Mindex])
                Mindex = j;
        }

        swap1(&arr[i], &arr[Mindex]);
    }
}

/********************************************************************************/
/*假設(shè)初始序列含有n個(gè)記錄,則可以看成n個(gè)有序的子序列,每個(gè)子序列的長(zhǎng)度為1,然后
* 兩兩歸并,得到(不小于n/2的最小整數(shù))個(gè)長(zhǎng)度為2或1的有序子序列,再兩兩歸并,...
* 如此重復(fù),直至得到一個(gè)長(zhǎng)度為n的有序序列為止,這種排序方法稱(chēng)為2路歸并排序
* 時(shí)間復(fù)雜度為O(nlogn),空間復(fù)雜度為O(n+logn),如果非遞歸實(shí)現(xiàn)歸并,則避免了遞歸時(shí)深度為logn的棧空間
* 空間復(fù)雜度為O(n) */


/*lpos is the start of left half, rpos is the start of right half*/
void merge(int a[], int tmp_array[], int lpos, int rpos, int rightn)
{
    int i, leftn, num_elements, tmpos;

    leftn = rpos - 1;
    tmpos = lpos;
    num_elements = rightn - lpos + 1;

    /*main loop*/
    while (lpos <= leftn && rpos <= rightn)
        if (a[lpos] <= a[rpos])
            tmp_array[tmpos++] = a[lpos++];
        else
            tmp_array[tmpos++] = a[rpos++];

    while (lpos <= leftn) /*copy rest of the first part*/
        tmp_array[tmpos++] = a[lpos++];
    while (rpos <= rightn) /*copy rest of the second part*/
        tmp_array[tmpos++] = a[rpos++];

    /*copy array back*/
    for (i = 0; i < num_elements; i++, rightn--)
        a[rightn] = tmp_array[rightn];
}


void msort(int a[], int tmp_array[], int left, int right)
{
    int center;

    if (left < right)
    {
        center = (right + left) / 2;
        msort(a, tmp_array, left, center);
        msort(a, tmp_array, center + 1, right);
        merge(a, tmp_array, left, center + 1, right);
    }
}



void merge_sort(int a[], int n)
{
    int *tmp_array;
    tmp_array = (int *)malloc(n * sizeof(int));

    if (tmp_array != NULL)
    {
        msort(a, tmp_array, 0, n - 1);
        free(tmp_array);
    }

    else
        printf("No space for tmp array!\n");
}

【參考】
[1] 《大話數(shù)據(jù)結(jié)構(gòu)》
[2] 十種排序算法總結(jié)

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
  • 序言:七十年代末昭伸,一起剝皮案震驚了整個(gè)濱河市梧乘,隨后出現(xiàn)的幾起案子,更是在濱河造成了極大的恐慌庐杨,老刑警劉巖选调,帶你破解...
    沈念sama閱讀 217,084評(píng)論 6 503
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件,死亡現(xiàn)場(chǎng)離奇詭異灵份,居然都是意外死亡仁堪,警方通過(guò)查閱死者的電腦和手機(jī),發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 92,623評(píng)論 3 392
  • 文/潘曉璐 我一進(jìn)店門(mén)填渠,熙熙樓的掌柜王于貴愁眉苦臉地迎上來(lái)弦聂,“玉大人鸟辅,你說(shuō)我怎么就攤上這事≥汉” “怎么了匪凉?”我有些...
    開(kāi)封第一講書(shū)人閱讀 163,450評(píng)論 0 353
  • 文/不壞的土叔 我叫張陵,是天一觀的道長(zhǎng)捺檬。 經(jīng)常有香客問(wèn)我再层,道長(zhǎng),這世上最難降的妖魔是什么欺冀? 我笑而不...
    開(kāi)封第一講書(shū)人閱讀 58,322評(píng)論 1 293
  • 正文 為了忘掉前任树绩,我火速辦了婚禮萨脑,結(jié)果婚禮上隐轩,老公的妹妹穿的比我還像新娘。我一直安慰自己渤早,他們只是感情好职车,可當(dāng)我...
    茶點(diǎn)故事閱讀 67,370評(píng)論 6 390
  • 文/花漫 我一把揭開(kāi)白布。 她就那樣靜靜地躺著鹊杖,像睡著了一般悴灵。 火紅的嫁衣襯著肌膚如雪。 梳的紋絲不亂的頭發(fā)上骂蓖,一...
    開(kāi)封第一講書(shū)人閱讀 51,274評(píng)論 1 300
  • 那天积瞒,我揣著相機(jī)與錄音,去河邊找鬼登下。 笑死茫孔,一個(gè)胖子當(dāng)著我的面吹牛,可吹牛的內(nèi)容都是我干的被芳。 我是一名探鬼主播缰贝,決...
    沈念sama閱讀 40,126評(píng)論 3 418
  • 文/蒼蘭香墨 我猛地睜開(kāi)眼,長(zhǎng)吁一口氣:“原來(lái)是場(chǎng)噩夢(mèng)啊……” “哼畔濒!你這毒婦竟也來(lái)了剩晴?” 一聲冷哼從身側(cè)響起,我...
    開(kāi)封第一講書(shū)人閱讀 38,980評(píng)論 0 275
  • 序言:老撾萬(wàn)榮一對(duì)情侶失蹤侵状,失蹤者是張志新(化名)和其女友劉穎赞弥,沒(méi)想到半個(gè)月后,有當(dāng)?shù)厝嗽跇?shù)林里發(fā)現(xiàn)了一具尸體趣兄,經(jīng)...
    沈念sama閱讀 45,414評(píng)論 1 313
  • 正文 獨(dú)居荒郊野嶺守林人離奇死亡嗤攻,尸身上長(zhǎng)有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 37,599評(píng)論 3 334
  • 正文 我和宋清朗相戀三年,在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了诽俯。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片妇菱。...
    茶點(diǎn)故事閱讀 39,773評(píng)論 1 348
  • 序言:一個(gè)原本活蹦亂跳的男人離奇死亡承粤,死狀恐怖,靈堂內(nèi)的尸體忽然破棺而出闯团,到底是詐尸還是另有隱情辛臊,我是刑警寧澤,帶...
    沈念sama閱讀 35,470評(píng)論 5 344
  • 正文 年R本政府宣布房交,位于F島的核電站彻舰,受9級(jí)特大地震影響,放射性物質(zhì)發(fā)生泄漏候味。R本人自食惡果不足惜刃唤,卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 41,080評(píng)論 3 327
  • 文/蒙蒙 一、第九天 我趴在偏房一處隱蔽的房頂上張望白群。 院中可真熱鬧尚胞,春花似錦、人聲如沸帜慢。這莊子的主人今日做“春日...
    開(kāi)封第一講書(shū)人閱讀 31,713評(píng)論 0 22
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽(yáng)粱玲。三九已至躬柬,卻和暖如春,著一層夾襖步出監(jiān)牢的瞬間抽减,已是汗流浹背允青。 一陣腳步聲響...
    開(kāi)封第一講書(shū)人閱讀 32,852評(píng)論 1 269
  • 我被黑心中介騙來(lái)泰國(guó)打工, 沒(méi)想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留卵沉,地道東北人颠锉。 一個(gè)月前我還...
    沈念sama閱讀 47,865評(píng)論 2 370
  • 正文 我出身青樓,卻偏偏與公主長(zhǎng)得像偎箫,于是被迫代替她去往敵國(guó)和親木柬。 傳聞我的和親對(duì)象是個(gè)殘疾皇子,可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 44,689評(píng)論 2 354

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

  • 一. 寫(xiě)在前面 要學(xué)習(xí)算法淹办,“排序”是一個(gè)回避不了的重要話題眉枕,在分析完并查集算法和常用數(shù)據(jù)結(jié)構(gòu)之后,今天我們終于可...
    Leesper閱讀 2,531評(píng)論 0 40
  • 概述 排序有內(nèi)部排序和外部排序怜森,內(nèi)部排序是數(shù)據(jù)記錄在內(nèi)存中進(jìn)行排序速挑,而外部排序是因排序的數(shù)據(jù)很大,一次不能容納全部...
    蟻前閱讀 5,183評(píng)論 0 52
  • 概述:排序有內(nèi)部排序和外部排序副硅,內(nèi)部排序是數(shù)據(jù)記錄在內(nèi)存中進(jìn)行排序姥宝,而外部排序是因排序的數(shù)據(jù)很大,一次不能容納全部...
    每天刷兩次牙閱讀 3,730評(píng)論 0 15
  • Recently, I read a quote: To exist is to change, to chang...
    JessicaRose閱讀 258評(píng)論 0 0
  • 在這一章里恐疲,故事的主人公是秦大奶奶腊满。我對(duì)秦大奶奶始終是抱著敬愛(ài)之情的套么,即使她有一段時(shí)間死皮爛臉的守著學(xué)校旁的房子不...
    那花評(píng)書(shū)閱讀 1,793評(píng)論 0 3