Algorithm -- Bubble Sort

柔情只为你懂 2022-06-02 11:23 96阅读 0赞

SortTestHelper.h

#ifndef SELECTIONSORT_SORTTESTHELPER_H
    #define SELECTIONSORT_SORTTESTHELPER_H
    
    #include <iostream>
    #include <ctime>
    #include <cassert>
    
    using namespace std;
    
    
    namespace SortTestHelper {
    
        // 生成有n个元素的随机数组,每个元素的随机范围为[rangeL, rangeR]
        int *generateRandomArray(int n, int rangeL, int rangeR) {
    
            assert(rangeL <= rangeR);
    
            int *arr = new int[n];
    
            srand(time(NULL));
            for (int i = 0; i < n; i++)
                arr[i] = rand() % (rangeR - rangeL + 1) + rangeL;
            return arr;
        }
    
        int *generateNearlyOrderedArray(int n, int swapTimes) {
            int *arr = new int[n];
            for (int i = 0; i < n; ++i) {
                arr[i] = i;
            }
            srand(time(NULL));
            for (int i = 0; i < swapTimes; ++i) {
                int posx = rand() % n;
                int posy = rand() % n;
                swap(arr[posx], arr[posy]);
            }
            return arr;
        }
    
        // 打印arr数组的所有内容
        template<typename T>
        void printArray(T arr[], int n) {
    
            for (int i = 0; i < n; i++)
                cout << arr[i] << " ";
            cout << endl;
    
            return;
        }
    
        template<typename T>
        bool isSorted(T arr[], int N) {
            for (int i = 0; i < N - 1; ++i) {
                if (arr[i] > arr[i + 1]) {
                    return false;
                }
            }
            return true;
        }
    
        template<typename T>
        void testSort(string sortName, void(*sort)(T[], int), T arr[], int N) {
            clock_t startTime = clock();
            sort(arr, N);
            clock_t endTime = clock();
    
            assert(isSorted(arr, N));
            cout << sortName << ":" << double(endTime - startTime) / CLOCKS_PER_SEC << "s" << endl;
            return;
        }
    
        int *copyIntArray(int a[], int n) {
            int *arr = new int[n];
            copy(a, a + n, arr);
            return arr;
        }
    };
    #endif //SELECTIONSORT_SORTTESTHELPER_H

main.cpp

#include <iostream>
    
    #include "SortTestHelper.h"
    #include "SelectionSort.h"
    #include "InsertionSort.h"
    
    using namespace std;
    
    template<typename T>
    void bubbleSort(T arr[], int n) {
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n - 1 - i; j++)
                if (arr[j] > arr[j + 1])
                    swap(arr[j], arr[j + 1]);
    }
    
    template<typename T>
    void bubbleSort1(T arr[], int n) {
        bool swapped;
    
        do{
            swapped = false;
            for( int i = 1 ; i < n ; i ++ )
                if( arr[i-1] > arr[i] ){
                    swap( arr[i-1] , arr[i] );
                    swapped = true;
                }
    
            // 优化, 每一趟Bubble Sort都将最大的元素放在了最后的位置
            // 所以下一次排序, 最后的元素可以不再考虑
            n --;
    
        }while(swapped);
    }
    
    template<typename T>
    void bubbleSort2( T arr[] , int n){
    
        int newn; // 使用newn进行优化
    
        do{
            newn = 0;
            for( int i = 1 ; i < n ; i ++ )
                if( arr[i-1] > arr[i] ){
                    swap( arr[i-1] , arr[i] );
    
                    // 记录最后一次的交换位置,在此之后的元素在下一轮扫描中均不考虑
                    newn = i;
                }
            n = newn;
        }while(newn > 0);
    }
    
    int main() {
        int n = 10000;
        /*int *arr = SortTestHelper::generateNearlyOrderedArray(n, 100);*/
        int *arr = SortTestHelper::generateRandomArray(n, 0, n);
        int *arr2 = SortTestHelper::copyIntArray(arr, n);
        int *arr3 = SortTestHelper::copyIntArray(arr, n);
        int *arr4 = SortTestHelper::copyIntArray(arr, n);
        int *arr5 = SortTestHelper::copyIntArray(arr, n);
        SortTestHelper::testSort("Selection Sort", selectionSort, arr, n);
        SortTestHelper::testSort("Insertion Sort", insertionSort, arr2, n);
        SortTestHelper::testSort("Bubble Sort", bubbleSort, arr3, n);
        SortTestHelper::testSort("Bubble Sort", bubbleSort1, arr4, n);
        SortTestHelper::testSort("Bubble Sort", bubbleSort2, arr5, n);
        delete[] arr;
        delete[] arr2;
        delete[] arr3;
        return 0;
    }