所有的排序c语言实现

客官°小女子只卖身不卖艺 2022-09-19 00:21 120阅读 0赞

排序主要有两种，一种是n平方复杂度的，一种是nlogn或者n根号n的。  
n平方复杂度的主要是一个一个将有序区间缩小，而nlogn或者根号n则是分区间的增大有序序列。  
\#include <stdio.h>  
\#include <stdlib.h>  
\#include <inttypes.h>  
\#include <math.h>  
//在linux中，rand函数的最大值是32位字节，windows是16位字节  
void swap(int32\_t \*a,int32\_t \*b)  
\{  
    int32\_t temp = \*a;  
    \*a = \*b;  
    \*b = temp;  
\}  
void print(int32\_t a\[\],int32\_t length)  
\{  
    int32\_t i;  
    for(i=0;i<length;i++)  
    \{  
        printf("%d\\n",a\[i\]);  
    \}  
\}  
//重新给数组赋予随机值  
void assign(int a\[\],int length)  
\{  
    int32\_t i;  
    for(i=0;i<length;i++)  
        a\[i\] = rand();  
\}  
void dubble(int32\_t a\[\],int32\_t length)  
\{  
    \_Bool flags = 0;  
    int32\_t i,j;  
    for(i=0;i<length-1&&!flags;i++)  
    \{  
        flags = 1;  
        for(j=length-1;j>0;j--)  
            if(a\[j\]<a\[j-1\])  
            \{  
                swap(&a\[j\],&a\[j-1\]);  
                flags = 0;  
            \}  
    \}  
\}  
void select(int32\_t a\[\],int32\_t length)  
\{  
    int32\_t i,j;  
    int32\_t min;  
    for(i=0;i<length-1;i++)  
    \{  
        min = i;  
        for(j=i+1;j<length;j++)  
        \{  
            if(a\[j\]<a\[min\])  
                min = j;  
        \}  
        if(min!=i)  
            swap(&a\[i\],&a\[min\]);  
    \}  
\}  
void insert(int32\_t a\[\],int32\_t length)  
\{  
    int32\_t i,j,temp;  
    for(i=1;i<length;i++)  
    \{  
        if(a\[i\]<a\[i-1\])  
        \{  
            temp = a\[i\];  
            for(j=i-1;j>=0&&a\[j\]>temp;j--)  
                a\[j+1\] = a\[j\];  
            a\[j+1\] = temp;  
        \}  
    \}  
\}  
void shell(int32\_t a\[\],int32\_t length)  
\{  
    int32\_t increment=length/2;  
    int32\_t i,j,temp;  
    while(increment>=1)  
    \{  
        for(i=increment;i<length;i++)  
        \{  
            if(a\[i\]<a\[i-increment\])  
            \{  
                temp = a\[i\];  
                for(j=i-increment;j>=0&&a\[j\]>temp;j-=increment)  
                    a\[j+increment\] = a\[j\];  
                a\[j+increment\] = temp;  
            \}  
        \}  
        increment/=2;  
    \}  
\}  
//由于堆排序涉及到\*2，所以应当用1  
void heapadjust(int32\_t a\[\],int32\_t low,int32\_t high)  
\{  
    int32\_t i,j,temp;  
    temp = a\[low-1\];  
    for(j=2\*low;j<=high;j\*=2)  
    \{  
        if(j<high&&a\[j-1\]<a\[j\])  
            j++;  
        if(temp>a\[j-1\])  
            break;  
        a\[low-1\] = a\[j-1\];  
        low = j;  
    \}  
    a\[low-1\] = temp;  
\}  
void heap(int32\_t a\[\],int32\_t length)  
\{  
    int32\_t i,j;  
    for(i=length/2;i>0;i--)  
        heapadjust(a,i,length);  
    for(i=length;i>1;i--)  
    \{  
        swap(&a\[0\],&a\[length-1\]);  
        heapadjust(a,1,i-1);  
    \}  
\}  
void Merge(int32\_t a\[\],int32\_t low,int32\_t mid,int32\_t high)  
\{  
    int32\_t i,j,k;  
    int32\_t \*temp;  
    temp = (int32\_t \*)malloc((high-low+1)\*sizeof(int32\_t));  
    i=low;  
    j=mid+1;  
    k=0;  
    while(i<=mid&&j<=high)  
    \{  
        if(a\[i\]>a\[j\])  
            temp\[k++\] = a\[j++\];  
        else  
            temp\[k++\] = a\[i++\];  
    \}  
    while(i<=mid)  
        temp\[k++\] = a\[i++\];  
    while(j<=high)  
        temp\[k++\] = a\[j++\];  
    for(i=low,j=0;j<k;j++,i++)  
        a\[i++\] = temp\[j++\];  
    free(temp);  
\}  
void Msort(int32\_t a\[\],int32\_t low,int32\_t high)  
\{  
    int32\_t i,j,mid;  
    if(high>low)  
    \{  
        mid = (high+low)/2;  
        Msort(a,low,mid);  
        Msort(a,mid+1,high);  
        Merge(a,low,mid,high);  
    \}  
\}  
void mergesort(int32\_t a\[\],int32\_t length)  
\{  
    Msort(a,0,length-1);  
\}  
int32\_t Partition(int32\_t a\[\],int32\_t low,int32\_t high)  
\{  
    int32\_t piv = a\[low\];  
    while(low<high)  
    \{  
        while(high>low&&a\[high\]>piv)  
            high--;  
        a\[low\] = a\[high\];  
        while(low<high&&a\[low\]<piv)  
            low++;  
        a\[high\] = a\[low\];  
    \}  
    a\[low\] = piv;  
    return low;  
\}  
void Qsort(int32\_t a\[\],int32\_t low,int32\_t high)  
\{  
    int32\_t piv;  
    if(low<high)  
    \{  
        piv = Partition(a,low,high);  
        Qsort(a,low,piv-1);  
        Qsort(a,piv+1,high);  
    \}  
\}  
void quicksort(int32\_t a\[\],int length)  
\{  
    Qsort(a,0,length-1);  
\}  
int main()  
\{  
    //init array  
    int32\_t a\[10\]=\{0,4,6,8,2,3,5,9,7,1\};  
    assign(a,10);  
    //print  
    printf("start:\\n");  
    print(a,10);  
    //sort  
    dubble(a,10);  
    //print  
    printf("after sort:\\n");  
    print(a,10);  
    return 0;  
\}