面試算法知識(shí)梳理(1) - 排序算法

面試算法代碼知識(shí)梳理系列

面試算法知識(shí)梳理(1) - 排序算法
面試算法知識(shí)梳理(2) - 字符串算法第一部分
面試算法知識(shí)梳理(3) - 字符串算法第二部分
面試算法知識(shí)梳理(4) - 數(shù)組第一部分
面試算法知識(shí)梳理(5) - 數(shù)組第二部分
面試算法知識(shí)梳理(6) - 數(shù)組第三部分
面試算法知識(shí)梳理(7) - 數(shù)組第四部分
面試算法知識(shí)梳理(8) - 二分查找算法及其變型
面試算法知識(shí)梳理(9) - 鏈表算法第一部分
面試算法知識(shí)梳理(10) - 二叉查找樹
面試算法知識(shí)梳理(11) - 二叉樹算法第一部分
面試算法知識(shí)梳理(12) - 二叉樹算法第二部分
面試算法知識(shí)梳理(13) - 二叉樹算法第三部分

一、概要

最近在看上學(xué)時(shí)候總結(jié)的一些東西菩暗，發(fā)現(xiàn)之前針對(duì)排序专钉、字符串尽棕、數(shù)組立哑、鏈表等仔雷，總結(jié)了一些面試時(shí)候常用的算法代碼水醋，因此打算整理一下分享給大家管削。

本文介紹了排序算法的C++代碼實(shí)現(xiàn)，所有代碼均可通過 菜鳥工具在線編譯器 直接運(yùn)行罗心，算法目錄：

  • 插入排序
  • 希爾排序
  • 選擇排序
  • 冒泡排序
  • 計(jì)數(shù)排序
  • 基數(shù)排序
  • 歸并排序
  • 快速排序
  • 雙向掃描的快速排序
  • 堆排序

二里伯、代碼實(shí)現(xiàn)

2.1 插入排序

#include <iostream>
#include <stdexcept>
using namespace std;

void printArray(int *p, int length) {
    for (int i = 0; i < length; i++) {
        cout << p[i] << ", ";
    }
}

void insertSort(int *p, int length){
    if(p == NULL || length <= 0)
        throw std::runtime_error("NULL Pointer");
    int i,j,temp;
    for(i = 1; i < length; i++){
        temp = p[i];
        for(j = i; j >= 1 && p[j-1] > temp; j--)
            p[j] = p[j-1];
        p[j] = temp;
    }
}

int main()
{   
    int a[] = {30, 29, 50, 2, 42, 60};
    insertSort(a, 6);
    printArray(a, 6);
    return 0;
}

運(yùn)行結(jié)果：

>> 2, 29, 30, 42, 50, 60,

2.2 希爾排序

#include <iostream>
#include <stdexcept>
using namespace std;

void printArray(int *p, int length) {
    for (int i = 0; i < length; i++) {
        cout << p[i] << ", ";
    }
}

void insertShell(int *p ,int inc, int length){
    if(p == NULL || length <= 0 || inc <= 0 || inc >= length)
        throw std::runtime_error("invaild input");
    int i,j,temp;
    for(i = inc; i < length; i++){
        temp = p[i];
        for(j = i; j >= inc && p[j-inc] > temp; j -= inc)
            p[j] = p[j-inc];
        p[j] = temp;
    }
}

void shellSort(int *p, int length){
    if(p == NULL || length <= 0)
        throw std::runtime_error("invaild input");
    int inc = length >> 1;
    while(inc >= 1){
        insertShell(p,inc,length);
        inc >>= 1;
    }
}

int main()
{   
    int a[] = {30, 29, 50, 2, 42, 60};
    shellSort(a, 6);
    printArray(a, 6);
    return 0;
}

運(yùn)行結(jié)果：

>> 2, 29, 30, 42, 50, 60,

2.3 選擇排序

#include <iostream>
#include <stdexcept>
using namespace std;

void printArray(int *p, int length) {
    for (int i = 0; i < length; i++) {
        cout << p[i] << ", ";
    }
}

void selectSort(int *p, int length){
    if(p == NULL || length <= 0)
        throw std::runtime_error("NULL Pointer");
    int i,j,mind,t;
    for(j = 0; j < length - 1; j++){
        mind = j;
        for(i = j+1; i < length; i++){
            if(p[i] < p[mind])
                mind = i;
        }
        if(mind != j){
            t = p[j]; p[j] = p[mind]; p[mind] = t;
        }
    }
}

int main()
{   
    int a[] = {30, 29, 50, 2, 42, 60};
    selectSort(a, 6);
    printArray(a, 6);
    return 0;
}

運(yùn)行結(jié)果：

>> 2, 29, 30, 42, 50, 60,

2.4 冒泡排序

#include <iostream>
#include <stdexcept>
using namespace std;

void printArray(int *p, int length) {
    for (int i = 0; i < length; i++) {
        cout << p[i] << ", ";
    }
}

void bubbleSort(int *p, int length){
    if(p == NULL || length <= 0)
        throw std::runtime_error("NULL Pointer");
    int i,j,t;
    for(j = 0; j < length - 1; j++)
        for(i = 0; i < length - j - 1; i++){
            if(p[i] > p[i+1]){
                t = p[i]; p[i] = p[i+1]; p[i+1] = t;
            }
    }
}

int main()
{   
    int a[] = {30, 29, 50, 2, 42, 60};
    bubbleSort(a, 6);
    printArray(a, 6);
    return 0;
}

運(yùn)行結(jié)果：

>> 2, 29, 30, 42, 50, 60,

2.5 計(jì)數(shù)排序

#include <iostream>
#include <stdexcept>
using namespace std;

void printArray(int *p, int length) {
    for (int i = 0; i < length; i++) {
        cout << p[i] << ", ";
    }
}

void countSort(int *p, int length, int maxNum){
    if(p == NULL || length <= 0 )
        throw std::runtime_error("NULL Pointer");
    int *c = new int[maxNum+1];
    int *b = new int[length];
    int i;
    for(i = 0; i < maxNum+1; i++){
        c[i] = 0;
    }
    for(i = 0; i < length; i++){
        if(p[i] > maxNum)
            throw std::runtime_error("invaild input");
        c[p[i]] += 1;
    }
    for(i = 1; i < maxNum+1; i++){
        c[i] += c[i-1];
    }
    for(i = length-1; i >= 0; i--){
        if( c[p[i]] < 1 )
            throw std::runtime_error("error");
        b[--c[p[i]]] = p[i];
    }
    for(i = 0; i < length; i++)
        p[i] = b[i];
    delete [] c; c = NULL;
    delete [] b; b = NULL;
}

int main()
{   
    int a[] = {30, 29, 50, 2, 42, 60};
    countSort(a, 6, 60);
    printArray(a, 6);
    return 0;
}

運(yùn)行結(jié)果為：

>> 2, 29, 30, 42, 50, 60,

2.6 基數(shù)排序

#include <iostream>
#include <stdexcept>
using namespace std;

void printArray(int *p, int length) {
    for (int i = 0; i < length; i++) {
        cout << p[i] << ", ";
    }
}

int getdigit(int x, int d){
    int a[] = {1, 10, 100};
    return (x/a[d]) % 10;
}

void radixSort(int *p, int length, int d, int radix){
    if(p == NULL || length <= 0 || d <= 0)
        throw std::runtime_error("NULL Pointer");
    int i;
    int *c = new int[radix+1];
    int *b = new int[length];
    for(int j = 0; j != d; j++){
        for(i = 0; i < radix + 1; i++)
            c[i] = 0;

        for(i = 0; i < length; i++){
            int r = getdigit(p[i], j);
            if(r > radix)
                throw std::runtime_error("invaild input");
            c[r] += 1;
        }

        for(i = 1; i < radix + 1; i++)
            c[i] += c[i-1];
        for(i = length - 1; i >= 0; i--){
            int r = getdigit(p[i], j);
            if(c[r] < 1)
                throw std::runtime_error("error");
            b[--c[r]] = p[i];
        }

        for(i = 0; i < length; i++)
            p[i] = b[i];
    }
    delete [] c; c = NULL;
    delete [] b; b = NULL;
}

int main()
{   
    int a[] = {30, 29, 50, 2, 42, 60};
    radixSort(a, 6, 2, 9);
    printArray(a, 6);
    return 0;
}

運(yùn)行結(jié)果為：

>> 2, 29, 30, 42, 50, 60,

2.7 歸并排序

#include <iostream>
#include <stdexcept>
using namespace std;

int INF = 0x7fffffff;

void printArray(int *p, int length) {
    for (int i = 0; i < length; i++) {
        cout << p[i] << ", ";
    }
}

void mergeCore(int *p1, int *p2, int p1Len, int p2Len){
    if(p1 == NULL || p2 == NULL || p1Len <= 0 || p2Len <= 0)
        throw std::runtime_error("error");
    int *l = new int[p1Len+1];
    int *r = new int[p2Len+1];
    int i;
    int m = 0;
    int n = 0;

    for(i = 0; i < p1Len; i++)
        l[i] = p1[i];
    l[i] = INF;

    for(i = 0; i < p2Len; i++)
        r[i] = p2[i];
    r[i] = INF;

    i = 0;
    while(i < p1Len + p2Len){
        if(r[n] < l[m]){
            p1[i++] = r[n++];
        }else{
            p1[i++] = l[m++];
        }
    }
    delete [] l; l = NULL;
    delete [] r; r = NULL;
}

void mergeSort(int *p, int length){
    if(p == NULL || length <= 0)
        throw std::runtime_error("error");
    if(length == 1)
        return;
    int llen,rlen;
    llen = length >> 1;
    rlen = length - llen;
    mergeSort(p,llen);
    mergeSort(p+llen,rlen);
    mergeCore(p,p+llen,llen,rlen);
}

int main()
{   
    int a[] = {30, 29, 50, 2, 42, 60};
    mergeSort(a, 6);
    printArray(a, 6);
    return 0;
}

運(yùn)行結(jié)果為：

>> 2, 29, 30, 42, 50, 60,

2.8 快速排序

#include <iostream>
#include <stdexcept>
using namespace std;

void printArray(int *p, int length) {
    for (int i = 0; i < length; i++) {
        cout << p[i] << ", ";
    }
}

void quickSort(int *p, int length){
    if(p == NULL || length <= 0)
        throw std::runtime_error("error");
    if(length == 1)
        return;
    int mid = 0;
    int t;
    for(int i = 0; i < length; i++){
        if(p[i] < p[0]){
            mid++;
            t = p[mid]; p[mid] = p[i]; p[i] = t;
        }
    }
    t = p[0]; p[0] = p[mid]; p[mid] = t;
    int rlen = length - mid - 1;
    if(mid > 0)
        quickSort(p,mid);
    if(rlen > 0)
        quickSort(p+mid+1,rlen);
}

int main()
{   
    int a[] = {30, 29, 50, 2, 42, 60};
    quickSort(a, 6);
    printArray(a, 6);
    return 0;
}

運(yùn)行結(jié)果為：

>> 2, 29, 30, 42, 50, 60,

2.9 雙向掃描的快速排序

#include <iostream>
#include <stdexcept>
using namespace std;

void printArray(int *p, int length) {
    for (int i = 0; i < length; i++) {
        cout << p[i] << ", ";
    }
}

void quickSortDouble(int *p, int length){
    if(p == NULL || length <= 0)
        throw std::runtime_error("error");
    if(length == 1)
        return;
    int i = 0;
    int t;
    int mid = length;
    while(true){
        do { i++; } while( i < length && p[i] < p[0]);
        do { mid--; } while( mid > 0 && p[mid] > p[0] );
        if(i > mid) break;
        t = p[i]; p[i] = p[mid]; p[mid] = t;
    }
    t = p[0]; p[0] = p[mid]; p[mid] = t;
    int rlen = length - mid - 1;
    if(mid > 0)
        quickSortDouble(p,mid);
    if(rlen > 0)
        quickSortDouble(p+mid+1,rlen);
}

int main()
{   
    int a[] = {30, 29, 50, 2, 42, 60};
    quickSortDouble(a, 6);
    printArray(a, 6);
    return 0;
}

運(yùn)行結(jié)果為：

>> 2, 29, 30, 42, 50, 60,

2.10 堆排序

/**
 * @author lizejun
 **/
public class HeapSort {
    
    public static void heapSort() {
        int[] arr = new int[]{9, 10, -1, 20, -30, 100};
        int len = arr.length;
        //1.初始化最大堆。
        for (int i = len / 2 - 1; i >= 0; i--) {
            heapAdjustNode(arr, i, len);
        }
        System.out.println(Arrays.toString(arr));
        for (int i = len - 1; i >= 1; i--) {
            //2.把最大的元素放到最后一個(gè)位置渤闷。
            int temp = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;
            //3.維護(hù)堆的特性疾瓮。
            heapAdjustNode(arr, 0, i);
        }
        System.out.println(Arrays.toString(arr));
    }

    private static void heapAdjustNode(int[] arr, int i, int length) {
        int temp = arr[i];
        //2*i+1 表示的是父節(jié)點(diǎn)的左孩子節(jié)點(diǎn)。
        for (int k = i * 2 + 1; k < length; k = 2 * k + 1) {
            //1.獲取左右子節(jié)點(diǎn)最大的值飒箭。
            if (k + 1 < length && arr[k+1] > arr[k]) {
                k++;
            }
            //2.1 如果左右孩子節(jié)點(diǎn)大于父節(jié)點(diǎn)狼电，那么用它替代父節(jié)點(diǎn)。
            if (arr[k] > temp) {
                arr[i] = arr[k];
                //上移的孩子節(jié)點(diǎn)作為下次循環(huán)的父節(jié)點(diǎn)弦蹂。
                i = k;
            //2.2 反之說明滿足最大堆的特性肩碟，跳出循環(huán)。   
            } else {
                break;
            }
        }
        arr[i] = temp;
    }
    
}

運(yùn)行結(jié)果為：

>> [100, 20, 9, 10, -30, -1]
>> [-30, -1, 9, 10, 20, 100]

更多文章凸椿，歡迎訪問我的 Android 知識(shí)梳理系列：

最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
  • 人面猴
    序言：七十年代末腾务，一起剝皮案震驚了整個(gè)濱河市，隨后出現(xiàn)的幾起案子削饵，更是在濱河造成了極大的恐慌，老刑警劉巖未巫，帶你破解...
    沈念sama閱讀 217,907評(píng)論 6贊 506
  • 死咒
    序言：濱河連續(xù)發(fā)生了三起死亡事件窿撬，死亡現(xiàn)場離奇詭異，居然都是意外死亡叙凡，警方通過查閱死者的電腦和手機(jī)劈伴，發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 92,987評(píng)論 3贊 395
  • 救了他兩次的神仙讓他今天三更去死
    文/潘曉璐 我一進(jìn)店門，熙熙樓的掌柜王于貴愁眉苦臉地迎上來，“玉大人跛璧，你說我怎么就攤上這事严里。” “怎么了追城？”我有些...
    開封第一講書人閱讀 164,298評(píng)論 0贊 354
  • 道士緝兇錄：失蹤的賣姜人
    文/不壞的土叔 我叫張陵刹碾，是天一觀的道長。 經(jīng)常有香客問我座柱，道長迷帜，這世上最難降的妖魔是什么？ 我笑而不...
    開封第一講書人閱讀 58,586評(píng)論 1贊 293
  • ?港島之戀（遺憾婚禮）
    正文 為了忘掉前任色洞，我火速辦了婚禮戏锹，結(jié)果婚禮上，老公的妹妹穿的比我還像新娘火诸。我一直安慰自己锦针，他們只是感情好，可當(dāng)我...
    茶點(diǎn)故事閱讀 67,633評(píng)論 6贊 392
  • 惡毒庶女頂嫁案：這布局不是一般人想出來的
    文/花漫 我一把揭開白布置蜀。 她就那樣靜靜地躺著奈搜，像睡著了一般。 火紅的嫁衣襯著肌膚如雪盾碗。 梳的紋絲不亂的頭發(fā)上媚污，一...
    開封第一講書人閱讀 51,488評(píng)論 1贊 302
  • 城市分裂傳說
    那天，我揣著相機(jī)與錄音廷雅，去河邊找鬼耗美。 笑死，一個(gè)胖子當(dāng)著我的面吹牛航缀，可吹牛的內(nèi)容都是我干的商架。 我是一名探鬼主播，決...
    沈念sama閱讀 40,275評(píng)論 3贊 418
  • 雙鴛鴦連環(huán)套：你想象不到人心有多黑
    文/蒼蘭香墨 我猛地睜開眼芥玉，長吁一口氣：“原來是場噩夢啊……” “哼蛇摸！你這毒婦竟也來了？” 一聲冷哼從身側(cè)響起灿巧，我...
    開封第一講書人閱讀 39,176評(píng)論 0贊 276
  • 萬榮殺人案實(shí)錄
    序言：老撾萬榮一對(duì)情侶失蹤赶袄，失蹤者是張志新（化名）和其女友劉穎，沒想到半個(gè)月后抠藕，有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體饿肺，經(jīng)...
    沈念sama閱讀 45,619評(píng)論 1贊 314
  • ?護(hù)林員之死
    正文 獨(dú)居荒郊野嶺守林人離奇死亡，尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 37,819評(píng)論 3贊 336
  • ?白月光啟示錄
    正文 我和宋清朗相戀三年盾似，在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了敬辣。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片。...
    茶點(diǎn)故事閱讀 39,932評(píng)論 1贊 348
  • 活死人
    序言：一個(gè)原本活蹦亂跳的男人離奇死亡，死狀恐怖溉跃，靈堂內(nèi)的尸體忽然破棺而出村刨，到底是詐尸還是另有隱情，我是刑警寧澤撰茎，帶...
    沈念sama閱讀 35,655評(píng)論 5贊 346
  • ?日本核電站爆炸內(nèi)幕
    正文 年R本政府宣布嵌牺，位于F島的核電站，受9級(jí)特大地震影響乾吻，放射性物質(zhì)發(fā)生泄漏髓梅。R本人自食惡果不足惜，卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 41,265評(píng)論 3贊 329
  • 男人毒藥：我在死后第九天來索命
    文/蒙蒙 一绎签、第九天 我趴在偏房一處隱蔽的房頂上張望枯饿。 院中可真熱鬧，春花似錦诡必、人聲如沸奢方。這莊子的主人今日做“春日...
    開封第一講書人閱讀 31,871評(píng)論 0贊 22
  • 一樁弒父案爸舒，背后竟有這般陰謀
    文/蒼蘭香墨 我抬頭看了看天上的太陽蟋字。三九已至，卻和暖如春扭勉，著一層夾襖步出監(jiān)牢的瞬間鹊奖，已是汗流浹背。 一陣腳步聲響...
    開封第一講書人閱讀 32,994評(píng)論 1贊 269
  • 情欲美人皮
    我被黑心中介騙來泰國打工涂炎， 沒想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留忠聚，地道東北人。 一個(gè)月前我還...
    沈念sama閱讀 48,095評(píng)論 3贊 370
  • 代替公主和親
    正文 我出身青樓唱捣，卻偏偏與公主長得像两蟀，于是被迫代替她去往敵國和親。 傳聞我的和親對(duì)象是個(gè)殘疾皇子震缭，可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 44,884評(píng)論 2贊 354

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

  • 一. 寫在前面 要學(xué)習(xí)算法赂毯，“排序”是一個(gè)回避不了的重要話題，在分析完并查集算法和常用數(shù)據(jù)結(jié)構(gòu)之后拣宰，今天我們終于可...
    Leesper閱讀 2,531評(píng)論 0贊 40
  • Android 自定義View的各種姿勢1 Activity的顯示之ViewRootImpl詳解 Activity...
    passiontim閱讀 172,129評(píng)論 25贊 707
  • 前言 本篇文章基本是從常用排序算法總結(jié)(一)快速排序引申而來党涕，其中大部分代碼和描述都來自這兩篇文章。 時(shí)間復(fù)雜度 ...
    王三的貓阿德閱讀 1,086評(píng)論 0贊 1
  • 今日看四場比賽巡社，趁記憶還未消退遣鼓，寫一點(diǎn)觀賽感受。隨手一寫重贺，大家就隨便一看，如果在這隨便一看之外還能收獲點(diǎn)對(duì)辯論的理...
    秋庫里閱讀 418評(píng)論 0贊 0
  • 同學(xué)們你們認(rèn)識(shí)野蠶子嗎？昨天在濕地公園我認(rèn)識(shí)了野蠶子气笙。 野蠶子的身上有像0一樣花紋次企，我數(shù)了好幾遍都數(shù)...
    古月汐_9a31閱讀 452評(píng)論 0贊 0