AcWing
  • 首页
  • 课程
  • 题库
  • 更多
    • 竞赛
    • 题解
    • 分享
    • 问答
    • 应用
    • 校园
  • 关闭
    历史记录
    清除记录
    猜你想搜
    AcWing热点
  • App
  • 登录/注册

各类排序算法总结

作者: 作者的头像   kylin_4 ,  2019-06-26 23:10:58 ,  所有人可见 ,  阅读 2206


16


21
#include <bits/stdc++.h>

using namespace std;

// 冒泡排序 O(n^2) 稳定

void bubbleSort(int a[], int n)
{
    for(int i = n - 1; i > 0; i--)
    {
        for(int j = 0; j < i; j++)
        {
            if(a[j] > a[j+1]) swap(a[j], a[j+1]);
        }
    }
}

// 快速排序 O(nlogn)

void quickSort(int a[], int l, int r)
{
   if(l>=r) return;

   int i = l, j = r, tmp = a[l];

   while(i < j)
   {
        while(i < j && a[j] >= tmp) j--;
        if(i < j) a[i++] = a[j];
        while(i < j && a[i] <= tmp) i++;
        if(i < j) a[j--] = a[i]; 
   }
   a[i] = tmp;
   quickSort(a,l,i-1);
   quickSort(a,i+1,r);
}

// 插入排序 O(n^2) 稳定

void insertSort(int a[], int n)
{
    for(int i = 1; i < n; i++)
    {
        int tmp = a[i], j;
        for(j = i; j > 0 && tmp < a[j-1];j--)
            a[j] = a[j-1];
        a[j] = tmp;
    }
}

// 选择排序 O(n^2)

void selectSort(int a[], int n)
{
    for(int i = 0; i < n - 1; i++)
    {
        for(int j = i + 1; j < n; j++)
        {
            if(a[i] > a[j]) swap(a[i], a[j]);
        }
    }
}

// 归并排序 O(nlogn) 稳定
void mergeSort(int a[], int l, int r)
{
    if(l >= r) return;

    int tmp[r-l+1];

    int mid = l + r >> 1;
    mergeSort(a,l,mid), mergeSort(a,mid+1,r);

    int i = l , j = mid + 1, k = 0;

    while(i <= mid && j <= r)
        if(a[i] <= a[j]) tmp[k++] = a[i++];
        else tmp[k++] = a[j++];

    while(i <= mid) tmp[k++] = a[i++];
    while(j <= r) tmp[k++] = a[j++];

    for(int i = l, j = 0; i <= r; i++, j++) a[i] = tmp[j];
}

// 堆排序 O(nlogn)
void adjust_heap(int a[], int x, int n)
{
    int l = x * 2 + 1;
    int r = x * 2 + 2;
    int max = x;

    if(l < n && a[l] > a[max]) max = l;
    if(r < n && a[r] > a[max]) max = r;

    if(max != x)
    {
        swap(a[x], a[max]);
        adjust_heap(a,max,n);
    }
}

void heapSort(int a[], int n)
{
    for(int i = n/2-1; i >= 0; i--)
        adjust_heap(a, i, n);

    for(int i = n-1; i > 0; i--)
    {
        swap(a[0], a[i]);
        adjust_heap(a,0,i);
    }
}

int main()
{
    int a[] = {3, 2, 1, 5, 3, 10, 3, 7, 6, 7, 9, 8, 1};
    int n = sizeof(a)/sizeof(int);
    // bubbleSort(a,n); 
    // quickSort(a,0,n-1);
    // insertSort(a,n);
    // selectSort(a, n);
    // heapSort(a, n);
    // mergeSort(a, 0, n-1);
    for(int i = 0; i < n; i++) cout << a[i] << ' ';
    cout << endl;

}


4 评论


用户头像
RyuJeXu   2021-11-26 16:47         踩      回复

啊对对对


用户头像
捡到一束光   2020-01-31 21:39         踩      回复

根据定义 选择排序,应该是每次找到最小值的下标,再交换吧?


用户头像
捡到一束光   2020-01-31 21:28         踩      回复

tql!


用户头像
人生真是寂寞如雪啊   2019-12-18 10:45         踩      回复

nice


App 内打开
你确定删除吗?
1024
x

© 2018-2025 AcWing 版权所有  |  京ICP备2021015969号-2
用户协议  |  隐私政策  |  常见问题  |  联系我们
AcWing
请输入登录信息
更多登录方式: 微信图标 qq图标 qq图标
请输入绑定的邮箱地址
请输入注册信息