所有排序C语言实现

旧城等待， 2024-04-17 05:57 1阅读 0赞

### 为了复习一下排序，所以把堆排序、快速排序、冒泡排序、选择排序、插入排序、归并排序都复习了一下，具体原理就不讲了，网上都有，直接看代码吧。 ###

## 1.堆排序 ##

#include<stdio.h>
    #include<stdlib.h>
    #include<string.h>
    //交换函数
    void swap（int *a,int *b）
    { 
        int tmp=*a;
        *a=*b;
        *b=tmp;
    }
    //排序函数
    void HeapAdjust(int A[],int s,int Length)
    { 
        int temp;
        int child;
        for(temp=A[s];2*s+1<Length;s=child)
        { 
            child=2*s+1;
            if(child!=Length-1&&A[child+1]>A[child])
            { 
                ++child;
            }
            if(temp<A[child])
            { 
                A[s]=A[child];
            }
            else
            { 
                break;
            }
        }
        A[s]=temp;
    }
    
    void HeapSort(int A[],int Length)
    { 
        for(int i=Length/2;i>=0;--i)
        { 
            HeapAdjust(A,i,Length);
        }
        
        for(int j=Length-1;j>0;--j)
        { 
            swap(&A[0],&A[j]);
            HeapAdjust(A,0,j);
                
        }
    }
    
    void Print(int A[],int Length)
    { 
        int i;
        for(i=0;i<Length;i++)
        { 
            printf("%d",A[i])
        }
    }
    
    int main()
    { 
    	int arr[10] = {  2,87,39,49,34,62,53,6,44,98 };
    	Print(arr, 10);
    	printf("\n");
    	HeapSort(arr, 10);
    	Print(arr, 10);
    	printf("\n");
        return 0;
    }

## 2.快速排序 ##

#include<stdio.h>
    #include<stdlib.h>
    #include<string.h>
    
    void swap(int *a,int *b)
    { 
        int tmp=*a;
        *a=*b;
        *b=tmp;
    }
    
    void QuickSort(int arry[],int start,int end)
    { 
        int tmpstart=start;
        int tmpend=end;
        int arryBase;  //基值
        int arryMiddle; //分界坐标
        //递归结束条件
        if(tmpstart>=tmpend)
        { 
            return;
        }
        arryBase=arry[start];
        while(start<end)
        { 
            while(start<end&&arry[end]>arryBase)
            { 
                end--;
            }
            if(start<end)
            { 
                swap(&arry[start],&arry[end]);
                start++;
            }
            while(start<end&&arry[start]>arryBase)
            { 
                start++;
            }
            if(start<end)
            { 
                swap(&arry[start],&arry[end]);
                end--;
            }
        }
        arry[start]=arryBase;
        arryMiddle=start;
        //递归处理
        QuickSort(arry,tmpstart,arryMiddle-1);
        QuickSort(arry,arryMiddle+1,tmpend);
    }
    
    int main();
    { 
        int myArr[] = { 12,13,15,20,0,-1,-10,100};
        int i=0;
        int arrLength = sizeof(myArr)/sizeof(int);
        quickSort(myArr,0,arrLength-1);
    
        for(i = 0; i<arrLength; i++)
            printf("%5d",myArr[i]);
        return 0;
    }
     快速排序算法的性能取决于快速排序递归的深度，所以可以用递归树来描述递归算法执行情况，在最优情况下，每次都划分的很均匀，那么仅需要递归long2n次，然后做n次比较，所以最好时间复杂度为O（nlog2n);空间复杂度为O（log2n）
    最坏情况是待排序为正序或逆序，每次划分只得到一个比上一次划分少一个记录的子序列。如果用递归树画出来就是一颗斜树。需要执行n-1次递归调用。且第i次划分需要经过n-i次关键字的比较才能找到第i个记录，因此时间复杂度为O（n2).最坏空间复杂度为O（n）,

## 3.冒泡排序 ##

#include<stdio.h>
    #include<stdlib.h>
    
    
    typedef int bool;
    #define False 0
    #define True 1
    
    void swap(int* a, int* b)
    { 
    	int tmp = *a;
    	*a = *b;
    	*b = tmp;
    }
    
    void BubbleSort(int arry[], int length)
    { 
    	bool Flag = True;
    	int i, j;
    	for (i = 0;i < length && Flag;i++)
    	{ 
    		Flag = False;
    		for (j = length - 1;j >= i;--j)
    		{ 
    			if (arry[j] < arry[j-1])
    			{ 
    				swap(&arry[j],&arry[j-1]);
    				Flag = True;
    			}
    		}
    	}
    }
    
    int main()
    { 
    	int arr1[] = { 4,1,5,6,2};
    	BubbleSort(arr1,5);
    	for (int i = 0;i < 5;i++)
    	{ 
    		printf("%d\t",arr1[i]);
    	}
    	return 0;
    }

## 4.选择排序 ##

void selectSort(char *a,int length)
    { 
        int min;
        for(int i=0;i<length;i++)
        { 
            min=i;
            for(int j=i+1;j<length;j++)
            { 
                if(a[j]<a[min])
                { 
                    ming=j
                }
            }
            if(i!=min)
            { 
                swap(&a[i],&a[min]);
            }
        }
    }

## 5.直接插入排序 ##

#include<stdio.h>
    #include<stdlib.h>
    
    void InsertSort(int arry[],int len)
    { 
        int Bnum;
        int i,j;
        for(i=1;i<len;i++)
        { 
            if(arry[i]<arry[i-1])
            { 
                Bnum=arry[i];
                while(j=i-1;arry[j]>Bnum;j--)
                { 
                    arry[j+1]=arry[j];
                }
                arry[j+1]=Bnum;
            }
        }
    }

## 6. 归并排序 ##

#include<stdio.h>
    #include<stdlib.h>
    #include<string.h>
    
    void MergeAdd(int arry[],int left,int mid,int right,int*temp)
    { 
        int i=left;
        int j=mid+1;
        int k=left; // 游标
        while(i<=mid&&j<=right)
        { 
            if(arry[i]<arry[j])
            { 
                temp[k++]=arry[i++];
            }
            else
            { 
                temp[k++]=arry[j]++;
            }
        }
        while(i<=mid)
        { 
            temp[k++]=arry[i++];
        }
        while(j<=right)
        { 
            temp[k++]=arry[j]++;
        }
        
        memcpy(arry+left,temp+left,sizeof(int)*(right-left+1));
    }
    
    void MergeSort(int arry[],int left,int right,int *temp)
    { 
        int mid=0;
        if(left<right)
        { 
            mid=left+(right-left)/2;
            MergeSort(arry,left,mid,temp);
            MergeSort(arry,mid+1,right);
            MergeAdd(arry,left,mid,right,temp);
        }
    }
    int main()
    { 
        int arry[]={ 2,45,12,53,155,66,21,66, 67};
        int len=sizeof(arr)/sizeof(int);
        int *temp=(int *)malloc(sizeof(int)*len);
        MergeSort(arry,0,len-1,temp);
        return 0;
    }