实现冒泡、插入、选择排序；快速排序。

sort_algorithm_main.cpp

#include <iostream>
#include "NSquareSort.h"
#include "NSort.h"
#include <ctime>
#include <cstdlib> //for rand
const int ARRAY_LENGTH = 100000;
using namespace std;

int main() {

    srand(time(nullptr));
    int* p_arr = new int[ARRAY_LENGTH];
    for(int i = 0; i < ARRAY_LENGTH; ++i){
        p_arr[i] = rand() % 100;
        cout << p_arr[i] << " ";
    }
    cout << endl;
    NSquareSort n_square_sort;
    NSort n_sort;
    clock_t start = clock();
    n_sort.QuickSort(p_arr, 0, ARRAY_LENGTH - 1);    // length -> time: 115 ms
//    n_square_sort.BubbleSort(p_arr, ARRAY_LENGTH);  //length --> time: 28097 ms
//    n_square_sort.InsertSort(p_arr, ARRAY_LENGTH);  //length --> time:6768 ms
//    n_square_sort.SelectSort(p_arr, ARRAY_LENGTH);  //length-->time:10639 ms
    clock_t end = clock();
    clock_t dur = end - start;
    cout << "time: " << 1000 * (dur) / CLOCKS_PER_SEC << endl;
    for(int i = 0; i < ARRAY_LENGTH; ++i) {
        cout << p_arr[i] << " ";
    }
    cout << endl;

    delete [] p_arr;

    return 0;
}

sort_algorithm_NSort.cpp

//
// Created by sanjay on 2020/2/21.
//

#include "NSort.h"

void NSort::QuickSort(int *array, int l, int r){
    if(l  < r) {
        int i = l, j = r, pivot = array[l];
        while (i < j) {
            while (i < j && array[j] > pivot) {
                --j;
            }
            if (i < j) {
                array[i++] = array[j];
            }
            while (i < j && array[i] <= pivot) {
                ++i;
            }
            if (i < j) {
                array[j--] = array[i];
            }
        }
        array[i] = pivot;   // 把一个固定了
        QuickSort(array, l, i - 1);
        QuickSort(array, i + 1, r);
    }

}

sort_algorithm_NSort.h

//
// Created by sanjay on 2020/2/21.
//

#ifndef SORT_ALGORITHM_NSORT_H
#define SORT_ALGORITHM_NSORT_H


class NSort {
public:
    void QuickSort(int array[], int, int);
};


#endif //SORT_ALGORITHM_NSORT_H

sort_algorithm_NSquareSort.cpp

//
// Created by sanjay on 2020/2/20.
//

#include "NSquareSort.h"

void NSquareSort::BubbleSort(int array[], int size) {
    if(size <= 1){
        return;
    }
    for(int i = 0; i < size - 1; ++i) {
        bool flag = false;
        for (int j = 0; j < size - 1 - i; ++j) {
            if (array[j] > array[j + 1]) {
                int temp = array[j];
                array[j] = array[j + 1];
                array[j + 1] = temp;
                flag = true;
            }
        }
        if(!flag) {
            break;
        }
    }
}

void NSquareSort::InsertSort(int *array, int size) {
    if (size <= 1) return;
    for(int i = 1; i < size; ++i) {
        int value = array[i];
        int j = i - 1;
        for(; j >= 0; --j) {
            if(array[j] > value) {
                array[j + 1] = array[j];
            }
            else {
                break;
            }
        } // for
        array[j + 1] = value;
    }

}

void NSquareSort::swap_number(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

void NSquareSort::SelectSort(int *array, int size) {
    // 选择排序
    if (size <= 1) {
        return;
    }
    for(int i = 0; i < size - 1; ++i) {
        int min = i;
        for(int j = i + 1; j < size; ++j) {
            if(array[min] > array[j]) {
                min = j;
            }
        }
        swap_number(&array[min], &array[i]);
    }
}

sort_algorithm_NSquareSort.h

//
// Created by sanjay on 2020/2/20.
//

#ifndef SORT_ALGORITHM_NSQUARESORT_H
#define SORT_ALGORITHM_NSQUARESORT_H


class NSquareSort {
public:
    void BubbleSort(int array[], int size);
    void InsertSort(int array[], int size);
    void SelectSort(int array[], int size);

private:
    void swap_number(int*, int*);
};


#endif //SORT_ALGORITHM_NSQUARESORT_H