Seven Basic Sorting Algorithms

Bubble Sort

Basic Idea

起泡排序（Bubble Sort） 过程中，关键字较小的记录好比水中气泡逐趟向上漂浮，关键字较大的记录好比石头往下沉，每一趟有一块“最大”的石头沉入水底。

Description

第1趟起泡排序：将第1个记录的关键字与第2个记录的关键字比较，若为逆序，则交换。再比较第2与第3个记录的关键字……依次类推，直至第n-1与第n个记录的关键字比较完为止。n-1次比较、交换的结果是选出了正序中第n个记录。
第i趟起泡排序：对前n-i个记录进行与第1趟同样的操作。n-i次比较、交换的结果是选出了正序中第n-i个记录。
重复步骤2，直至本趟排序无记录交换或i = n为止。

Implement

Time Complexity: O(n^2)
Space Complexity: O(n)
Oder By: asc
Language: C++ 14

#include <vector>

void bubble_sort(vector<T> &array) {
    bool no_change;

    for (int i = 0; i < array.size() - 1; i++) {
        no_change = true;
        for (int j = 0; j < array.size() - i - 1; j++) {
            if (array[j] > array[j + 1]) {
                no_change = false;
                // swap(array[j], array[j+1]);
                array[j] += array[j + 1];
                array[j + 1] = array[j] - array[j + 1];
                array[j] -= array[j + 1];
            }
        }
        if (no_change) break;
    }
}

Quick Sort

Basic Idea

快速排序（Quick Sort） 是对起泡排序的一种改进，通过一趟排序将待排记录分割成独立的两部分，其中一部分的关键字均比另一部分的关键字小。再分别对这两部分记录进行排序，以达到整体有序。

Description

对待排序列选取任意一个记录（通常选第一个）作为枢轴（pivot），其关键字为pivot_key。附设两个指针low和high。
一趟快速排序：high向前搜索，找到第1个关键字小于pivot_key的记录，将其与枢轴记录交换；low向后搜索，找到第1个关键字大于pivot_key的记录，将其与枢轴记录交换；重复这两步，直至low = high为止。产生两个子序列。
将产生的两个子序列再分别进行快速排序，产生两个子序列。
重复步骤3，直至待排序列中只有一个记录为止。

Implement

Time Complexity: O(n*log n)
Space Complexity: O(n)
Oder By: asc
Language: C++ 14

Version 1

#include <vector>

template<typename T>
void quick_sort(vector<T> &array, int begin, int end) {
    if (begin < end - 1) {
        T pivot_key = array[begin];
        int low = begin, high = end - 1;

        while (low < high) {
            while (low < high && array[high] >= pivot_key) high--;
            swap(array[low], array[high]);
            while (low < high && array[low] <= pivot_key) low++;
            swap(array[low], array[high]);
        }
        quick_sort(array, begin, low);
        quick_sort(array, low + 1, end);
    }
}

Version 2（优化）

#include <vector>

template<typename T>
void quick_sort(vector<T> &array, int begin, int end) {
    if (begin < end - 1) {
        int low = begin, high = end - 1;

        while (low < high) {
            while (low < high && array[high] >= array[begin]) high--;
            while (low < high && array[low] <= array[begin]) low++;
            swap(array[low], array[high]);
        }
        swap(array[begin], array[low]);
        quick_sort(array, begin, low);
        quick_sort(array, low + 1, end);
    }
}

Version 3（再度优化）

#include <vector>

template<typename T>
void quick_sort(vector<T> &array, int begin, int end) {
    if (begin < end - 1) {
        T pivot_key = array[begin];
        int low = begin, high = end - 1;

        while (low < high) {
            while (low < high && array[high] >= pivot_key) high--;
            array[low] = array[high];
            while (low < high && array[low] <= pivot_key) low++;
            array[high] = array[low];
        }
        array[low] = pivot_key;
        quick_sort(array, begin, low);
        quick_sort(array, low + 1, end);
    }
}

Straight Insertion Sort

Basic Idea

直接插入排序（Straight Insertion Sort） 的基本思想是将一个记录插入到一个有序序列中，从而得到一个新的、记录数增1的有序序列。

Description

将当前的第i个记录插入由第1个记录到第i-1个记录组成的有序子序列中。
从第2个记录开始，到第n个记录为止，依次重复步骤1。

Implement

Time Complexity: O(n^2)
Space Complexity: O(n)
Oder By: asc
Language: C++ 14

#include <vector>

template<typename T>
void insert_sort(vector<T> &array) {
    for (int j, i = 1; i < array.size(); i++) {
        if (array[i] < array[i - 1]) {
            T temp = array[i];
            array[i] = array[i - 1];

            for (j = i - 2; j >= 0 && array[j] > temp; array[j + 1] = array[j], j--);
            array[j + 1] = temp;
        }
    }
}

Shell's Sort

Basic Idea

希尔排序（Shell's Sort） 又称 缩小增量排序（Diminishing Increment Sort），是一种对简单插入排序的优化。它的基本思想是：将待排序列分割成若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”，再对全体记录进行一次直接插入排序。

Description

按照 增量（间隙 gap） 划分成若干子序列，如gap = 3，划分{R1, R2, R3, R4, R5, R6, R7}为{R1, R4, R7}和{R2, R5}和{R3, R6}。对每个子序列分别进行直接插入排序。
递减增量，重复步骤1，直至gap = 1为止。

Implement

Time Complexity: ? ? ?
Space Complexity: O(n)
Oder By: asc
Language: C++ 14

// sort.h
#include <vector>

void shell_sort(vector<T> &array, vector<int> &gap) {
    for (int j, t = 0; t < gap.size(); t++) {
        for (int i = gap[t]; i < array.size(); i++) {
            if (array[i] < array[i - gap[t]]) {
                T temp = array[i];
                array[i] = array[i - gap[t]];

                for (j = i - 2 * gap[t]; j >= 0 && array[j] > temp; array[j + gap[t]] = array[j], j -= gap[t]);
                array[j + gap[t]] = temp;
            }
        }
    }
}

Using

// main.cpp
#include "sort.h"
#include <iostream>

using namespace std;

int main() {
    int n = 20;
    vector<float> array(n);
    array = {1, 4, 6, 7, 0, 9, 8, 3, 2, 5, 0, 1, 2, 9, 8, 3, 4, 7, 5, 6};
    vector<int> gap(5);
    gap = {7, 5, 3, 2, 1};

    shell_sort(array, gap);

    for (int i = 0; i < n; cout << array[i] << " ", i++);
    return 0;
}

[*] Caution! 增量（间隙）序列gap应满足如下条件：

记录的关键字递减。
除最后一个记录外，其余所有记录的关键字没有除1外的公因子。
最后一个记录的关键字为1。

Simple Selection Sort

Basic Idea

简单选择排序（Simple Selection Sort） 的基本思想是：通过n-i次关键字间的比较，从n-i+1个记录中选出关键字最小的记录，并和第i个记录交换。

Implement

Time Complexity: O(n^2)
Space Complexity: O(n)
Oder By: asc
Language: C++ 14

#include <vector>

template<typename T>
void selection_sort(vector<T> &array) {
    for (int min, i = 0; i < array.size(); i++) {
        min = i;
        for (int j = i + 1; j < array.size(); j++) {
            if (array[j] < array[min]) {
                min = j;
            }
        }
        if (min != i) {
            swap(array[min], array[i]);
        }
    }
}

Heap Sort

Basic Idea

堆（Heap） 对应一颗完全二叉树，且该树中所有非终端结点的值均不大于（或不小于）其左右孩子节点的值。

堆排序（Heap Sort） 需要解决两个问题：

如何构建一个堆？
堆顶输出后，如何维护堆的性质？

Description

已知：

第i个节点的父节点的索引为floor((i-1)/2)
第i个节点的左孩子节点的索引为2*i+1
第i个节点的右孩子节点的索引为2*i+2

Implement

Time Complexity: O(n*log n)
Space Complexity: O(n)
Oder By: asc
Language: C++ 14

// sort.h
#include <vector>

template<typename T>
void max_heapify(vector<T> &array, int begin, int end) {
    int cur = begin, child = cur * 2 + 1;

    while (child < end) {
        if (child + 1 < end && array[child] < array[child + 1]) {
            child++;
        }
        if (array[cur] < array[child]) {
            swap(array[cur], array[child]);
            cur = child;
            child = 2 * cur + 1;
        } else {
            break;
        }
    }
}

template<typename T>
void heap_sort(vector<T> &array) {
    int n = array.size();

    for (int i = n / 2 - 1; i >= 0; i--) {      // Build max heap
        max_heapify(array, i, array.size() - 1);
    }
    while (n--) {                               // Heap sort to make array oder by asc
        swap(array[0], array[n]);
        max_heapify(array, 0, n);
    }
}

Using

非STL（自定义）

// main.cpp
#include "sort.h"
#include <iostream>

using namespace std;

int main() {

    vector<float> array(n);
    array = {1, 4, 6, 7, 0, 9, 8, 3, 2, 5, 0, 1, 2, 9, 8, 3, 4, 7, 5, 6};

    heap_sort(array);

    for (int i = 0; i < n; cout << array[i] << " ", i++);
    return 0;
}

STL（推荐）

// main.cpp
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    vector<int> max_heap;                       // 设置大顶堆
    max_heap = {1, 4, 6, 7, 0, 9, 8, 3, 2, 5, 0, 1, 2, 9, 8, 3, 4, 7, 5, 6};
    make_heap(max_heap.begin(), max_heap.end());
    sort_heap(max_heap.begin(), max_heap.end());

    for (int i = 0; i < max_heap.size(); cout << max_heap[i] << " ", i++);
    return 0;
}

2-Way Merging Sort

Basic Idea

2-路归并排序（2-Way Merging Sort） 和上述方法均不相同。“归并”的意思是将两个或两个以上的有序表组合成一个新的有序表。

Description

将待排序列分隔成n个单位为1的子序列，相邻的子序列两两比较合并成单位为2的n/2个子序列
重复步骤1，合并后的子序列的单位为floor(2^i)，直至floor(2^i) = n为止。

Implement

Time Complexity: O(n*log n)
Space Complexity: O(n)
Oder By: asc
Language: C++ 14

#include <vector>

template<typename T>
void merge(vector<T> &array, int begin, int middle, int end, vector<T> &temp) {
    // 将有序的 array[begin ... middle-1] 和 array[middle ... end-1] 归并为有序的 temp[begin ... end-1]
    int lb = begin, rb = middle, tb = begin;
    while (lb != middle && rb != end) {
        if (array[lb] < array[rb])
            temp[tb++] = array[lb++];
        else
            temp[tb++] = array[rb++];
    }

    while (lb < middle) temp[tb++] = array[lb++];

    while (rb < end) temp[tb++] = array[rb++];

    for (int i = begin; i < end; array[i] = temp[i], i++);
}

template<typename T>
void merge_sort(vector<T> &array, int begin, int end, vector<T> &temp) {
    // 使无序的的 array[begin ... end-1] 归并为有序序列
    int middle = (begin + end) / 2;
    if (middle != begin) {
        merge_sort(array, begin, middle, temp);
        merge_sort(array, middle, end, temp);
        merge(array, begin, middle, end, temp);
    }
}

Bubble Sort

Basic Idea

Description

Implement

Quick Sort

Basic Idea

Description

Implement

Straight Insertion Sort

Basic Idea

Description

Implement

Shell's Sort

Basic Idea

Description

Implement

Using

Simple Selection Sort

Basic Idea

Implement

Heap Sort

Basic Idea

Description

Implement

Using

2-Way Merging Sort

Basic Idea

Description

Implement

Reference