排序算法

一.插入排序(Insertion Sort)
插入排序，如打扑克时的理牌一样，左手为空，从牌堆摸牌，将摸到的牌从右往左对比，放到比其小的牌的右边。
代码示例:

#include<iostream>
using namespace std;
int main()
{
    int a[10];
    for (int i = 0; i < 10; i++) {
        cin >> a[i];
    }
    //4 5 2 8 1 9 3 7 6 0 a数组的key
    //0 1 2 3 4 5 6 7 8 9 i下标
    for (int i = 2; i < 10; i++) {
        int key = a[i];//选定一个数将其与左边的数一一对比
        int j = i - 1;
        while (j >= 0 && a[j] < key) //如果比选定的数字大则将其右移
        {
            a[j + 1] = a[j];
            j--;
        }
        a[j + 1] = key;
    }
    for (int i = 0; i < 10; i++) {
        cout << a[i] << " ";
    }
    return 0;
}

二.选择排序(Selection sort)
遍历数组，找到最小的数，交换位置，让最小的数排在前面
代码示例:

#include<iostream>
using namespace std;
int main()
{
    int a[10];
    for (int i = 0; i < 10; i++)cin >> a[i];

    for (int i = 0; i < 10; i++) {
        int temp = i;
        for (int j = i; j < 10; j++) {
            if (a[j] < a[temp]) {
                temp = j;
            }
        }
        swap(a[i], a[temp]);
    }
    for (int i = 0; i < 10; i++) {
        cout << a[i] << " ";
    }

    return 0;
}

三.冒泡排序(Bubble Sort)
每次就行两个数之间的比较,将大(小)的数放在右边,每次循环更大(小)的数会像泡泡一样飘到最右边.
代码示例:

#include<iostream>
using namespace std;
int main()
{
    // 定义包含10个元素的整数数组
    int a[10];
    for (int i = 0; i < 10; i++) {
        // 从标准输入流读取用户输入的整数，并存储到数组a中
        cin >> a[i];
    }

    // 使用冒泡排序算法对数组a进行排序
    for (int i = 0; i < 10; i++) {
        for (int j = i + 1; j < 10; j++) {
            // 如果当前元素大于后续元素，则交换它们的位置
            if (a[i] > a[j]) {
                int temp=a[i];
                a[i] = a[j];
                a[j] = temp;
            }
        }
    }

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

    // 返回程序运行成功状态
    return 0;
}

四.合并排序(Merge sort)
利用递归,将原数组拆分,接着合并的同时排序,如图

代码示例:

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

// 归并排序的辅助函数，用于将两个已排序的子数组合并为一个排序数组
void merge(vector<int>& a, int l, int mid, int r) {
    int nx = mid - l + 1;  // 计算第一个子数组的大小
    int ny = r - mid;      // 计算第二个子数组的大小
    vector<int>P(nx);      // 创建第一个子数组
    vector<int>Q(ny);      // 创建第二个子数组

    // 将元素复制到临时数组P和Q中
    for (int i = 0; i < nx; i++) {
        P[i] = a[l + i];
    }
    for (int i = 0; i < ny; i++) {
        Q[i] = a[mid + 1 + i];
    }

    int i = 0, j = 0, k = l;
    // 合并两个子数组
    while (i < nx && j < ny) {
        if (P[i] <= Q[j]) {
            a[k] = P[i];
            i++;
        }
        else {
            a[k] = Q[j];
            j++;
        }
        k++;
    }

    // 将剩余的元素复制回原数组
    while (i < nx) {
        a[k] = P[i];
        i++;
        k++;
    }
    while (j < ny) {
        a[k] = Q[j];
        j++;
        k++;
    }
}

// 归并排序算法的主要逻辑，递归地将数组分为较小的数组，并调用merge函数进行合并
void merge_sort(vector<int>& a, int l, int r) {
    if (l < r) {
        int mid = (l + r) / 2;      // 计算中间索引
        merge_sort(a, l, mid);           // 递归排序左半部分
        merge_sort(a, mid + 1, r);       // 递归排序右半部分

        merge(a, l, mid, r);             // 合并两个已排序的子数组
    }
}

int main()
{
    vector<int>a(10);       // 创建一个包含10个元素的向量

    // 从标准输入中读取输入元素并存储在向量中
    for (int i = 0; i < 10; i++) {
        cin >> a[i];
    }

    merge_sort(a, 0, a.size() - 1);   // 对输入的数组进行归并排序

    // 输出排序后的数组元素
    for (int i = 0; i < 10; i++) {
        cout << a[i] << " ";
    }

    return 0;
}

五.快速排序(Quick Sort)
快速排序维护左右指针left,right和基准点base
先让right不断向左扫,找到比base大(小)的值然后与left指向的值交换
然后left不断向右扫,找到比base小(大)的值然后与right指向的值交换
一次操作后会形成两个区间,然后分别对两个区间进行上述操作
代码示例中用了两种方法,一种普通的,一种使用分治
代码示例:

#include<iostream>

using namespace std;

void quickSort_num1(int arr[], int star, int end) {
    //确定左右指针的位置
    int left = star, right = end;
    //设置基准点
    int base = arr[star];
    if (left < right) {
        while (left < right) {
            //先让由指针不断往左寻找比 base 小的值,找到了便交换
            //如果没找到,此时left = right 等于没交换
            while (left < right && arr[right] >= base) {
                right--;
            }
            arr[left] = arr[right];
            //先让由指针不断往右寻找比 base 大的值,找到了便交换
            //如果没找到,此时left = right 等于没交换
            while (left < right && arr[left] <= base) {
                left++;
            }
            arr[right] = arr[left];
        }
        //arr[right] = base 也可以,因为最终left=right
        arr[left] = base;
        //接着再让分割好的两个小区间进行上述操作
        //左边区间为比base小的值
        quickSort_num1(arr, star, left - 1);
        //右边区间为比base大的值
        quickSort_num1(arr, left + 1, end);
    }
}

//采用分治的方法,先找分割点
//partition为寻找分割点的函数
int partition(int arr[], int left, int right) {
    int base = arr[left];
    while (left < right) {
        //先让由指针不断往左寻找比 base 小的值,找到了便交换
        //如果没找到,此时left = right 等于没交换
        while (left < right && arr[right] >= base) {
            right--;
        }
        arr[left] = arr[right];
        //先让由指针不断往右寻找比 base 大的值,找到了便交换
        //如果没找到,此时left = right 等于没交换
        while (left < right && arr[left] <= base) {
            left++;
        }
        arr[right] = arr[left];
    }
    arr[left] = base;
    return left;
}

void quickSort_num2(int arr[], int left, int right) {
    if (left < right) {
        //确定分割点
        int pos = partition(arr, left, right);
        //左右区间,再重复操作
        quickSort_num2(arr, left, pos - 1);
        quickSort_num2(arr, pos + 1, right);
    }
}

int main() {
    int arr1[10] = {9, 8, 7, 6, 5, 4, 3, 2, 1, 10};
    quickSort_num1(arr1, 0, 9);
    for (int i = 0; i < 10; i++) {
        cout << arr1[i] << " ";
    }
    cout << '\n';
    //采用分治思想
    int arr2[10] = {9, 8, 7, 6, 5, 4, 3, 2, 1, 10};
    quickSort_num2(arr2, 0, 9);
    for (int i = 0; i < 10; i++) {
        cout << arr2[i] << " ";
    }
    cout << '\n';
    return 0;
}