数据结构常用的七种排序算法总结

排序算法在数据结构里属于最为重要的一部分，例如我们熟悉的冒泡、选择、插入、归并等，这些当初在第一次学习的时候，并没有很好的掌握，现在因为在备战考研，刚刚进行完数据结构的一轮简单复习在开始整理一轮比较重要的代码，于是从第八章开始整理7种重要的排序–冒泡、选择、希尔排序、插入、归并、堆排序。

void BubbleSort1(int *arr,int len)
{
    int i,j;
    bool flag=false;
    //这个是从后面亡前面冒
    for(i=0;i
        for(j=len-1;j>0;j--)
        {
            if(arr[j]
                swap(&arr[j],&arr[j-1]);
                flag=true;
            }
        }
        if(flag==false)
        {
            return;
        }
    }
}

void BubbleSort2(int *arr,int len)
{
    int i,j;
    for(i=0;i
        for(j=0;j
            if(arr[j]>arr[j+1])
            {
                swap(&arr[j],&arr[j+1]);
            }
        }
    }
}

void InsertSort(int *arr,int len)
{
    int i,j;
    int tmp;
    for(i=1;i
        tmp=arr[i];
        for(j=i-1;j>=0&&arr[j]>tmp;j--)
        {
            arr[j+1]=arr[j];
        }
        arr[j+1]=tmp;
    }
}

void ChooseSort(int *arr,int len)
{
    int i,j,min;
    for(i=0;i
        min=i;
        for(j=i+1;j
            if(arr[j]
                min=j;
            }
        }
        if(min!=i)
        {
            swap(&arr[i],&arr[min]);
        }
    }
}

void ShellSort(int *arr,int len)
{
    int i,j,dk;
    int tmp;
    for(dk=len/2;dk>=1;dk=dk/2)
    {
        for(i=dk+1;i
            tmp=arr[i];
            for(j=i-dk;j>=0&&arr[j]>tmp;j-=dk)
            {
                arr[j+dk]=arr[j];
            }
            arr[j+dk]=tmp;
        }
    }
}

int GetPortion(int *arr,int low,int high)
{
    int Portion=arr[low];
    while (low
        while (low=Portion)high--;//往前搜索
            arr[low]=arr[high];
        while (low
    int Position= GetPortion(arr,low,len);
    if(low
        QuickSort(arr,low,Position-1);
        QuickSort(arr,Position+1,len);
    }
}

void BuildMax(int *arr,int start,int end)
{
    int dad=start;
    int son=2*dad+1;
    while (son<=end)
    {
        if(son+1<=end&&arr[son]
            son++;
        }
        else if(arr[dad]>arr[son])
        {
            return;
        } else{
            swap(&arr[dad],&arr[son]);
            dad=son;
            son=2*dad+1;
        }
    }
}
void HeapSort(int *arr,int len)
{
    int i;
    for(i=len/2-1;i>=0;i--)//从len/2-1到0
    {
        BuildMax(arr,i,len-1);//调用构建大根堆的函数
    }
}

void Merge(int *arr,int low,int mid,int len)
{
    int *A=(int *) malloc(sizeof(int )*(len+1));
    int i,j,k;
    for(i=low;i<=len;i++)
    {
        A[i]=arr[i];//将arr的元素复制到A中
    }
    for(i=low,j=mid+1,k=i;i<=mid&&j<=len;k+=1)
    {
        if(A[i]<=A[j])
        {
            arr[k]=A[i++];
        } else
            arr[k]=A[j++];
    }
    while (i<=mid)arr[k++]=A[i++];
    while (j<=len)arr[k++]=A[j++];//后面还没处理好的元素
}
void MergeSort(int *arr,int low,int len)
{
    if(low
        int mid=(low+len)/2;
        MergeSort(arr,low,mid);
        MergeSort(arr,mid+1,len);
        Merge(arr,low,mid,len);//合并在一起

    }
}

#include 
#include 
#include 
#include 
//本项目将总结所有考研重要的排序算法
void Menu_Show()
{
    printf("********Choose The way about Sorting*********n");
    printf("************************n");
    printf("1、BubbleSort1n");
    printf("2、BubbleSort2n");
    printf("3、InsertSortn");
    printf("4、ChooseSortn");
    printf("5、ShellSortn");
    printf("6、QuickSortn");
    printf("7、HeapSortn");
    printf("8、MergeSortn");
    printf("************************n");
}
void swap(int *a,int *b)
{
    int tmp=*a;
    *a=*b;
    *b=tmp;
}
int Str_Change_To_Number(char *str)
{
    if(strcmp(str,"BubbleSort1")==0)
    {
        return 1;
    }
    else if(strcmp(str,"BubbleSort2")==0)
    {
        return 2;
    }
    else if(strcmp(str,"InsertSort")==0)
    {
        return 3;
    }
    else if(strcmp(str,"ChooseSort")==0)
    {
        return 4;
    }
    else if(strcmp(str,"ShellSort")==0)
    {
        return 5;
    }
    else if(strcmp(str,"QuickSort")==0)
    {
        return 6;
    }
    else if(strcmp(str,"HeapSort")==0)
    {
        return 7;
    }
    else if(strcmp(str,"MergeSort")==0)
    {
        return 8;
    }
    else{
        return -1;
    }
}
void BubbleSort1(int *arr,int len)
{
    int i,j;
    bool flag=false;
    for(i=0;i
        for(j=len-1;j>0;j--)
        {
            if(arr[j]
                swap(&arr[j],&arr[j-1]);
                flag=true;
            }
        }
        if(flag==false)
        {
            return;
        }
    }
}
void BubbleSort2(int *arr,int len)
{
    int i,j;
    for(i=0;i
        for(j=0;j
            if(arr[j]>arr[j+1])
            {
                swap(&arr[j],&arr[j+1]);
            }
        }
    }
}
void InsertSort(int *arr,int len)
{
    int i,j;
    int tmp;
    for(i=1;i
        tmp=arr[i];
        for(j=i-1;j>=0&&arr[j]>tmp;j--)
        {
            arr[j+1]=arr[j];
        }
        arr[j+1]=tmp;
    }
}
void ChooseSort(int *arr,int len)
{
    int i,j,min;
    for(i=0;i
        min=i;
        for(j=i+1;j
            if(arr[j]
                min=j;
            }
        }
        if(min!=i)
        {
            swap(&arr[i],&arr[min]);
        }
    }
}
void ShellSort(int *arr,int len)
{
    int i,j,dk;
    int tmp;
    for(dk=len/2;dk>=1;dk=dk/2)
    {
        for(i=dk+1;i
            tmp=arr[i];
            for(j=i-dk;j>=0&&arr[j]>tmp;j-=dk)
            {
                arr[j+dk]=arr[j];
            }
            arr[j+dk]=tmp;
        }
    }
}
int GetPortion(int *arr,int low,int high)
{
    int Portion=arr[low];
    while (low
        while (low=Portion)high--;//往前搜索
            arr[low]=arr[high];
        while (low
    int Position= GetPortion(arr,low,len);
    if(low
        QuickSort(arr,low,Position-1);
        QuickSort(arr,Position+1,len);
    }
}
void BuildMax(int *arr,int start,int end)
{
    int dad=start;
    int son=2*dad+1;
    while (son<=end)
    {
        if(son+1<=end&&arr[son]
            son++;
        }
        else if(arr[dad]>arr[son])
        {
            return;
        } else{
            swap(&arr[dad],&arr[son]);
            dad=son;
            son=2*dad+1;
        }
    }
}
void HeapSort(int *arr,int len)
{
    int i;
    for(i=len/2-1;i>=0;i--)//从len/2-1到1
    {
        BuildMax(arr,i,len-1);
    }
}
void Merge(int *arr,int low,int mid,int len)
{
    int *A=(int *) malloc(sizeof(int )*(len+1));
    int i,j,k;
    for(i=low;i<=len;i++)
    {
        A[i]=arr[i];//将arr的元素复制到A中
    }
    for(i=low,j=mid+1,k=i;i<=mid&&j<=len;k+=1)
    {
        if(A[i]<=A[j])
        {
            arr[k]=A[i++];
        } else
            arr[k]=A[j++];
    }
    while (i<=mid)arr[k++]=A[i++];
    while (j<=len)arr[k++]=A[j++];//后面还没处理好的元素


}
void MergeSort(int *arr,int low,int len)
{
    if(low
        int mid=(low+len)/2;
        MergeSort(arr,low,mid);
        MergeSort(arr,mid+1,len);
        Merge(arr,low,mid,len);//合并在一起

    }
}
void Show(int *arr,int len)
{
    for (int i = 0; i 
        printf("%d ",arr[i]);
    }
}
int main()
{
    int arr[]={1,51,67,99,134,78,990,69,56,123};//1 51 56 67 69 78 99 123 134 990
    int len= sizeof(arr)/ sizeof(int );
    Menu_Show();
    char str[100];
    gets(str);
    int Index= Str_Change_To_Number(str);
    switch (Index) {
        case 1:
            BubbleSort1(arr,len);
            break;
        case 2:
            BubbleSort2(arr,len);
            break;
        case 3:
            InsertSort(arr,len);
            break;
        case 4:
            ChooseSort(arr,len);
            break;
        case 5:
            ShellSort(arr,len);
            break;
        case 6:
            QuickSort(arr,0,len-1);
            break;
        case 7:
            HeapSort(arr,len);//每个case后都要要break,否则原来的堆排序会被归并排序的结果覆盖
            break;
        case 8:
            MergeSort(arr,0,len-1);
            break;
        default:
            printf("Not exist the way of sorting--立即推--放弃考研");
            exit(0);
    }
    Show(arr,len);
}