各种排序-C语言描述

浅浅的花香味﹌ 2022-09-16 06:16 150阅读 0赞

## 各种排序-C语言描述 ##

各种排序算法

#include <stdio.h>
    #include <stdlib.h>
    
    void insert_sort(int * data,int length);
    void bubble_sort(int * data,int length);
    void shell_sort(int * data,int length);
    void merge_sort(int * data,int length);
    void quick_sort(int * data,int length);
    
    int main(){
        
        int length = 15;
        int data[length];
        int i = 0;
        for(i=0;i<length;i++){
        
            data[i] = rand();
        }
        //insert_sort(data,length);
        //bubble_sort(data,length);
        //shell_sort(data,length);
        //merge_sort(data,length);
        quick_sort(data,length);
        for(i=0;i<length;i++){
        
            printf("%d\n",data[i]);
        }
    }
    
    void insert_sort(int *data,int length){
        
        int i=0,j=0;
        for(i=1;i<length;i++){
        
            /*for(j=i;j>0;j--){
                if(data[j]<data[j-1]){
                    int temp = data[j];
                    data[j] = data[j-1];
                    data[j-1] = temp;
                }
                else
                   break;
            }
            */
            int temp = data[i];
            for(j=i;j>0;j--){
        
                if(data[j-1] > temp)
                    data[j] = data[j-1];
            }
            data[j] = temp;
        }
    }
    
    void bubble_sort(int * data,int length){
        
        int i=0,j=0;
        for(i=0;i<length;i++){
        
            for(j=0;j<length-1;j++){
        
                if(data[j]>data[j+1]){
        
                    int temp = data[j+1];
                    data[j+1] = data[j];
                    data[j] = temp;
                 }
             }
         }
    }
    
    void shell_sort(int * data,int length){
        
        int i = 0,j = 0,increment = 0;
        int temp;
        for(increment = length/2;increment>0;increment/=2){
        
            for(i = increment;i<length;i++){
        
                temp = data[i];
                for(j=i;j>=increment;j-=increment){
        
                    if(temp<data[j-increment])
                        data[j] = data[j-increment];
                    else
                        break;
                }
                data[j] = temp;
            }
        }
    }
    
    void MSort(int * data,int * temp_array,int left,int right);
    void Merge(int * data,int * temp_array,int rpos,int rend);
    void merge_sort(int *data,int length){
        
        int * temp_array;
        temp_array = malloc(sizeof(int)*length);
        MSort(data,temp_array,0,length-1);
        free(temp_array);
    }
    
    void MSort(int *data,int * temp_array,int left,int right){
        
        int mid;
        
        if(left < right){
        
            mid = (left+right)/2;
            MSort(data,temp_array,left,mid);
            MSort(data,temp_array,mid+1,right);
            Merge(data,temp_array,left,mid+1,right);
        }
    }
    
    void Merge(int * data,int *temp_array,int lpos,int rpos,int rend){
        
        int i,lend,num,temppos;
        lend = rpos-1;
        temppos = lpos;
        num = rend-lpos+1;
        
        while(lpos<=lend && rpos<=rend){
        
           if(data[lpos] <= data[rpos])
               temp_array[temppos++] = data[lpos++];
           else
               temp_array[temppos++] = data[rpos];
           
        while(lpos < lend)
            temp_array[temppos++] = data[lpos++];
        while<rpos <= rend)
            temp_array[temppos++] = data[rpos++];
        for(i=0;i<num;i++,rend--)
            data[rend] = temp_array[rend];
    }
    
    void MyQSort(int * data,int left,int right);
    void QSort(int * data,ine left,int right);
    void quick_sort(int * data,int length){
        
        //MYQSort(data,0,length-1);
        QSort(data,0,length-1);
    }
    
    void MyQSort(int *data,int left,int right){
        
        if(left>right)
            return;
        int mid = (left+right)/2;
        int temp = data[mid];
        data[mid] = data[right];
        data[right] = temp;
    
        int i = left;
        int j = right-1;
        while(i<j){
        
            while((data[i]<temp) && (i<right)){
        
                i++;
            }
            while((data[j]>temp) && (j>left)){
        
                j--;
            }
            if(i<j){
        
                int t = data[j];
                data[j] = data[i];
                data[i] = t;
            }
            else{
        
                int t1=data[i];
                data[i] data[right];
                data[right] = t1;
                break;
            }
        }
        MyQSort(data,left,i-1);
        MyQSort(data,i+1,right);
    }
    
    void Swap(int *a,int *b){
        
        int t = (*a);
        (*a) = (*b);
        (*b) = t;
    }
    
    int Median3(int * data,int left,int right){
        
        int center = (left+right)/2;
        if(data[left] > data[center])
            Swap(&data[left],&data[right]);
        if(data[left] > data[right])
            Swap(&data[left],&data[right]);
        if(data[center] > data[right])
            Swap[&data[center],&data[right]);
        Swap(&data[center],&data[right-1]);
        return data[right-1];
    }
    
    void QSort(int *data,int left,int right){
        
        int i,j;
        int Pivot;
    
        if(left+Cutoff<=right){
        
            Pivot = Median3(data,left,right);
            i = left;
            j = right-1;
            for(;;){
        
                while(data[++i] < Pivot){
        }
                while(data[--j] < Pivot){
        }
                if(i<j)
                    Swap(&data[i],&data[j]);
                else
                    break;
            }
            Swap(&data[i],&data[right-1]);
            QSort(data,left,i-1);
            QSort(data,i+1,right);
        else
            insert_sort(data+left,right-left+1);
    }
    
    void Qselect(int *data,int k,int left,int right){
        
        int i,j;
        int Pivot;
        if(left+Cutoff <= right){
        
            Pivot = Median3(data,left,right);
            i = left;
            j = right-1;
            for(;;){
        
                while(data[++i]<Pivot){
        }
                while(data[--j]>Pivot){
        }
                if(i<j)
                    Swap(&data[i],&data[j]);
                else
                    break;
                }
            Swap(&data[i],&data[right-1]);
            if(k<=i)
                Qselect(data,k,left,i-1);
            else if(k>i+1)
                QSelect(data,k,i+1,right);
            }
        else
            insert_sort(data+left,right-left+1);
    }