一些排序算法

一些排序算法

更多排序算法可以看这位作者的

冒泡排序，下标从0开始的，要是从1记得第二个for循环 “j

void bubble_sort()
{
    for(int i=0;ia[j+1])
    swap(a[j],a[j+1]);
}

选择排序，这里是从下标0开始的

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

}

快速排序，这里下标从1开始

void quick_sort(int l,int r)
{
    if(l>=r)
    return ;
    int x = a[l];
    int low = l,high = r;
    while(low=x)high--;
        a[low] = a[high];
        while(low 
 
 
归并排序， 这里下标从1开始
 
 
void f(int s1,int e1,int s2,int e2)
{
    int p=0,p1=s1,p2=s2;
    while(p1<=e1&&p2<=e2)
    {
        if(a[p1]<=a[p2])
        b[p++]=a[p1++];
        else
        {  
            //求逆序对的话这里加上：cnt+=e1-p1+1;
            b[p++]=a[p2++];
        }
    }
    while(p1<=e1)
    {
        b[p++]=a[p1++];
    }
    while(p2<=e2)
    { 
         b[p++]=a[p2++];
    }
    for(int i=s1;i<=e2;i++)
    {
        a[i] = b[i-s1];
    }
    return ;
}
void ssort(int l,int r)
{
    if(l> 1;
        ssort(l,mid);
        ssort(mid+1,r);
        f(l,mid,mid+1,r);
    }
}
 
 
 
堆排序 ，这里下标从1开始
 
 
#include 

using namespace std;
const int N = 100010;
int a[N];
int siz,n,m;
void adjust(int x)
{
    int temp = x;
    if(x*2<=siz&&a[x*2]> n>> m;
    for(int i=1;i<=n;i++)
    cin >>a[i];
    
    siz=n;
    
    for(int i=n/2;i>=1;i--)
    adjust(i);
    
    for(int i=1;i<=m;i++)
    {
        cout < 
 
 
插入排序
 
 
 
//这里代码是从下标为0开始的
void insert_sort() {
    for (int i = 1; i < n; i++) {
        int x = a[i];
        int j = i - 1;

        while (j >= 0 && x < a[j]) {
            a[j + 1] = a[j];
            j--;
        }
        a[j + 1] = x;
    }
    for(int i=0;i 
 
希尔排序 别名——缩小增量排序 (可以看作插入排序的改进)
 
 
#include 

using namespace std;
const int N = 21010;
int a[N];
int n;
void shell_sort()
{
    int gap = n/2;
    while(gap>=1)
    {
        for(int i=gap+1;i<=n;i++)
        {
            int j = i-gap;
            a[0] = a[i];
            while(j>0&&a[0]> n;
    for(int i=1;i<=n;i++)
    cin >>a[i];
    shell_sort();
     return 0;
}
欢迎分享，转载请注明来源：内存溢出
原文地址:https://54852.com/zaji/5651306.html