C++ sorting 例子

> Bubble Sort

    #include <iostream>
    
    void swap(int &a, int &b) {
        int temp = a;
        a = b;
        b = temp;
    }
    
    void bubbleSort(int arr[], int size) {
        for (int i = 0; i < size - 1; ++i) {
            for (int j = 0; j < size - i - 1; ++j) {
                // 如果相邻元素逆序，则交换它们
                if (arr[j] > arr[j + 1]) {
                    swap(arr[j], arr[j + 1]);
                }
            }
        }
    }
    
    void printArray(int arr[], int size) {
        for (int i = 0; i < size; ++i) {
            std::cout << arr[i] << " ";
        }
        std::cout << std::endl;
    }
    
    int main() {
        const int size = 6;
        int arr[size] = {64, 25, 12, 22, 11, 1};
    
        std::cout << "原始数组: ";
        printArray(arr, size);
    
        bubbleSort(arr, size);
    
        std::cout << "排序后数组: ";
        printArray(arr, size);
    
        return 0;
    }

## > Insert Sort

#include <iostream>

void insertionSort(int arr[], int size) {
    for (int i = 1; i < size; ++i) {
        int key = arr[i];
        int j = i - 1;

        // 将 arr[0..i-1] 中大于 key 的元素向右移动
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            --j;
        }

        // 将 key 插入到正确的位置
        arr[j + 1] = key;
    }
}

void printArray(int arr[], int size) {
    for (int i = 0; i < size; ++i) {
        std::cout << arr[i] << " ";
    }
    std::cout << std::endl;
}

int main() {
    const int size = 6;
    int arr[size] = {64, 25, 12, 22, 11, 1};

    std::cout << "原始数组: ";
    printArray(arr, size);

    insertionSort(arr, size);

    std::cout << "排序后数组: ";
    printArray(arr, size);

    return 0;
}

> Quick Sort

#include <iostream>

void swap(int &a, int &b) {
    int temp = a;
    a = b;
    b = temp;
}

int partition(int arr[], int low, int high) {
    // 选择最右边的元素作为基准
    int pivot = arr[high];
    int i = low - 1;  // 小于等于基准的元素的最右索引

    for (int j = low; j < high; ++j) {
        // 如果当前元素小于或等于基准，则将其交换到最左边
        if (arr[j] <= pivot) {
            ++i;
            swap(arr[i], arr[j]);
        }
    }

    // 将基准元素放到正确的位置
    swap(arr[i + 1], arr[high]);
    return i + 1;  // 返回基准元素的索引
}

void quickSort(int arr[], int low, int high) {
    if (low < high) {
        // 对数组进行分割，获取基准元素的索引
        int pivotIndex = partition(arr, low, high);

        // 递归地对左右子数组进行排序
        quickSort(arr, low, pivotIndex - 1);
        quickSort(arr, pivotIndex + 1, high);
    }
}

void printArray(int arr[], int size) {
    for (int i = 0; i < size; ++i) {
        std::cout << arr[i] << " ";
    }
    std::cout << std::endl;
}

int main() {
    const int size = 6;
    int arr[size] = {64, 25, 12, 22, 11, 1};

    std::cout << "原始数组: ";
    printArray(arr, size);

    quickSort(arr, 0, size - 1);

    std::cout << "排序后数组: ";
    printArray(arr, size);

    return 0;
}