十大排序算法C++實作

#include <iostream>
#include <memory>
#include <functional>
#include <string.h>
#include <vector>

void print(int *data, int size)
{
    for (int i = 0; i < size; i++) {
        std::cout << data[i] << " ";
    }
    std::cout << std::endl;
    return;
}

//O(n^2) stable
void bubbleSort(int *data, int size)
{
   for (int i = 0; i < size - 1; ++i) {
       for (int j = 0; j < size - 1 - i; ++j) {
           if (data[j] > data[j + 1]) { // must >, not >=
               int tmp = data[j + 1];
               data[j + 1] = data[j];
               data[j] = tmp;
           }
       }
   }
   return;
}

//O(n^2) unstable
void selectSort(int *data, int size)
{
    for (int i = 0; i < size - 1; ++i) {
        int maxIndex = 0;
        for (int j = 1; j < size - i; ++j) {
            if (data[j] > data[maxIndex]) {
                maxIndex = j;
            }
        }
        int tmp = data[maxIndex];
        data[maxIndex] = data[size - 1 - i];
        data[size - 1 - i] = tmp;
    }
    return;
}

//O(n^2) stable
//建構有序的序列，将無序元素依次插入到有序序列中，從右向左周遊有序序列，直到找到合适位置進行插入
void insertSort(int *data, int size)
{
    for (int i = 1; i < size; ++i) {
        int tmp = data[i];
        int j = i - 1;
        while (j >= 0 && tmp < data[j]) { //must < , not <=
            data[j + 1] = data[j];
            j--;
        }
        data[j + 1] = tmp;
    }
    return;
}

//O(n(logn)^2) unstable optimize for insertSort
void shellSort(int *data, int size)
{
    for (int gap = size /2; gap > 0; gap /= 2) {
        for (int i = gap; i < size; ++i) {
            int j = i;
            int tmp = data[j];
            while (j - gap >= 0 && tmp < data[j - gap]) {
                data[j] = data[j - gap];
                j -= gap;
            }
            data[j] = tmp;
        } 
    }
    return;
}

//O(nlogn) stable
void mergeSort(int *data, int size)
{
    int *tmp = new int[size];
    auto merge = [data, size, tmp](int left, int mid, int right) {
        int i = left;
        int j = mid + 1;
        int t = 0;
        while (i <= mid && j <= right) {
            if (data[i] <= data[j]) {
                tmp[t++] = data[i++];
            } else {
                tmp[t++] = data[j++];
            }
        }

        while (i <= mid) {
            tmp[t++] = data[i++];
        }

        while (j <= right) {
            tmp[t++] = data[j++];
        }

        t = 0;

        while (left <= right) {
            data[left++] = tmp[t++];
        }

        return;
    };

    std::function<void(int, int)> sort = [&sort, &merge](int left, int right) {
        if (left < right) {
            int mid = (left + right) / 2;
            sort(left, mid);
            sort(mid + 1, right);
            merge(left, mid, right);
        }
    };

    // const auto& sort = [&merge](int left, int right) {
    //     const auto& sortImpl = [&merge](auto &&self, int left, int right) ->void{  //c++14 must ->void, or compile error
    //         if (left < right) {
    //             int mid = (left + right) / 2;
    //             self(self, left, mid);
    //             self(self, mid + 1, right);
    //             merge(left, mid, right);
    //         }
    //     };
    //     sortImpl(sortImpl, left, right);
    // };
    
    sort(0, size - 1);

    return;
}


//O(nlogn) unstable
//大根堆(大根樹 + 完全二叉樹)
void heapSort(int *data, int size)
{
    //O(nlogn)
    auto heapInitialize = [] (int *data, int size) {
        // 從最後一個父節點開始建堆
        for (int root = size / 2 - 1; root >= 0; root--) {
            int rootElement = data[root];
            int child = root * 2 + 1;
            while (child <= size - 1) {
                if (child < size - 1 && data[child] < data[child + 1]) {
                    child++;
                }
                if (rootElement >= data[child]) {
                    break;
                }
                data[(child - 1) / 2] = data[child];
                child = child * 2 + 1;
            }
            data[(child - 1) / 2] = rootElement;
        }
    };

    auto heapPop = [] (int *data, int size) {
        int lastElement = data[size - 1];
        int current = 0;
        int child = 1;
        
        while (child <= size - 1) {
            if (child < size - 1 && data[child] < data[child + 1]) {
                child++;
            }
            if (lastElement >= data[child]) {
                break;
            }
            data[(child - 1) / 2] = data[child];
            current = child;
            child = child * 2 + 1;
        }
        data[current] = lastElement;
    };

    heapInitialize(data, size);
    for (int i = 0; i < size - 1; i++) {
        int tmp = data[0]; //第一個元素--最大元素
        heapPop(data, size - i);
        data[size - 1 - i] = tmp;
    }
    return;
}

//O(nlogn) unstable
void quickSort(int *data, int size)
{
    //find pivot position
    auto partition = [](int *data, int low, int high) {
        int pivot = data[low];
        while (low < high) {
            while (low < high && data[high] >= pivot) { //從右開始找到第一個小于基準值的
                high--;
            }
            data[low] = data[high];
            while (low < high && data[low] <= pivot) {
                low++;
            }
            data[high] = data[low];
        }
        data[low] = pivot;
        return low;
    };

    std::function<void(int*, int, int)> quickSortImpl = [&partition, &quickSortImpl](int *data, int low, int high) {
        if (low < high) {
            int pivotPosition = partition(data, low, high);
            quickSortImpl(data, low, pivotPosition - 1);
            quickSortImpl(data, pivotPosition + 1, high);
        }
    };

    quickSortImpl(data, 0, size - 1);
    return;
}


//O(n + m) stable
void countSort(int *data, int size)
{
    int maxValue = data[0];
    int minValue = data[0];
    for (int i = 1; i < size; i++) {
        if (data[i] > maxValue) {
            maxValue = data[i];
        }
        if (data[i] < minValue) {
            minValue = data[i];
        }
    }

    int bucketSize = maxValue - minValue + 1;
    std::vector<int> count(bucketSize, 0);
    for (int i = 0; i < size; i++) {
        count[data[i] - minValue]++;
    }

    for (int i = 1; i < bucketSize; i++) {
        count[i] = count[i - 1] + count[i];
    }

    std::vector<int> tmp(size, 0);
    for (int i = size - 1; i >= 0; i--) {
        int k = data[i] - minValue;
        tmp[count[k] - 1] = data[i];
        count[k]--;
    }

    memcpy(data, tmp.data(), size * sizeof(int));

    return;
}

// O(n) stable
void bucketSort(int *data, int size)
{
    const int BUCKET = 5;
    int maxValue = data[0];
    int minValue = data[0];
    for (int i = 1; i < size; i++) {
        if (data[i] > maxValue) {
            maxValue = data[i];
        }
        if (data[i] < minValue) {
            minValue = data[i];
        }
    }

    //生成桶
    int bucketNum = (maxValue - minValue) / BUCKET + 1;
    std::vector<std::vector<int>> bucket(bucketNum); //每個桶裡也是一個數組

    //按範圍進行入桶
    for (int i = 0; i < size; i++) {
        bucket[(data[i] - minValue) / BUCKET].push_back(data[i]);
    }

    //每個桶内進行插入排序
    for (int i = 0; i < bucketNum; i++) {
        insertSort(bucket[i].data(), bucket[i].size());
    }

    //桶合并
    int index = 0;
    for (int i = 0; i < bucketNum; i++) {
        for (const auto &s : bucket[i]) {
            data[index++] = s;
        }
    }

    return;
}

//O(n * k) stable
//桶的個數确定：10個， 排序次數确定：最大元素位數
void radixSort(int *data, int size)
{
    auto maxBit = [data, size]()->int {
        int maxData = data[0];
        for (int i = 0; i < size; i++) {
            if (maxData < data[i]) {
                maxData = data[i];
            }
        }
        int bits = 1;
        while (maxData /= 10) {
            ++bits;
        }
        return bits;
    };

    int radix = 1;
    int maxbit = maxBit();
    std::vector<int> tmp(size, 0); //臨時數組，用于存儲每次按某位排序的結果
    for (int i = 0; i < maxbit; i++) {
        std::vector<int> count(10, 0);
        //統計每個桶裡面的元素個數
        for (int j = 0; j < size; j++) {
            count[(data[j] / radix) % 10]++;
        }

        //累加桶的計數,用來确定每個元素的在數組中的位置
        for (int j = 1; j < 10; j++) {
           count[j] = count[j - 1] + count[j];
        }

        //根據count将資料進行排序收集到tmp
        for (int j = size - 1; j >= 0; j--) {
            int k = (data[j] / radix) % 10;
            tmp[count[k] - 1] = data[j];
            count[k]--;
        }

        //資料寫會data, 為下一次排序作準備
        memcpy(data, tmp.data(), size * sizeof(int));
        // for (int j = 0; j < size; j++) {
        //     data[j] = tmp[j];
        // }
        radix *= 10;
    }
    return;
}


int main(void)
{
    int data[] = {1, 4, 9, 2, 9, 24, 100, 3, 389, 22};
    const int size = sizeof(data) / sizeof(int);
    // bubbleSort(data, size);
    // print(data, size);

    // selectSort(data, size);
    // print(data, size);

    // insertSort(data, size);
    // print(data, size);

    // shellSort(data, size);
    // print(data, size);

    // mergeSort(data, size);
    // print(data, size);

    // heapSort(data, size);
    // print(data, size);

    // quickSort(data, size);
    // print(data, size);

    // countSort(data, size);
    // print(data, size);

    // bucketSort(data, size);
    // print(data, size);

    radixSort(data, size);
    print(data, size);
 
    return 0;
}
十大排序算法C++實作

繼續閱讀

Ubuntu14.04 LTS下安裝mongodb

[轉]九大排序算法——C語言實作及詳解

httpd服務的部署、啟動、配置和簡單優化一、部署二、啟動三、配置檔案

配置網頁内容通路

手動安裝Intel network I217-LM網卡的Linux驅動

禁止ubuntu系統彈出報錯界面

Ubuntu Linux下Apache的配置檔案

[C++學習曆程]基礎部分 C++中的函數學習

使用遞減運算符在循環中按遞減順序列印10到0之間的整數

指針，常量和類型别名

VS C++常見問題集錦1.在Vs中編C出現這兩個錯誤是什麼原因？錯誤1：error LNK2005: _main 已經在 *** 中定義

samba伺服器的功能

【Linux】UDP廣播封包接收速率問題

Linux裝置模型（中）之上層容器

PowerPC平台 Linux移植三
