def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        for j in range(0, n-i-1):
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]
    return arr

def insertion_sort(arr):
    n = len(arr)
    for i in range(1, n):
       key = arr[i]
       j = i-1
       while j >= 0 and key < arr[j]:
           arr[j+1] = arr[j]
           j -= 1
       arr[j+1] = key
    return arr

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

def merge_sort(arr):
    if len(arr) > 1:
       mid = len(arr) // 2
       left_half = arr[:mid]
       right_half = arr[mid:]

       merge_sort(left_half)
       merge_sort(right_half)

       i = j = k = 0
       while i < len(left_half) and j < len(right_half):
           if left_half[i] < right_half[j]:
               arr[k] = left_half[i]
               i += 1
           else:
               arr[k] = right_half[j]
               j += 1
           k += 1

       while i < len(left_half):
           arr[k] = left_half[i]
           i += 1
           k += 1

       while j < len(right_half):
           arr[k] = right_half[j]
           j += 1
           k += 1
    return arr 

def quick_sort(arr):
   if len(arr) > 1:
       pivot = arr[len(arr) // 2]
       left = [x for x in arr if x < pivot]
       middle = [x for x in arr if x == pivot]
       right = [x for x in arr if x > pivot]
       return quick_sort(left) + middle + quick_sort(right)
   else:
       return arr

arr = [64, 34, 25, 12, 22, 11, 90]

print("原始数组:")
print(arr)

print("\n冒泡排序:")
print(bubble_sort(arr))

print("\n插入排序:")
print(insertion_sort(arr))

print("\n选择排序:")
print(selection_sort(arr))

print("\n归并排序:")
print(merge_sort(arr))

print("\n快速排序:")
print(quick_sort(arr))

#include <iostream>
#include <vector>

using namespace std;

void bubble_sort(vector<int> &arr)
{
    int n = arr.size();
    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < n - i - 1; ++j)
        {
            if (arr[j] > arr[j + 1])
            {
                swap(arr[j], arr[j + 1]);
            }
        }
    }
}

void insertion_sort(vector<int> &arr)
{
    int n = arr.size();
    for (int i = 1; i < n; ++i)
    {
        int key = arr[i];
        int j = i - 1;
        while (j >= 0 && key < arr[j])
        {
            arr[j + 1] = arr[j];
            j -= 1;
        }
        arr[j + 1] = key;
    }
}

void selection_sort(vector<int> &arr)
{
    int n = arr.size();
    for (int i = 0; i < n; ++i)
    {
        int min_idx = i;
        for (int j = i + 1; j < n; ++j)
        {
            if (arr[j] < arr[min_idx])
            {
                min_idx = j;
            }
        }
        swap(arr[i], arr[min_idx]);
    }
}

void merge_sort(vector<int> &arr)
{
    if (arr.size() > 1)
    {
        int mid = arr.size() / 2;
        vector<int> left_half(arr.begin(), arr.begin() + mid);
        vector<int> right_half(arr.begin() + mid, arr.end());

        merge_sort(left_half);
        merge_sort(right_half);

        int i = 0, j = 0, k = 0;
        while (i < left_half.size() && j < right_half.size())
        {
            if (left_half[i] < right_half[j])
            {
                arr[k++] = left_half[i++];
            }
            else
            {
                arr[k++] = right_half[j++];
            }
        }

        while (i < left_half.size())
        {
            arr[k++] = left_half[i++];
        }

        while (j < right_half.size())
        {
            arr[k++] = right_half[j++];
        }
    }
}

int partition(vector<int> &nums, int left, int right)
{
    int pivot = nums[left];
    int i = left + 1;
    int j = right;

    while (true)
    {
        while (i <= j && nums[i] < pivot)
            ++i;
        while (i <= j && nums[j] >= pivot)
            --j;
        if (i > j)
            break;
        swap(nums[i++], nums[j--]);
    }
    swap(nums[left], nums[j]);
    return j;
}

void quickSort(vector<int> &nums, int left, int right)
{
    if (left >= right)
        return;
    int pivotIndex = partition(nums, left, right);
    quickSort(nums, left, pivotIndex - 1);
    quickSort(nums, pivotIndex + 1, right);
}

void quick_sort(vector<int> &arr)
{
    quickSort(arr, 0, arr.size() - 1);
}

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

    cout << "原始数组:" << endl;
    for (int i : arr)
    {
        cout << i << " ";
    }
    cout << endl;

    bubble_sort(arr);
    cout << "冒泡排序:" << endl;
    for (int i : arr)
    {
        cout << i << " ";
    }
    cout << endl;

    insertion_sort(arr);
    cout << "插入排序:" << endl;
    for (int i : arr)
    {
        cout << i << " ";
    }
    cout << endl;

    selection_sort(arr);
    cout << "选择排序:" << endl;
    for (int i : arr)
    {
        cout << i << " ";
    }
    cout << endl;

    merge_sort(arr);
    cout << "归并排序:" << endl;
    for (int i : arr)
    {
        cout << i << " ";
    }
    cout << endl;

    quick_sort(arr);
    cout << "快速排序:" << endl;
    for (int i : arr)
    {
        cout << i << " ";
    }
    cout << endl;
}