// C++ program to find maximum element in an array
#include <iostream>
using namespace std;

int findMax(int arr[], int n) {
    int max = arr[0];
    for (int i = 1; i < n; i++) {
        if (arr[i] > max) {
            max = arr[i];
        }
    }
    return max;
}

int main() {
    int arr[] = {64, 34, 25, 12, 22, 11, 90};
    int n = sizeof(arr)/sizeof(arr[0]);
    int max = findMax(arr, n);
    cout << "Maximum element is " << max << endl;
    return 0;
}

//编译命令
// g++ max_element.cpp -o max_element
//运行命令
// ./max_element

#include <iostream>
#include <vector>
using namespace std;

void selectionSort(vector<int>& arr)
{
    int n = arr.size();
    for (int i = 0;i < n-1; i++){
        //从最左边开始，找到最小的数，放到最左边
        int minIndex = i; //已排序和未排序分隔墙位置
        for (int j=i+1;j<n;j++){
            if (arr[j] < arr[minIndex])
            {
                minIndex = j;
            }
        }
        //交换
        if (minIndex != i){
            swap(arr[i], arr[minIndex]);
        }
    }
}

int main()
{
    vector<int> arr = {64, 25, 12, 22, 11,23,78};
    int n = arr.size();
    cout << "排序前的数组: ";
    for (int i=0;i<n;i++){
        cout << arr[i] << " ";
    }
    cout << endl;
    selectionSort(arr);
    cout << "排序后的数组: ";
    for (int i=0;i<n;i++){
        cout << arr[i] << " ";
    }
    cout << endl;
    return 0;
}

def selection_sort(arr):
    n = len(arr)
    for i in range(n):
        min_idx = i
        for j in range(i+1, n):
            if arr[j] < arr[min_idx]:
                min_idx = j
        arr[i], arr[min_idx] = arr[min_idx], arr[i]
    return arr

# 示例
arr = [64, 34, 25, 12, 22, 11, 90]
print("排序前的数组:", arr)
sorted_arr = selection_sort(arr)
print("排序后的数组:", sorted_arr)

// 冒泡排序
#include <iostream>
#include <vector>

void bubbleSort(std::vector<int>& arr)
{
    int n = arr.size();
    for (int i=0;i<n-1;i++) // 外层循环：控制已排序区间
    {
        bool flag = false; // 初始化标志位
        //从末尾开始寻找最小的数
        for (int j = n-1; j > i;j--)// 内层循环：从末尾向前找
        {
            if (arr[j] < arr[j-1]) // 比较相邻元素
            {
                std::swap(arr[j], arr[j-1]);
                flag = true; // 记录交换发生
            }
        }
        if (!flag) // 若没有发生交换，说明已排序区间已有序，则退出循环
            break;
    }
}

int main()
{
    std::vector<int> arr = {64, 25, 12, 22, 11,23,78};
    int n = arr.size();
    std::cout << "排序前的数组: ";
    for (int i=0;i<n;i++){
        std::cout << arr[i] << " ";
    }
    std::cout << std::endl;
    bubbleSort(arr);
    std::cout << "排序后的数组: ";
    for (int i=0;i<n;i++){
        std::cout << arr[i] << " ";
    }
    std::cout << std::endl;
    return 0;
}

// 插入排序
#include <iostream>
#include <vector>
using namespace std;

void insertionSort(vector<int>& arr) {
    int n = arr.size();
    //外循环：已排序区间为[0, i-1]
    for(int i=1; i<n; i++) // 从第二个元素开始
    {
        int key = arr[i]; // 待插入元素
        int j = i-1; // 从i-1开始比较
        //内循环：待插入元素key插入到已排序区间[0, i-1]的正确位置
        while(j>=0 && arr[j]>key) // 找到比key小的元素
        {
            arr[j+1] = arr[j]; // 元素向右移动一位
            j--;
        }
        arr[j+1] = key; // 将该元素插入到正确位置
    }
}
int main()
{
    vector<int> arr = {64, 25, 12, 22, 11,23,78};
    int n = arr.size();
    cout << "排序前的数组: ";
    for (int i=0;i<n;i++){
        cout << arr[i] << " ";
    }
    cout << endl;
    insertionSort(arr);
    cout << "排序后的数组: ";
    for (int i=0;i<n;i++){
        cout << arr[i] << " ";
    }
    cout << endl;
    return 0;
}

#include <iostream>
#include <vector>
using namespace std;

// 希尔排序
void shellSort(vector<int>& arr) {
    int n = arr.size();

    // 初始步长为数组长度的一半
    for (int gap = n / 2; gap > 0; gap /= 2) {
        // 按当前步长对数组进行插入排序
        for (int i = gap; i < n; i++) {
            int temp = arr[i];
            int j = i;

            // 将大于 temp 的元素移动到当前位置
            while (j >= gap && arr[j - gap] > temp) {
                arr[j] = arr[j - gap];
                j -= gap;
            }
            // 将 temp 插入到适当位置
            arr[j] = temp;
        }
    }
}

// 打印数组
void printArray(const vector<int>& arr) {
    for (int num : arr) {
        cout << num << " ";
    }
    cout << endl;
}

int main() {
    vector<int> arr = {64, 25, 12, 22, 11, 23, 78};

    cout << "排序前的数组：";
    printArray(arr);

    // 调用希尔排序
    shellSort(arr);

    cout << "排序后的数组：";
    printArray(arr);

    return 0;
}

#include <iostream>
#include <vector>
using namespace std;

/**
 * @brief 合并两个已排序的子数组
 * 
 * @param arr 原数组，包含需要排序的元素
 * @param left 左子数组的起始索引
 * @param mid 左子数组的结束索引（右子数组的起始索引为 mid + 1）
 * @param right 右子数组的结束索引
 */
void merge(vector<int>& arr, int left, int mid, int right)
{
    int i = left, j = mid + 1; // i指向左子数组的起始，j指向右子数组的起始
    int k = 0; // 临时数组的索引
    vector<int> temp(right - left + 1); // 临时数组，用于存储合并后的结果

    // 比较左右子数组的元素，将较小的元素加入临时数组
    while (i <= mid && j <= right)
    {
        if (arr[i] <= arr[j])
        {
            temp[k++] = arr[i++];
        }
        else
        {
            temp[k++] = arr[j++];
        }
    }

    // 将左子数组剩余元素加入临时数组
    while (i <= mid)
    {
        temp[k++] = arr[i++];
    }

    // 将右子数组剩余元素加入临时数组
    while (j <= right)
    {
        temp[k++] = arr[j++];
    }

    // 将临时数组中的元素复制回原数组的对应位置
    for (int m = 0; m < temp.size(); m++)
    {
        arr[left + m] = temp[m];
    }
}

/**
 * @brief 归并排序主函数（递归分治）
 * 
 * @param arr 原数组，包含需要排序的元素
 * @param left 当前子数组的起始索引
 * @param right 当前子数组的结束索引
 */
void mergeSort(vector<int>& arr, int left, int right)
{
    if (left < right)
    {
        int mid = left + (right - left) / 2; // 防止整数溢出的计算方式

        // 递归排序左半部分
        mergeSort(arr, left, mid);

        // 递归排序右半部分
        mergeSort(arr, mid + 1, right);

        // 合并左右两部分
        merge(arr, left, mid, right);
    }
}

/**
 * @brief 主函数，测试归并排序
 */
int main()
{
    vector<int> arr = {64, 25, 12, 22, 11, 23, 78}; // 测试数组
    int n = arr.size();

    // 输出排序前的数组
    cout << "排序前的数组: ";
    for (int i = 0; i < n; i++)
    {
        cout << arr[i] << " ";
    }
    cout << endl;

    // 调用归并排序函数
    mergeSort(arr, 0, n - 1);

    // 输出排序后的数组
    cout << "排序后的数组: ";
    for (int i = 0; i < n; i++)
    {
        cout << arr[i] << " ";
    }
    cout << endl;

    return 0;
}

FUNCTION MaxSubarray(A, low, high):
    IF low == high:                  // 基本情况：只有一个元素
        RETURN A[low]

    mid = (low + high) / 2           // 计算中点

    // 递归求解左右部分的最大子数组和
    leftSum = MaxSubarray(A, low, mid)
    rightSum = MaxSubarray(A, mid + 1, high)

    // 求解跨越中间部分的最大子数组和
    crossSum = MaxCrossingSubarray(A, low, mid, high)

    // 返回三者中的最大值
    RETURN max(leftSum, rightSum, crossSum)

// 计算跨越中间部分的最大子数组和
FUNCTION MaxCrossingSubarray(A, low, mid, high):
    // 从中间向左计算最大和
    leftMaxSum = -∞
    sum = 0
    FOR i FROM mid DOWNTO low:
        sum = sum + A[i]
        IF sum > leftMaxSum:
            leftMaxSum = sum

    // 从中间向右计算最大和
    rightMaxSum = -∞
    sum = 0
    FOR i FROM mid + 1 TO high:
        sum = sum + A[i]
        IF sum > rightMaxSum:
            rightMaxSum = sum

    // 返回跨越中点的最大和
    RETURN leftMaxSum + rightMaxSum

#include <iostream>
#include <vector>
using namespace std;

// 调整堆，使得以i为根的子树满足最大堆性质
void heapify(vector<int>& arr, int n, int i) {
    int largest = i; // 假设根节点是最大的
    int left = 2 * i + 1; // 左子节点的索引
    int right = 2 * i + 2; // 右子节点的索引

    // 如果左子节点比根节点大，则更新最大值
    if (left < n && arr[left] > arr[largest]) {
        largest = left;
    }

    // 如果右子节点比当前最大值还大，则更新最大值
    if (right < n && arr[right] > arr[largest]) {
        largest = right;
    }

    // 如果最大值不是根节点，交换根节点和最大子节点
    if (largest != i) {
        swap(arr[i], arr[largest]);

        // 递归调整堆，保证交换后的子树仍然满足堆的性质
        heapify(arr, n, largest);
    }
}

// 堆排序的主函数
void heapSort(vector<int>& arr) {
    int n = arr.size();

    // 1. 构建最大堆
    // 从最后一个非叶子节点开始调整堆
    for (int i = n / 2 - 1; i >= 0; i--) {
        heapify(arr, n, i);
    }

    // 2. 一个一个地将最大元素（根节点）移到数组的末尾，并重新调整堆
    for (int i = n - 1; i >= 1; i--) {
        // 交换当前最大元素与最后一个元素
        swap(arr[0], arr[i]);

        // 调整剩余的部分，恢复堆的性质
        heapify(arr, i, 0);
    }
}

// 打印数组
void printArray(const vector<int>& arr) {
    for (int i : arr) {
        cout << i << " ";
    }
    cout << endl;
}

int main() {
    vector<int> arr = {64, 25, 12, 22, 11,23,78};

    cout << "排序前的数组：";
    printArray(arr);

    // 调用堆排序函数
    heapSort(arr);

    cout << "排序后的数组：";
    printArray(arr);

    return 0;
}

QUICKSORT(A, p, r)
    if p < r
        q = PARTITION(A, p, r)
        QUICKSORT(A, p, q-1)
        QUICKSORT(A, q+1, r)

PARTITION(A, p, r)
    x = A[r]
    i = p - 1
    for j = p to r - 1
        if A[j] <= x
            i = i + 1
            swap A[i] and A[j]
    swap A[i+1] and A[r]
    return i+1

#include <iostream>
#include <vector>
using namespace std;

// 分区操作，将基准元素放置在正确位置，并返回该位置的索引
int partition(vector<int>& arr, int low, int high) {
    int pivot = arr[high];  // 选择最后一个元素作为基准
    int i = low - 1;  // i表示小于基准元素的部分的最后一个元素的索引

    // 遍历数组，找到小于基准元素的元素并交换
    for (int j = low; j < high; j++) {
        if (arr[j] <= pivot) {
            i++;  // 小于基准的部分右移
            swap(arr[i], arr[j]);  // 交换元素
        }
    }

    // 将基准元素放到正确的位置（即它应该位于索引i+1的位置）
    swap(arr[i + 1], arr[high]);

    // 返回基准元素的位置
    return i + 1;
}

// 快速排序主函数
void quickSort(vector<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(const vector<int>& arr) {
    for (int num : arr) {
        cout << num << " ";
    }
    cout << endl;
}

int main() {
    vector<int> arr = {64, 25, 12, 22, 11,23,78};

    cout << "排序前的数组：";
    printArray(arr);

    // 调用快速排序
    quickSort(arr, 0, arr.size() - 1);

    cout << "排序后的数组：";
    printArray(arr);

    return 0;
}

COUNTING-SORT(A,B,k)
    C[0..k] := 0 // 计数数组初始化为0
    for i = 1 to A.length do
        C[A[i]] := C[A[i]] + 1 // 统计每个元素的出现次数
    for i = 1 to k do
        C[i] := C[i] + C[i-1] // 计算每个元素的排序位置
    for i = A.length downto 1 do // 反向遍历数组
        B[C[A[i]]] := A[i] // 将元素放入输出数组
        C[A[i]] := C[A[i]] - 1 // 元素计数减1
return B

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

// 计数排序函数
void countingSort(vector<int>& arr) {
    if (arr.empty()) return; // 如果数组为空，直接返回

    // 找出数组中最大和最小的元素
    int maxVal = *max_element(arr.begin(), arr.end());
    int minVal = *min_element(arr.begin(), arr.end());

    // 创建计数数组，大小为范围的大小（最大值 - 最小值 + 1）
    int range = maxVal - minVal + 1;
    vector<int> count(range, 0); // 初始化计数数组
    vector<int> output(arr.size()); // 输出排序后的数组

    // 统计每个元素的出现次数
    for (int num : arr) {
        count[num - minVal]++;
    }

    // 统计累加频次（将计数转换为位置）
    for (int i = 1; i < range; i++) {
        count[i] += count[i - 1];
    }

    // 将元素放回输出数组，根据累积的频次找到正确位置
    for (int i = arr.size() - 1; i >= 0; i--) {
        output[count[arr[i] - minVal] - 1] = arr[i];
        count[arr[i] - minVal]--;
    }

    // 将排序后的结果拷贝回原数组
    arr = output;
}

// 打印数组
void printArray(const vector<int>& arr) {
    for (int num : arr) {
        cout << num << " ";
    }
    cout << endl;
}

int main() {
    vector<int> arr = {64, 25, 12, 22, 11,23,78};

    cout << "排序前的数组：";
    printArray(arr);

    // 调用计数排序
    countingSort(arr);

    cout << "排序后的数组：";
    printArray(arr);

    return 0;
}

RADIX-SORT(A,d)
    for i = 1 to d
        use a stable sorting algorithm to sort A according to the i-th digit
    return A

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

// 计数排序，用于基数排序
void countingSortForRadix(vector<int>& arr, int exp) {
    int n = arr.size();
    vector<int> output(n);       // 用于存储排序后的结果
    vector<int> count(10, 0);   // 基数为10，所以计数数组大小为10

    // 根据当前位（exp），统计每个数字出现的次数
    for (int i = 0; i < n; i++) {
        int digit = (arr[i] / exp) % 10; // 提取当前位的数字
        count[digit]++;
    }

    // 更新计数数组，计算累积位置
    for (int i = 1; i < 10; i++) {
        count[i] += count[i - 1];
    }

    // 按当前位的数字，将元素放入正确位置
    for (int i = n - 1; i >= 0; i--) {
        int digit = (arr[i] / exp) % 10; 
        output[count[digit] - 1] = arr[i]; 
        count[digit]--;  // 更新计数数组
    }

    // 将排序结果复制回原数组
    for (int i = 0; i < n; i++) {
        arr[i] = output[i];
    }
}

// 基数排序主函数
void radixSort(vector<int>& arr) {
    // 找到数组中的最大值，确定最高位数
    int maxVal = *max_element(arr.begin(), arr.end());

    // 从最低有效位（exp = 1, 即个位）开始，一直到最高位
    for (int exp = 1; maxVal / exp > 0; exp *= 10) {
        countingSortForRadix(arr, exp); // 按当前位进行计数排序
    }
}

// 打印数组
void printArray(const vector<int>& arr) {
    for (int num : arr) {
        cout << num << " ";
    }
    cout << endl;
}

int main() {
    vector<int> arr = {170, 45, 75, 90, 802, 24, 2, 66};

    cout << "排序前的数组：";
    printArray(arr);

    // 调用基数排序
    radixSort(arr);

    cout << "排序后的数组：";
    printArray(arr);

    return 0;
}

// 桶排序（使用插入排序进行桶内排序）
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

// 插入排序函数，用于桶内排序
void insertionSort(vector<float>& bucket) {
    for (size_t i = 1; i < bucket.size(); i++) {
        float key = bucket[i];
        int j = i - 1;
        // 将 key 插入到已排序部分
        while (j >= 0 && bucket[j] > key) {
            bucket[j + 1] = bucket[j];
            j--;
        }
        bucket[j + 1] = key;
    }
}

// 桶排序主函数
void bucketSort(vector<float>& arr) {
    int n = arr.size();
    if (n <= 1) return; // 如果数组大小为 1 或 0，无需排序

    // 创建 n 个桶（每个桶是一个 vector）
    vector<vector<float>> buckets(n);

    // 将元素分配到桶中
    float maxVal = *max_element(arr.begin(), arr.end());
    float minVal = *min_element(arr.begin(), arr.end());
    float range = maxVal - minVal;

    for (int i = 0; i < n; i++) {
        int bucketIndex = (arr[i] - minVal) / range * (n - 1); // 计算桶索引
        buckets[bucketIndex].push_back(arr[i]); // 将元素放入桶中
    }

    // 对每个桶内进行排序
    for (int i = 0; i < n; i++) {
        insertionSort(buckets[i]); // 对桶内元素排序
    }

    // 合并所有桶中的元素到原数组
    int index = 0;
    for (int i = 0; i < n; i++) {
        for (float value : buckets[i]) {
            arr[index++] = value;
        }
    }
}

// 打印数组
void printArray(const vector<float>& arr) {
    for (float num : arr) {
        cout << num << " ";
    }
    cout << endl;
}

int main() {
    vector<float> arr = {0.897, 0.565, 0.656, 0.123, 0.665, 0.343};

    cout << "排序前的数组：";
    printArray(arr);

    // 调用桶排序
    bucketSort(arr);

    cout << "排序后的数组：";
    printArray(arr);

    return 0;
}