排序

冒泡排序

#include<iostream>

using namespace std;

void BubbleSortAsc(double num[],int length)
{
    bool exchange=true;
    for(int i=0;i<length-1;i++)
    {
        for(int j=0;j<length-1-i;j++)
        {
            if(num[j]>num[j+1])
            {
                double t=num[j];
                num[j]=num[j+1];
                num[j+1]=t;
                exchange=false;
            }
        }
        if(exchange)
            break;
    }
}

void BubbleSortDesc(double num[],int length)
{
    bool exchange=true;
    for(int i=0;i<length-1;i++)
    {
        for(int j=0;j<length-1-i;j++)
        {
            if(num[j]<num[j+1])
            {
                double t=num[j];
                num[j]=num[j+1];
                num[j+1]=t;
                exchange=false;
            }
        }
        if(exchange)
            break;
    }
}

int main()
{
    double num[1000];
    int length;
    for(length=0;cin>>num[length];length++);
    BubbleSortDesc(num,length);
    for(int i=0;i<length;i++)
        cout<<num[i]<<" ";
    return 0;
}

优化

#include<iostream>

using namespace std;

void BubbleSortAsc(double num[],int length)
{
    bool exchange=true;
    int pos,k=length-1,n=0;//n：最小值下标（首指针）；k：最大值下标（尾指针）；pos：用于记录最后一次交换的位置
    for(int i=0;i<length-1;i++)
    {
        //正向寻找最大值
        pos=0;
        for(int j=n;j<k;j++)
        {
            if(num[j]>num[j+1])
            {
                double t=num[j];
                num[j]=num[j+1];
                num[j+1]=t;
                exchange=false;
                pos=j;
            }
        }
        if(exchange)
            break;
        k=pos;
        //反向寻找最小值
        for(int j=k;j>n;j--)
        {
            if(num[j]<num[j-1])
            {
                double t=num[j-1];
                num[j-1]=num[j];
                num[j]=t;
                exchange=false;
            }
        }
        n++;
        if(exchange)
            break;
    }
}

void BubbleSortDesc(double num[],int length)
{
    bool exchange=true;
    int pos,k=length-1,n=0;
    for(int i=0;i<length-1;i++)
    {
        //正向寻找最小值
        pos=0;
        for(int j=n;j<k;j++)
        {
            if(num[j]<num[j+1])
            {
                double t=num[j];
                num[j]=num[j+1];
                num[j+1]=t;
                exchange=false;
                pos=j;
            }
        }
        if(exchange)
            break;
        k=pos;
        //反向寻找最大值
        for(int j=k;j>n;j--)
        {
            if(num[j]>num[j-1])
            {
                double t=num[j];
                num[j]=num[j-1];
                num[j-1]=t;
                exchange=false;
            }
        }
        n++;
        if(exchange)
            break;
    }
}

int main()
{
    double num[1000];
    int length;
    for(length=0;cin>>num[length];length++);
    BubbleSortDesc(num,length);
    for(int i=0;i<length;i++)
        cout<<num[i]<<" ";
    return 0;
}

选择排序

#include<iostream>

using namespace std;

void SelectionSortAsc(double num[],int length)
{
    int minindex;
    for(int i=0;i<length-1;i++)
    {
        minindex=i;
        for(int j=i+1;j<length;j++)
        {
            if(num[j]<num[minindex])
                minindex=j;
        }
        double t=num[minindex];
        num[minindex]=num[i];
        num[i]=t;
    }
}

void SelectionSortDesc(double num[],int length)
{
    int maxindex;
    for(int i=0;i<length-1;i++)
    {
        maxindex=i;
        for(int j=i+1;j<length;j++)
        {
            if(num[j]>num[maxindex])
                maxindex=j;
        }
        double t=num[maxindex];
        num[maxindex]=num[i];
        num[i]=t;
    }
}

int main()
{
    double num[1000];
    int length;
    for(length=0;cin>>num[length];length++);
    SelectionSortDesc(num,length);
    for(int i=0;i<length;i++)
        cout<<num[i]<<" ";
    return 0;
}

优化

#include<iostream>

using namespace std;

void SelectionSortAsc(double num[],int length)
{
    int minindex,maxindex,left,right;
    for(left=0,right=length-1;left<=right;left++,right--)
    {
        minindex=left;
        maxindex=right;
        for(int i=left;i<=right;i++)
        {
            if(num[i]<num[minindex])
                minindex=i;
            if(num[i]>num[maxindex])
                maxindex=i;
        }
        if(minindex!=left)
        {
            double t=num[minindex];
            num[minindex]=num[left];
            num[left]=t;
            if(maxindex==left)
                maxindex=minindex;

        }
        if(maxindex!=right)
        {
            double t=num[maxindex];
            num[maxindex]=num[right];
            num[right]=t;
        }
    }
}

void SelectionSortDesc(double num[],int length)
{
    int minindex,maxindex,left,right;
    for(left=0,right=length-1;left<=right;left++,right--)
    {
        minindex=right;
        maxindex=left;
        for(int i=left;i<=right;i++)
        {
            if(num[i]<num[minindex])
                minindex=i;
            if(num[i]>num[maxindex])
                maxindex=i;
        }
        if(maxindex!=left)
        {
            double t=num[maxindex];
            num[maxindex]=num[left];
            num[left]=t;
            if(minindex==left)
                minindex=maxindex;
        }
        if(minindex!=right)
        {
            double t=num[minindex];
            num[minindex]=num[right];
            num[right]=t;
        }
    }
}

int main()
{
    double num[1000];
    int length;
    for(length=0;cin>>num[length];length++);
    SelectionSortDesc(num,length);
    for(int i=0;i<length;i++)
        cout<<num[i]<<" ";
    return 0;
}

插入排序

#include<iostream>

using namespace std;

void InsertionSortAsc(double num[],int length)
{
    int preindex;
    double current;
    for(int i=1;i<length;i++)
    {
        if(num[i]>num[i-1])
            continue;//小优化，如果已排好则后面不用执行
        preindex=i-1;
        current=num[i];
        while(preindex>=0&&num[preindex]>current)
        {
            num[preindex+1]=num[preindex];
            preindex--;
        }
        num[preindex+1]=current;
    }
}

void InsertionSortDesc(double num[],int length)
{
    int preindex;
    double current;
    for(int i=1;i<length;i++)
    {
        if(num[i]<num[i-1])
            continue;
        preindex=i-1;
        current=num[i];
        while(preindex>=0&&num[preindex]<current)
        {
            num[preindex+1]=num[preindex];
            preindex--;
        }
        num[preindex+1]=current;
    }
}

int main()
{
    double num[1000];
    int length;
    for(length=0;cin>>num[length];length++);
    InsertionSortDesc(num,length);
    for(int i=0;i<length;i++)
        cout<<num[i]<<" ";
    return 0;
}

折半插入排序

#include<iostream>

using namespace std;

void BinaryInsertionSortAsc(double num[],int length)
{
    int left,right,mid;
    double current;
    for(int i=1;i<length;i++)
    {
        left=0;
        right=i-1;
        current=num[i];
        while(left<=right)
        {
            mid=left+(right-left)/2;//效果等同于（left+right）/2，而且可以防止left+right的和溢出
            if(current<=num[mid])
                right=mid-1;
            else if(current>num[mid])
                left=mid+1;
        }
        for(int j=i;j>left;j--)
            num[j]=num[j-1];
        num[left]=current;
    }
}

void BinaryInsertionSortDesc(double num[],int length)
{
    int left,right,mid;
    double current;
    for(int i=1;i<length;i++)
    {
        left=0;
        right=i-1;
        current=num[i];
        while(left<=right)
        {
            mid=left+(right-left)/2;
            if(current>=num[mid])
                right=mid-1;
            else if(current<num[mid])
                left=mid+1;
        }
        for(int j=i;j>left;j--)
            num[j]=num[j-1];
        num[left]=current;
    }
}

int main()
{
    double num[1000];
    int length;
    for(length=0;cin>>num[length];length++);
    BinaryInsertionSortDesc(num,length);
    for(int i=0;i<length;i++)
        cout<<num[i]<<" ";
    return 0;
}

希尔排序

#include<iostream>

using namespace std;

void ShellSortAsc(double num[],int length)
{
    int gap=length,preindex;
    double current;
    while(gap>1)
    {
        gap=gap/3+1;
        for(int i=gap; i<length; i++)
        {
            preindex=i-gap;
            current=num[i];
            while(preindex>=0&&num[preindex]>current)
            {
                num[preindex+gap]=num[preindex];
                preindex-=gap;
            }
            num[preindex+gap]=current;
        }
    }
}

void ShellSortDesc(double num[],int length)
{
    int gap=length,preindex;
    double current;
    while(gap>1)
    {
        gap=gap/3+1;
        for(int i=gap; i<length; i++)
        {
            preindex=i-gap;
            current=num[i];
            while(preindex>=0&&num[preindex]<current)
            {
                num[preindex+gap]=num[preindex];
                preindex-=gap;
            }
            num[preindex+gap]=current;
        }
    }
}

int main()
{
    double num[1000];
    int length;
    for(length=0;cin>>num[length];length++);
    ShellSortDesc(num,length);
    for(int i=0;i<length;i++)
        cout<<num[i]<<" ";
    return 0;
}

快速排序

#include<iostream>

using namespace std;

void QuickSortAsc(double num[],int left,int right)
{
    int i=left,j=right;
    double mid=num[(left+right)/2];
    do
    {
        while(num[i]<mid)
            i++;
        while(num[j]>mid)
            j--;
        if(i<=j)
        {
            double t=num[i];
            num[i]=num[j];
            num[j]=t;
            i++;
            j--;
        }
    }while(i<=j);
    if(left<j) QuickSortAsc(num,left,j);
    if(i<right) QuickSortAsc(num,i,right);
}

void QuickSortDesc(double num[],int left,int right)
{
    int i=left,j=right;
    double mid=num[(left+right)/2];
    do
    {
        while(num[i]>mid)
            i++;
        while(num[j]<mid)
            j--;
        if(i<=j)
        {
            double t=num[i];
            num[i]=num[j];
            num[j]=t;
            i++;
            j--;
        }
    }while(i<=j);
    if(left<j) QuickSortDesc(num,left,j);
    if(i<right) QuickSortDesc(num,i,right);
}

int main()
{
    double num[1000];
    int length;
    for(length=0;cin>>num[length];length++);
    QuickSortDesc(num,0,length-1);
    for(int i=0;i<length;i++)
        cout<<num[i]<<" ";
    return 0;
}

快速排序（挖坑法）

#include<iostream>

using namespace std;

void QuickSortAsc(double num[],int left,int right)
{
    int i=left,j=right;
    double tmp=num[left];
    while(i<j)
    {
        while(i<j&&num[j]>=tmp)
            j--;
        if(i<j)
            num[i++]=num[j];
        while(i<j&&num[i]<=tmp)
            i++;
        if(i<j)
            num[j--]=num[i];
    }
    num[i]=tmp;
    if(left<j-1) QuickSortAsc(num,left,i-1);
    if(i+1<right) QuickSortAsc(num,i+1,right);
}

void QuickSortDesc(double num[],int left,int right)
{
    int i=left,j=right;
    double tmp=num[left];
    while(i<j)
    {
        while(i<j&&num[j]<=tmp)
            j--;
        if(i<j)
            num[i++]=num[j];
        while(i<j&&num[i]>=tmp)
            i++;
        if(i<j)
            num[j--]=num[i];
    }
    num[i]=tmp;
    if(left<j-1) QuickSortDesc(num,left,i-1);
    if(i+1<right) QuickSortDesc(num,i+1,right);
}

int main()
{
    double num[1000];
    int length;
    for(length=0;cin>>num[length];length++);
    QuickSortDesc(num,0,length-1);
    for(int i=0;i<length;i++)
        cout<<num[i]<<" ";
    return 0;
}

归并排序

#include<iostream>

using namespace std;

void mergeAsc(double num[],int left,int mid,int right)
{
    double tmp[right-left+1];
    int p1=left,p2=mid+1,index=0;
    while(p1<=mid&&p2<=right)
    {
        if(num[p1]<num[p2])
        {
            tmp[index]=num[p1];
            p1++;
            index++;
        }
        else
        {
            tmp[index]=num[p2];
            p2++;
            index++;
        }
    }
//简洁写法：
//while(p1<=mid&&p2<=right)
//    tmp[index++]=num[p1]<num[p2]?num[p1++]:num[p2++];
    while(p1<=mid)//将左边剩余元素填充进tmp中
    {
        tmp[index]=num[p1];
        p1++;
        index++;
    }
//简洁写法：
//while(p1<=mid)
//    tmp[index++]=num[p1++];
    while(p2<=right)//将右序列剩余元素填充进tmp中
    {
        tmp[index]=num[p2];
        p2++;
        index++;
    }
//简洁写法
//while(p2<=right)
//    tmp[index++]=num[p2++];
    for(int i=0;i<right-left+1;i++)
        num[left+i]=tmp[i];
}

void MergeSortAsc(double num[],int left,int right)
{
    if(left>=right)
        return;
    int mid=(left+right)/2;
    MergeSortAsc(num,left,mid);
    MergeSortAsc(num,mid+1,right);
    mergeAsc(num,left,mid,right);
}

void mergeDesc(double num[],int left,int mid,int right)
{
    double tmp[right-left+1];
    int p1=left,p2=mid+1,index=0;
    while(p1<=mid&&p2<=right)
        tmp[index++]=num[p1]>num[p2]?num[p1++]:num[p2++];
    while(p1<=mid)
        tmp[index++]=num[p1++];
    while(p2<=right)
        tmp[index++]=num[p2++];
    for(int i=0;i<right-left+1;i++)
        num[left+i]=tmp[i];
}

void MergeSortDesc(double num[],int left,int right)
{
    if(left>=right)
        return;
    int mid=(left+right)/2;
    MergeSortDesc(num,left,mid);
    MergeSortDesc(num,mid+1,right);
    mergeDesc(num,left,mid,right);
}

int main()
{
    double num[1000];
    int length;
    for(length=0;cin>>num[length];length++);
    MergeSortDesc(num,0,length-1);
    for(int i=0;i<length;i++)
        cout<<num[i]<<" ";
    return 0;
}

堆排序

#include<iostream>

using namespace std;

void adjustAsc(double num[],int i,int length)
{
    int j,flag=0;
    while(2*i+1<length&&flag==0)
    {
        j=2*i+1;
        if(j+1<length&&num[j]<num[j+1])
            j++;
        if(num[j]>num[i])
        {
            double tmp=num[i];
            num[i]=num[j];
            num[j]=tmp;
            i=j;//更新i为刚才与它交换的儿子结点的编号，便于接下来继续向下调整
        }
        else
            flag=1;
    }
}

void HeapSortAsc(double num[],int length)
{
    //构建大顶堆
    for(int i=length/2-1;i>=0;i--)
        adjustAsc(num,i,length);
    //交换堆顶元素与末尾元素+调整堆结构
    for(int i=length-1;i>0;i--)
    {
        double tmp=num[0];
        num[0]=num[i];
        num[i]=tmp;
        adjustAsc(num,0,i);
    }
}

void adjustDesc(double num[],int i,int length)
{
    int j,flag=0;
    while(2*i+1<length&&flag==0)
    {
        j=2*i+1;
        if(j+1<length&&num[j+1]<num[j])
            j++;
        if(num[j]<num[i])
        {
            double tmp=num[i];
            num[i]=num[j];
            num[j]=tmp;
            i=j;
        }
        else
            flag=1;
    }
}

void HeapSortDesc(double num[],int length)
{
    for(int i=length/2-1;i>=0;i--)
        adjustDesc(num,i,length);
    for(int i=length-1;i>0;i--)
    {
        double tmp=num[0];
        num[0]=num[i];
        num[i]=tmp;
        adjustDesc(num,0,i);
    }
}

int main()
{
    double num[1000];
    int length;
    for(length=0;cin>>num[length];length++);
    HeapSortDesc(num,length);
    for(int i=0;i<length;i++)
        cout<<num[i]<<" ";
    return 0;
}