面试算法代码知识梳理系列

面试算法知识梳理(1) - 排序算法
面试算法知识梳理(2) - 字符串算法第一部分
面试算法知识梳理(3) - 字符串算法第二部分
面试算法知识梳理(4) - 数组第一部分
面试算法知识梳理(5) - 数组第二部分
面试算法知识梳理(6) - 数组第三部分
面试算法知识梳理(7) - 数组第四部分
面试算法知识梳理(8) - 二分查找算法及其变型
面试算法知识梳理(9) - 链表算法第一部分
面试算法知识梳理(10) - 二叉查找树
面试算法知识梳理(11) - 二叉树算法第一部分
面试算法知识梳理(12) - 二叉树算法第二部分
面试算法知识梳理(13) - 二叉树算法第三部分

---

一、概要

最近在看上学时候总结的一些东西，发现之前针对排序、字符串、数组、链表等，总结了一些面试时候常用的算法代码，因此打算整理一下分享给大家。

本文介绍了排序算法的C++代码实现，所有代码均可通过 菜鸟工具在线编译器 直接运行，算法目录：

• 插入排序
• 希尔排序
• 选择排序
• 冒泡排序
• 计数排序
• 基数排序
• 归并排序
• 快速排序
• 双向扫描的快速排序
• 堆排序

二、代码实现

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;
}

运行结果：

>> 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;
}

运行结果：

>> 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;
}

运行结果：

>> 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;
}

运行结果：

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

2.5 计数排序

#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;
}

运行结果为：

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

2.6 基数排序

#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;
}

运行结果为：

>> 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;
}

运行结果为：

>> 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;
}

运行结果为：

>> 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;
}

运行结果为：

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

2.10 堆排序

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

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

void maxHeapify(int *p, int di, int length){
    if(p == NULL || length <= 0 || di >= length || di < 0)
        throw std::runtime_error("error");
    int li = (di<<1)+1;
    int t = p[di];
    while(li < length){
        if(li+1 < length && p[li+1] > p[li])
            li++;
        if(p[di] >= p[li])
            break;
        p[di] = p[li];
        di = li;
        li = (di<<1)+1;
    }
    p[di] = t;
}

void buildMaxHeap(int *p, int length){
    if(p == NULL || length <= 0)
        throw std::runtime_error("error");
    for(int i=(length>>1)-1; i >= 0; i--){
        maxHeapify(p,i,length);
    }
}

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

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

运行结果为：

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

---

更多文章，欢迎访问我的 Android 知识梳理系列：

• Android 知识梳理目录：http://www.jianshu.com/p/fd82d18994ce
• 个人主页：http://lizejun.cn
• 个人知识总结目录：http://lizejun.cn/categories/