题解 | 排序

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#define maxn 110
using namespace std;
int a[maxn];

void BubbleSort(int *arr,int len)//冒泡排序
{
    for(int i=0;i<len;i++)
    {
        for(int j = 0; j<len-i-1;j++)
        {
            if(a[j]>a[j+1])swap(a[j],a[j+1]);
        }
    }
}

void SelectSort(int *arr,int len)//选择排序
{
    for(int i=0;i<len;i++)
    {
        int minn = arr[i];
        for(int j=i+1;j<len;j++)
        {
            if(minn > arr[j])
            {
                minn = arr[j];
                swap(arr[i],arr[j]);
            }
        }
    }
}


int Huafen(int* arr,int l,int r)//快排
{
    int pri = arr[l];
    while(l<r)
    {
        while(l<r && pri <= arr[r])r--;
        arr[l] = arr[r];
        while(l<r && pri >= arr[l])l++;
        arr[r] = arr[l];
    }
    arr[l] = pri;
    return l;
}

void Qsort(int *arr,int l,int r)
{
    int mid;
    if(l < r)
    {
        mid = Huafen(arr, l, r);
        Qsort(arr, l, mid -1);
        Qsort(arr, mid + 1, r);
    }
}

void heapAdjust(int *arr,int root ,int len)//从小到大排序使用大根堆
{
    int tmp = arr[root];
    for(int i=(root + 1)*2 -1;i<len;i = (i+1)*2-1)
    {
        if(i <len-1 && arr[i]<arr[i+1])//找出大的
        {
            i++;
        }
        if(tmp >= arr[i])break;
        else{
            arr[root] = arr[i];
            root = i;
        }
    }
    arr[root] = tmp;
}

void buildHeap(int *arr,int len)
{
    for(int i=(len/2)-1;i>=0;i--)
    {
        heapAdjust(arr,i,len);
    }
}

void HeapSort(int *arr,int len){
    int tmp;
    buildHeap(arr,len);
    for(int i=len-1;i>0;i--)
    {
        swap(arr[0],arr[i]);
        heapAdjust(arr,0,i);
    }
}


int main() {
   int n;
   while(cin>>n)
   {
        for(int i=0;i<n;i++)cin>>a[i];
       // Qsort(a,0,n-1);
      //  BubbleSort(a,n);
      //  SelectSort(a,n);
      HeapSort(a,n);
        for(int i=0;i<n;i++)
        {
            cout<<a[i]<<" ";
        }cout<<endl;
   }
}
// 64 位输出请用 printf("%lld")