各种常见排序算法实现

╰+哭是因爲堅強的太久メ 2022-03-07 05:38 179阅读 0赞

将各种常见排序算法简单实现了一下，包括：1、简单插入排序；2、冒泡排序；3、简单选择排序；4、快速排序；5、希尔排序；6、堆排序；7、归并排序

代码如下：

#include<stdio.h>
    #include<stdlib.h>
    #include<time.h>
    
    #define LEN 10
    
    //初始化数组
    void init(int arr[], int len);
    //打印数组元素
    void print(int arr[], int len);
    //打印堆元素
    void printH(int arrH[], int len);
    //交换两个整数的值
    void swap(int & a, int & b);
    //简单插入排序
    void insertSort(int arr[], int len);
    //冒泡排序
    void bubbleSort(int arr[], int len);
    //简单选择排序
    void selectSort(int arr[], int len);
    //返回快排枢轴下标
    int partion(int arr[], int low, int high);
    //快速排序
    void quickSort(int arr[], int low, int high);
    //堆调整
    void heapAjust(int arrH[], int s, int m);
    //堆排序
    void heapSort(int arrH[],int len);
    //希尔排序
    void shellSort(int arr[], int len);
    //归并
    void merge(int arr[], int temp[], int s, int m, int t);
    //归并排序
    void mergeSort(int arr[], int temp[],int s, int t);
    int main()
    {
        int arr[LEN];
        //堆排序用，arrH[0]做临时变量使用
        int arrH[LEN+1];
        int temp[LEN]={0};
        srand((unsigned)time(NULL));
        //简单插入排序
        init(arr,LEN);
        printf("\n原始数据:");
        print(arr,LEN); 
        printf("插入排序后:");
        insertSort(arr,LEN);
        print(arr,LEN);
        //冒泡排序
        init(arr,LEN);
        printf("\n原始数据:");
        print(arr,LEN);
        printf("冒泡排序后:");
        bubbleSort(arr,LEN);
        print(arr,LEN);
        //简单选择排序
        init(arr,LEN);
        printf("\n原始数据:");
        print(arr,LEN);
        printf("简单选择排序后:");
        selectSort(arr,LEN);
        print(arr,LEN);
        //快速排序
        init(arr,LEN);
        printf("\n原始数据:");
        print(arr,LEN);
        printf("快速排序后:");
        quickSort(arr,0,LEN - 1);
        print(arr,LEN);
        //希尔排序
        init(arr,LEN);
        printf("\n原始数据:");
        print(arr,LEN);
        printf("希尔排序后:");
        shellSort(arr,LEN);
        print(arr,LEN);
        //对排序
        init(arrH,LEN+1);
        arrH[0] = 100;//将第一个元素初始化为0
        printf("\n原始数据:");
        printH(arrH,LEN+1);
        printf("堆排序后:");
        heapSort(arrH,LEN);
        printH(arrH,LEN+1);
        //归并排序
        init(arr,LEN);
        printf("\n原始数据:");
        print(arr,LEN);
        printf("归并排序后:");
        mergeSort(arr,temp,0,LEN - 1);
        print(arr,LEN);
        return 0;
    }
    
    //初始化数组
    void init(int arr[], int len)
    {
       int i;
       for (i = 0; i< len; i++)
       {
           arr[i] = rand() % 1000;
       }
    }
    
    //打印数组元素
    void print(int arr[], int len)
    {
       int i;
       printf("\n");
       for (i = 0; i < len; i++)
           printf("%d    ",arr[i]);
       printf("\n");
    }
    //打印堆元素
    void printH(int arrH[], int len)
    {
       int i;
       printf("\n");
       for (i = 1; i < len; i++)
           printf("%d    ",arrH[i]);
       printf("\n");
    }
    //交换两个整数的值
    void swap(int & a, int & b)
    {
        a = a ^ b;
        b = a ^ b;
        a = a ^ b;
    }
    //简单插入排序
    void insertSort(int arr[], int len)
    {
        int i,j,temp;
        for (i = 1; i < len; i++)
        {
            temp = arr[i];
            for(j = i - 1; j >= 0 && arr[j] > temp; j--)
                arr[j+1] = arr[j];
            arr[j+1] = temp;
        }      
    }
    //冒泡排序
    void bubbleSort(int arr[], int len)
    {
        int i,j,exchange;
        exchange = 0;
        for (i = 0; i < len - 1; i++)
        {
            for (j = 0; j < len - i - 1; j++)
            {
                if (arr[j] > arr[j+1])
      	    {
                    swap(arr[j],arr[j+1]);
                    exchange = 1;
                }
            }
            //如果没交换元素，说明已排好序
            if (!exchange)
            {
                break;
            }
        }
    }
    //简单选择排序
    void selectSort(int arr[], int len)
    {
        int i,j,temp;
        for (i = 0; i < len - 1; i++)
        {
            temp = i;
            for (j = i + 1; j < len; j++)
            {
                if (arr[j] < arr[temp])
                {
                    temp = j; 
                }
            }
            if (temp != i)
            {
                swap(arr[temp],arr[i]);
            }
        }
            
    }
    //返回快排枢轴下标
    int partion(int arr[], int low, int high)
    {
        int temp;
        temp = arr[low];
        while (low < high)
        {
            while (low < high && arr[high] >= temp)
                high--;
            arr[low] = arr[high];
            while (low < high && arr[low] <= temp)
                low++;
            arr[high] = arr[low];
        }
        arr[low] = temp;
        return low;
    }
    //快速排序
    void quickSort(int arr[], int low, int high)
    {
        if (low > high || low < 0 || high < 0)
        {
            return;
        } 
    
        if (low < high)
        {
    	int mid = partion(arr,low,high);
            quickSort(arr,low,mid - 1);
            quickSort(arr,mid + 1,high); 
        }         
    }
    //堆调整，大堆
    void heapAjust(int arrH[], int s, int m)
    {
        int temp = arrH[s];
        int i;
        for (i = 2 * s; i <= m; i *= 2)
        {
            if ((i < m) && (arrH[i] < arrH[i+1]))
               i++;
            if(arrH[i] <= temp)
               break;
            arrH[s] = arrH[i];
            s = i;
        }
        arrH[s] = temp; 
    }
    //堆排序
    void heapSort(int arrH[],int len)
    {
        int i;
        for (i = len / 2; i > 0; i--)
            heapAjust(arrH,i,len);
        for (i = len; i > 1; i--)
        {
            swap(arrH[1],arrH[i]);
            heapAjust(arrH,1,i - 1);
        }
    }
    //希尔排序
    void shellSort(int arr[], int len)
    {
     int h = 0;
     int i = 0;
     int j = 0;
     //设置步长
     for(h = 1; h < len; h = 3 * h + 1)
         ;
     while(h)
     {
         h /= 3;
         if(h < 1)
             break;
         for(i = h; i < len; i++)
            for(j = i; j >= h; j-=h)
            {
               if(arr[j-h] < arr[j])
                  break;
               swap(arr[j-h],arr[j]);
            }
      }
    }
    
    //归并arr[s...t]
    void merge(int arr[],int temp[], int s, int m, int t)
    {
        //printf("\ns=%d,m=%d,t=%d\n",s,m,t);
        //int *temp;
        //int temp[10];
        int i,j,k,mm=s;
        if( s >= t )
    	return;
        //temp = (int *)malloc( (t - s + 1)*sizeof(int) );
        for ( k = s,j = m + 1; ( s <= m ) && ( j <= t ); k++ )
        {
    	if ( arr[s] <= arr[j] )
    	    temp[k] = arr[s++];
    	else
    	    temp[k] = arr[j++];
        }
        if ( s <= m )
        {
    	for ( i = s; i <= m; i++ )
    	{
    	    temp[k++] = arr[i];
       	}
        }
        if ( j <= t )
        {
    	for ( i = j; i <= t; i++ )
    	{
    	    temp[k++] = arr[i];
      	}
        }
        //将排好的元素再赋值回原数组arr
        for( i = mm; i <= t; i++ )
        {
    	arr[i] = temp[i];
        }
        //printf("\n");
        //free(temp);
    }
    
    //归并排序
    void mergeSort(int arr[], int temp[], int s, int t)
    {
        int m = 0,i;
        if( s < t )
        {
    	m = ( s + t ) / 2;
    	mergeSort(arr,temp,s,m);
    	mergeSort(arr,temp,m+1,t);
    	merge(arr,temp,s,m,t);
        }
    }

运行结果：

![20130507211812355][]

[20130507211812355]: /images/20220307/a0ea176681a143318c51dac43a0348e0.png