常見排序算法

希爾排序晶疼,快速排序,堆排序锭吨,2路歸并算法的c++簡單實現(xiàn)

#include <iostream>
#include <ctime>
#include <cmath>
using namespace std;

//對數(shù)列做一趟增量為d的希爾插入排序
void shellInsert(int *list, int length, int d)
{
    for (int i = d; i < length; i++)
    {
        //間隔為d的插入排序
        if (list[i] < list[i - d])
        {
            int temp = list[i];
            int j;
            //向左查找最終插入位置寒匙,查找的同時順便右搬數(shù)據(jù)
            for (j = i - d; j >= 0 && temp < list[j]; j -= d)
                list[j + d] = list[j];
            list[j + d] = temp;
        }
    }
}

//希爾排序(升序)
void shellSort(int *list, int length)
{
    //以{2^n-1}為增量序列
    for (int d = 1 << (int)log2(length); d >= 2; d >>= 1)
        shellInsert(list, length, d - 1);
}

//快速排序(升序)
void quickSort(int *list, int length)
{
    if (length <= 1) return;
    //隨機選取信標
    int pivot = list[rand() % length];
    int i = 0, j = length - 1;
    while (i != j)
    {
        while (i != j && list[i] < pivot) 
            i++;
        while (i != j && list[j] >= pivot)
            j--;
        swap(list[i], list[j]);
    }
    quickSort(list, i);
    quickSort(list + i, length - i);
}

//堆排序(升序)
void heapSort(int *list, int length)
{
    int heap[length + 1] = {0};
    //建堆
    for (int i = 1; i <= length; i++)
    {
        heap[i] = list[i - 1];
        for (int j = i; j > 1 && heap[j] < heap[j / 2]; j /= 2)
            swap(heap[j], heap[j / 2]);
    }
    //彈出锄弱,重調(diào)整
    for (int i = 0, j = length; i < length; i++, j--)
    {
        list[i] = heap[1];
        swap(heap[1], heap[j]);
        for (int k = 2; k < j; k *= 2)
        {
            //從2個孩子(或只有1個孩子)中選取最小的那個去比較
            if (k + 1 < j && heap[k + 1] < heap[k])
                k = k + 1;
            if (heap[k] < heap[k / 2])
                swap(heap[k], heap[k / 2]);
            else
                break;
        }
    }
}

//2路歸并排序(升序)
void mergeSort(int *list, int length)
{
    if (length <= 1)
        return;
    int mid = length / 2;
    mergeSort(list, mid);
    mergeSort(list + mid, length - mid);
    //2路歸并
    int tempList[length];
    int i = 0, j = mid, k = 0;
    while (k < length)
    {
        if (j >= length || (i < mid && list[i] < list[j]))
            tempList[k++] = list[i++];
        if (i >= mid || (j < length && list[j] < list[i]))
            tempList[k++] = list[j++];
    }
    for (k = 0; k < length; k++)
        list[k] = tempList[k];
}

int main()
{
    //初始化數(shù)列
    int length;
    cin >> length;

    int *list = new int[length];
    for (int i = 0; i < length; i++)
        list[i] = i;

    //隨機洗切數(shù)列
    srand(time(0));
    for (int i = length - 1; i > 0; i--)
        swap(list[i], list[rand() % i]);

    //打印排序前數(shù)列
    for (int i = 0; i < length; i++)
        cout << list[i] << " ";
    cout << endl;

    //shellSort(list, length);
    //quickSort(list, length);
    //heapSort(list, length);
    mergeSort(list, length);

    //打印排序后數(shù)列
    for (int i = 0; i < length; i++)
        cout << list[i] << " ";
    cout << endl;
}

運行結果

int main()里面寫了一個隨機數(shù)列生成肖卧,可以快速驗證算法的正確性

歡迎友好交流

最后編輯于
?著作權歸作者所有,轉載或內(nèi)容合作請聯(lián)系作者
  • 序言:七十年代末掸鹅,一起剝皮案震驚了整個濱河市巍沙,隨后出現(xiàn)的幾起案子,更是在濱河造成了極大的恐慌句携,老刑警劉巖,帶你破解...
    沈念sama閱讀 217,734評論 6 505
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件牡辽,死亡現(xiàn)場離奇詭異,居然都是意外死亡敞临,警方通過查閱死者的電腦和手機,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 92,931評論 3 394
  • 文/潘曉璐 我一進店門麸澜,熙熙樓的掌柜王于貴愁眉苦臉地迎上來挺尿,“玉大人,你說我怎么就攤上這事”喾” “怎么了熟史?”我有些...
    開封第一講書人閱讀 164,133評論 0 354
  • 文/不壞的土叔 我叫張陵,是天一觀的道長窄俏。 經(jīng)常有香客問我蹂匹,道長,這世上最難降的妖魔是什么凹蜈? 我笑而不...
    開封第一講書人閱讀 58,532評論 1 293
  • 正文 為了忘掉前任限寞,我火速辦了婚禮仰坦,結果婚禮上履植,老公的妹妹穿的比我還像新娘。我一直安慰自己悄晃,他們只是感情好玫霎,可當我...
    茶點故事閱讀 67,585評論 6 392
  • 文/花漫 我一把揭開白布。 她就那樣靜靜地躺著妈橄,像睡著了一般庶近。 火紅的嫁衣襯著肌膚如雪。 梳的紋絲不亂的頭發(fā)上眷蚓,一...
    開封第一講書人閱讀 51,462評論 1 302
  • 那天鼻种,我揣著相機與錄音,去河邊找鬼溪椎。 笑死普舆,一個胖子當著我的面吹牛,可吹牛的內(nèi)容都是我干的校读。 我是一名探鬼主播沼侣,決...
    沈念sama閱讀 40,262評論 3 418
  • 文/蒼蘭香墨 我猛地睜開眼,長吁一口氣:“原來是場噩夢啊……” “哼歉秫!你這毒婦竟也來了蛾洛?” 一聲冷哼從身側響起,我...
    開封第一講書人閱讀 39,153評論 0 276
  • 序言:老撾萬榮一對情侶失蹤雁芙,失蹤者是張志新(化名)和其女友劉穎轧膘,沒想到半個月后,有當?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體兔甘,經(jīng)...
    沈念sama閱讀 45,587評論 1 314
  • 正文 獨居荒郊野嶺守林人離奇死亡谎碍,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點故事閱讀 37,792評論 3 336
  • 正文 我和宋清朗相戀三年,在試婚紗的時候發(fā)現(xiàn)自己被綠了洞焙。 大學時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片蟆淀。...
    茶點故事閱讀 39,919評論 1 348
  • 序言:一個原本活蹦亂跳的男人離奇死亡拯啦,死狀恐怖,靈堂內(nèi)的尸體忽然破棺而出熔任,到底是詐尸還是另有隱情褒链,我是刑警寧澤,帶...
    沈念sama閱讀 35,635評論 5 345
  • 正文 年R本政府宣布疑苔,位于F島的核電站甫匹,受9級特大地震影響,放射性物質發(fā)生泄漏惦费。R本人自食惡果不足惜兵迅,卻給世界環(huán)境...
    茶點故事閱讀 41,237評論 3 329
  • 文/蒙蒙 一、第九天 我趴在偏房一處隱蔽的房頂上張望趁餐。 院中可真熱鬧喷兼,春花似錦、人聲如沸后雷。這莊子的主人今日做“春日...
    開封第一講書人閱讀 31,855評論 0 22
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽臀突。三九已至勉抓,卻和暖如春,著一層夾襖步出監(jiān)牢的瞬間候学,已是汗流浹背藕筋。 一陣腳步聲響...
    開封第一講書人閱讀 32,983評論 1 269
  • 我被黑心中介騙來泰國打工, 沒想到剛下飛機就差點兒被人妖公主榨干…… 1. 我叫王不留梳码,地道東北人隐圾。 一個月前我還...
    沈念sama閱讀 48,048評論 3 370
  • 正文 我出身青樓,卻偏偏與公主長得像掰茶,于是被迫代替她去往敵國和親暇藏。 傳聞我的和親對象是個殘疾皇子,可洞房花燭夜當晚...
    茶點故事閱讀 44,864評論 2 354