C语言排序算法实现

冒泡排序

#include <stdio.h>
#include  <stdlib.h>
#include <string.h>

//数组的首地址传进去
void bubbleSorting(int *arr,int arrLength){

    for (int i = 0; i < arrLength; ++i) {
        for (int j = 0; j < arrLength-i-1; ++j) {
            if(arr[j]>arr[j+1]){
                int temp = arr[j+1];
                arr[j+1]=arr[j];
                arr[j]=temp;
            }
        }
    }
}

int main(){
    int arr[]={3,9,-1,10,20};
    int length = sizeof(arr)/sizeof(int);
    printf("%d\n",length);
    bubbleSorting(arr,length);
    for (int i = 0; i < length; ++i) {
        printf("%d ",arr[i]);
    }
    return 0;
}

选择排序

#include <stdio.h>
#include  <stdlib.h>
#include <string.h>
void selectedSorting(int* arr,int length){
    //int minNum = INT_MAX;  //整数中的最小值,由于是局部变量，必须赋初值
    for (int i = 0; i < length; ++i) {
        int minNum = INT_MAX;  //整数中的最小值,由于是局部变量，必须赋初值
        int index = 0;
        for (int j = i; j < length; ++j) {
            if(arr[j]<minNum){
                minNum=arr[j];
                index = j;
            }
        }
        //交换位置
        arr[index]=arr[i];
        arr[i]=minNum;
    }
}
int main() {
    int arr[]={8,3,2,1,7,4,6,5};
    selectedSorting(arr, sizeof(arr)/ sizeof(int));
    for (int i = 0; i < sizeof(arr)/ sizeof(int); ++i) {
        printf("%d ",arr[i]);
    }
    return 0;
}

插入排序

#include <stdio.h>
#include  <stdlib.h>
#include <string.h>

void insertionSorting(int* arr,int length){
    for (int i = 1; i < length; ++i) {
        //首先获取当前元素和索引
        int currentNum = arr[i];
        int currentIndex = i;
        while (currentNum<arr[currentIndex-1] && currentIndex>=0){
            arr[currentIndex]=arr[currentIndex-1];
            currentIndex--;
        }
        arr[currentIndex]=currentNum;
    }
}

int main() {
    int arr[]={8,3,2,1,7,4,6,5};
    insertionSorting(arr, sizeof(arr)/ sizeof(int));
    for (int i = 0; i < sizeof(arr)/ sizeof(int); ++i) {
        printf("%d ",arr[i]);
    }
    printf("hello,world!");
    return 0;
}

希尔排序（插入方式）（非交换方式）

#include <stdio.h>
#include  <stdlib.h>
#include <string.h>


void shellSorting(int* arr,int length){
    for (int gap = length/2; gap >=1 ; gap=gap/2) {
        for (int i = 0; i < length; i=i+gap) {
            int currentNum = arr[i];
            int currentIndex = i;
            while (currentNum<arr[currentIndex-gap] && currentIndex>=0){
                arr[currentIndex]=arr[currentIndex-gap];
                currentIndex=currentIndex-gap;
            }
            arr[currentIndex]=currentNum;
        }
    }
}
int main() {

    int arr[]={8,3,2,1,7,4,6,5};
    shellSorting(arr, sizeof(arr)/ sizeof(int));
    for (int i = 0; i < sizeof(arr)/ sizeof(int); ++i) {
        printf("%d ",arr[i]);
    }
    printf("hello,world!");
    return 0;
}

快速排序

#include <stdio.h>
#include  <stdlib.h>
#include <string.h>

//递归形式进行排序，分程左右两个部分，需要找到一个基准数
void quickSorting(int *arr,int left,int right){
     int l  = left;
     int r  = right;
     //pivot 中轴值
     int pivot = arr[(right+left)/2];
     int temp = 0;

     // while循环的目的是比中轴值小放到左边， 比中轴值大放到右边
     while (l<r){
         //左边先找,找到一个元素
         while (arr[l]<pivot){
             l+=1;
         }

         //右边先找,找到一个元素
         while (arr[r]>pivot){
             r-=1;
         }

         //如果l>=r说明pivot的左右两的值，已经交完完成
         if(l>=r){
             break;
         }

         //交换
         temp=arr[l];
         arr[l]=arr[r];
         arr[r]=temp;

         //如果交换完后，发现这个arr[l]==pivot值 相等r--,前移
         if(arr[l]==pivot){
             r-=1;
         }

         //如果交换完后，发现这个arr[r]==pivot值 相等l++,前移
         if(arr[r]==pivot){
             l+=1;
         }

     }

     //如果l==r，必须l++ ,r-- ，否则为出现栈溢出
     //如果是奇数个数字，如果不再走一步，就会在中间相遇，必须错开中轴值
     if(l==r){
        l+=1;
        r-=1;
     }

     //向左递归
     if(left<r){
         quickSorting(arr,left,r);
     }

     //向右递归
     if(right>l){
        quickSorting(arr,l,right);
     }

}

int main() {
    int arr[]={8,3,2,1,7,4,6,5};
    quickSorting(arr, 0,(sizeof(arr)/ sizeof(int))-1);
    for (int i = 0; i < sizeof(arr)/ sizeof(int); ++i) {
        printf("%d ",arr[i]);
    }
    printf("hello,world!");
    return 0;
}

归并排序（分治思想）

#include <stdio.h>
#include  <stdlib.h>
#include <string.h>

//合并数组
void merge(int* arr,int left,int mid,int right,int *temp){
     int i = left; //初始化i，左边有序序列的初始索引
     int j = mid+1; //初始化j，右边有序序列的初始索引
     int t = 0; //指向temp数组的当前索引

     //第一步
     //先把左右两边（有序）的数据按照规则填充到temp数组
     //直到左右两边的有序序列，有一边处理完毕
     while (i<=mid && j<=right){
        if(arr[i]<=arr[j]){
            temp[t]=arr[i];
            t+=1;
            i+=1;
        }else{
            temp[t]=arr[j];
            t+=1;
            j+=1;
        }
     }

     //第二步
     //把剩余数据的一边的数据依次全部填充到temp中
    while (i<=mid){
        temp[t]=arr[i];
        t+=1;
        i+=1;
    }

    while (j<=right){
        temp[t]=arr[j];
        t+=1;
        j+=1;
    }

    //第三步
    //将temp数据拷贝到arr
    //注意，并不是每次都拷贝所有
    t=0;
    int tempLeft =left;
    while (tempLeft<=right){
       arr[tempLeft]=temp[t];
       t+=1;
       tempLeft+=1;
    }
}


/**
 * @param arr 待排序的数组
 * @param left 左索引
 * @param right 右索引
 * @param temp  临时开辟的数组，用于局部排序和存储
 */
void mergeSorting(int* arr,int left,int right,int *temp){

    if(left<right){
        int mid = (left+right)/2; //中间索引

        //向左递归拆解
        mergeSorting(arr,left,mid,temp);

        //向右递归拆解
        mergeSorting(arr,mid+1,right,temp);

        //聚合
        merge(arr,left,mid,right,temp);
    }
}



int main() {
    int arr[]={8,3,2,1,7,4,6,5};
    int temp[sizeof(arr)/ sizeof(int)]={};
    mergeSorting(arr, 0,sizeof(arr)/ sizeof(int),temp);
    for (int i = 0; i < sizeof(arr)/ sizeof(int); ++i) {
        printf("%d ",arr[i]);
    }
    printf("hello,world!");
    return 0;
}

基数排序（桶排序）

基数排序的基本思想（典型的空间换时间方式）：

将所有待比较数值统一为同样的数位长度，数位较短的数前面补零。然后从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成后，数列就变成了一个有序序列。

#include <stdio.h>
#include  <stdlib.h>
#include <string.h>
//#define NUMBER 10

void radixSorting(int *arr, int length) {
    char strTemp[] = " ";
    int max = arr[0];
    for (int i = 0; i < length; ++i) {
        if (arr[i] >= max) {
            max = arr[i];
        }
    }
    //得到最大数的是几位数
    sprintf(strTemp,"%d",max);
    int maxLength = strlen(strTemp);
    //定义一个二维数组，表示10个桶，每个桶就是一个一维数组
    //二维数组包括10个一维数组
    int bucket[10][length];

    //为了记录每个桶中实际存放了多少个数据，我们定义一个一维数组来记录每个桶每次放入的数据的个数
    //即bucketElementCounts[0] 代表bucket[0]中存放的个数
    int bucketElementCounts[10]={};

    for (int i = 0,n=1; i < maxLength; ++i,n*=10) {
         //针对每个元素的对应位进行排序处理，第一次是各位，第二次是十位，第三次是百位
        for (int j = 0; j < length; ++j) {
            //取出每个元素对应位的值
            int digitOfElement = arr[j]/n%10;
            //放入到对应的桶中
            bucket[digitOfElement][bucketElementCounts[digitOfElement]]=arr[j];
            bucketElementCounts[digitOfElement]++;
        }

        //按照这个桶的顺序（一维数组的下标依次取出数据，放入原来的数组）
        int index =0;
        //遍历每一桶，并将桶中得数据，放回到原数组
        for (int k = 0; k < sizeof(bucketElementCounts)/ sizeof(int); ++k) {
            //如果桶中有数据，我们才放回到原数组中
            if(bucketElementCounts[k]!=0){
                //循环该桶，即第k个桶（即第k个一维数组），放入
                for (int l = 0; l < bucketElementCounts[k]; ++l) {
                    //取出元素放回到arr
                    arr[index++]=bucket[k][l];
                }
            }

            //取出数据放回后，需要将记录每个桶的中元素个数的数据清零
            bucketElementCounts[k]=0;
        }
    }
}
int main() {

    int arr[] = {53, 3, 542, 748, 14, 214};
    radixSorting(arr, sizeof(arr)/ sizeof(int));

    for (int i = 0; i < sizeof(arr)/ sizeof(int); ++i) {
        printf("%d ",arr[i]);
    }
    return 0;
}

速度较快，但是遇到超大数量级的就不行了。空间不足，容易造成内存溢出。