排序算法

    基础排序算法思想：

    • 可以认为是在给定的数列中先找出最大值或最小值。
    • 然后在剩下的数据中再找最大值(或最小值)，重复此过程……最后让数列变得有序。

    冒泡排序

    每次将最大元素后移

    1. 比较相邻元素：从列表的第一个元素开始，比较相邻的两个元素。
    2. 交换位置：如果前一个元素比后一个元素大，则交换它们的位置。
    3. 重复遍历：对列表中的每一对相邻元素重复上述步骤，直到列表的末尾。这样，最大的元素会被"冒泡"到列表的最后。
    4. 缩小范围：忽略已经排序好的最后一个元素，重复上述步骤，直到整个列表排序完成。
    int n,t;
cin>>n;
for(int i=0;i<n;i++) 
    cin>>a[i];
for(int i=0;i<n-1;i++){//最后一次可以不比较所以减一
    for(int j=0;j<n-1-i;j++){
        if(a[j]>a[j+1]{
            t=a[j];
            a[j]=a[j+1];
            a[j+1]=t;    
        }
    }
}

    优化

    void BubbleSort(int a[], int n){
    for(int i=1; i<n; i++){
        bool flag = 1;
        for(int j=1; j<=n-i; j++){
            if(a[j+1] < a[j]){
                swap(a[j+1], a[j]);
                flag = 0;
            }
        }
        if(flag) break;
    }
}

    选择排序

    #include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
int a[N];
int main() {
    int n, t, maxn = 0;
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    for (int i = 1; i <= n; i++) { // 1
        int t = i;
        for (int j = i + 1; j <= n; j++) { // 2-5
            if (a[j] > a[t]) {
                t = j;
            }
        }
        if (t != i)
            swap(a[i], a[t]);
    }
    for (int i = 1; i <= n; i++)
        cout << a[i] << " ";
    return 0;
}

    插入排序

    int n,t;
cin>>n;
for(int i=0;i<n;i++) 
    cin>>a[i];
for(int i=1;i<n;i++){
    int now=a[i],j;
    for(j=i-1;j>=0;j--){
       if(now<a[j]) a[j+1]=a[j];
       else break;
    }
    a[j+1]=now;
}

    稳定性

    • 相同元素在排序前后的相对位置不变
    算法名称是否稳定
    冒泡排序稳定
    选择排序不稳定
    插入排序稳定