排序算法

// SortBase.h
#pragma once
class SortBase
{
public:
    SortBase() { };
    virtual ~SortBase() { };
    virtual void Show();

protected:
    static constexpr int size = 10;
    //int data[size] = { 5,4,4,1,2,3 };
    int data[size] = { 1,6,9,7,4,5,8,10,2,3 };
};

// SortBase.cpp
#include "pch.h"
#include "SortBase.h"

void SortBase::Show()
{
    for (size_t i = 0; i < size; i++)
    {
        std::cout << data[i] << " ";
    }
    std::cout << std::endl;
}

// Sort.h
#pragma once
#include "SortBase.h"

class Sort : 
    public SortBase
{
public:
    void InsertionSort();
    void BubbleSort();
    void ShellSort();
    void BinaryInsertionSort();
    void SelectionSort();
    void CountingSort();
    void HeapSort();

private:
    void InsertionSortImple(int arr[], int length, int step = 1);
    void BubbleSortImple(int arr[], int length);
    void ShellSortImple(int arr[], int length);
    void BinaryInsertionSortImple(int arr[], int length);
    void SelectionSortImple(int arr[], int length);
    void CountingSortImple(int arr[], int length);
    void HeapSortImple(int arr[], int root, int length);

public:
    Sort() {};
    ~Sort() {};
};

// Sort.cpp
#include "pch.h"
#include "Sort.h"


void Sort::InsertionSort()
{
    InsertionSortImple(data, size, 1);
}

void Sort::BubbleSort()
{
    BubbleSortImple(data, size);
}

void Sort::ShellSort()
{
    ShellSortImple(data, size);
}

void Sort::BinaryInsertionSort()
{
    BinaryInsertionSortImple(data, size);
}

void Sort::SelectionSort()
{
    SelectionSortImple(data, size);
}

void Sort::CountingSort()
{
    CountingSortImple(data, size);
}

void Sort::HeapSort()
{
    for (int i = (size - 1) / 2; i > -1; --i)
    {
        HeapSortImple(data, i, size);
    }
    for (size_t i = 0; i < size; i++)
    {
        std::swap(data[0], data[size - i - 1]);
        HeapSortImple(data, 0, size - i - 1);
    }
}

void Sort::InsertionSortImple(int arr[], int length, int step)
{
    for (size_t i = step; i < length; i += step)
    {
        int pos = i - step;
        int temp = arr[i];
        for (; pos > -1 && temp < arr[pos]; pos -= step)
        {
            arr[pos + step] = arr[pos];
        }
        arr[pos + step] = temp;
    }
}

void Sort::BubbleSortImple(int arr[], int length)
{
    for (size_t i = 0; i < length; i++)
    {
        for (size_t j = 0; j < length - i - 1; j++)
        {
            if (data[j + 1] < data[j])
            {
                std::swap(data[j + 1], data[j]);
            }
        }
    }
}

void Sort::ShellSortImple(int arr[], int length)
{
    for (int step = length / 2; step > 0; step /= 2)
    {
        InsertionSortImple(arr, length, step);
    }
}

void Sort::BinaryInsertionSortImple(int arr[], int length)
{
    for (size_t count = 1; count < length; count++)
    {
        int temp = arr[count];
        int low = 0;
        int high = count - 1;
        for (; low <= high;)
        {
            int mid = (high + low) / 2;
            if (temp < arr[mid])
            {
                high = mid - 1;
            }
            else
            {
                low = mid + 1;
            }
        }
        // 此时 high 为小于 temp 的元素中最大的
        // temp == -1 代表 temp 此时为最小的元素
        int pos = count - 1;
        for (; pos > high; pos--)
        {
            arr[pos + 1] = arr[pos];
        }
        arr[pos + 1] = temp;
    }
}

void Sort::SelectionSortImple(int arr[], int length)
{
    for (size_t i = 0; i < length - 1; i++)
    {
        int pos = i;
        for (size_t j = i + 1; j < length; j++)
        {
            if (arr[j] < arr[pos])
            {
                pos = j;
            }
        }
        std::swap(arr[i], arr[pos]);
    }
}

void Sort::CountingSortImple(int arr[], int length)
{
    int * pCount = new int[length];
    int * pArray = new int[length];
    bool * pFlag = new bool[length];
    for (size_t i = 0; i < length; i++)
    {
        pFlag[i] = true;
        pCount[i] = 0;
        pArray[i] = -1;
    }
    for (size_t i = 0; i < length; i++)
    {
        // 记录数组中有多少个小于 arr[i] 的元素
        for (size_t j = 0; j < length; j++)
        {
            if (arr[j] < arr[i])
            {
                pCount[i]++;
            }
        }
    }
    for (size_t i = 0; i < length; i++)
    {
        if (pFlag[pCount[i]] == true)
        {
            pFlag[pCount[i]] = false;
            pArray[pCount[i]] = arr[i];
        }
        else
        {
            for (; pFlag[pCount[i]] == false; pCount[i]++);
            pFlag[pCount[i]] = false;
            pArray[pCount[i]] = arr[i];
        }
    }
    for (size_t i = 0; i < length; i++)
    {
        arr[i] = pArray[i];
    }
    delete[] pArray;
    delete[] pCount;
    delete[] pFlag;
}

/*          HEAP SAMPLE
 *              0
 *             / \
 *            1   2
 *           / \ / \
 *          3  4 5  6
 *         /(\)
 *        7   8
 *  
 *  IF EXISTS
 *      [LEFT] = [FATHER] * 2 + 1
 *      [RIGHT] = [LEFT + 1] = [FATHER * 2 + 2]
*/

void Sort::HeapSortImple(int arr[], int root, int length)
{
    int temp = arr[root];
    int pos = root;
    for (size_t i = 2 * root + 1; i < length; i *= 2)
    {
        // 选择子节点中最大项
        if (i + 1 < length && arr[i] < arr[i + 1])
        {
            i++;
        }
        // 如果原始节点（参数 arr[root]）小于子节点中最大项，则交换，否则说明堆已经有序，停止循环
        if (temp < arr[i])
        {
            arr[pos] = arr[i];
            pos = i;
        }
        else
        {
            break;
        }
    }
    arr[pos] = temp;
}