冒泡、选择、插入、希尔、归并、快速、堆等十大排序算法——C语言实现及其复杂度比较

冒泡排序

基本思想：比较相邻元素。以从小到大排序为例，每一轮选出最大值放在序列最右边，每一轮比较的次数都将减少一次。

/*************************************************
*    冒泡排序
*    待排序序列：12,45,3,6,99,1,37,78（从小到大）
**************************************************/
#include <stdio.h>
void bubble_sort(int a[],int size)
{
        int i = 0, j = 0;
        for(i = 0; i < size; i++){
                for(j = 0;j < size - 1 - i; j++){
                        if(a[j]>a[j+1]){
                                int temp = a[j];
                                a[j] = a[j+1];
                                a[j+1] = temp;
                        }
                }
        }
}
int main()
{
        int array[8] = {12,45,3,6,99,1,37,78};      //待排序序列
        int i = 0;
        int length = sizeof(array) / sizeof(array[0]);  //序列长度

        bubble_sort(array,length);  //冒泡排序

        /*输出排序后结果*/
        for(i = 0; i < length; i++)
        {
                printf("%d ",array[i]);
        }
        printf("\n");

}

排序结果：

选择排序

基本思想：从待排序的中数据元素选出最小的一个元素，存放在序列的起始位置，然后从剩余的未排序元素中寻找到最小元素，然后放到已排序的序列的末尾，直到序列排序完毕。

/*************************************************
*    选择排序
*    待排序序列：12,45,3,6,99,1,37,78（从小到大）
**************************************************/

#include <stdio.h>
void choose_sort(int a[],int size)
{
        int i = 0, j = 0;
        for(i = size - 1; i > 0; i--){
                for(j = 0;j < i; j++){
                        if(a[i] < a[j]){
                                int temp = a[j];
                                a[j] = a[i];
                                a[i] = temp;
                        }
                }
        }
}

插入排序

基本思想：选定第一个数为基准，此后从未排序序列中选取数据插入到已排序序列的前或后，直到序列排序完毕。

/*************************************************
*    插入排序
*    待排序序列：12,45,3,6,99,1,37,78（从小到大）
**************************************************/

#include <stdio.h>
void insert_sort(int a[],int size)
{
        int i = 0, j = 0;
        for(i = 0; i < size-1; i++){
                int right = i;
                int num = a[right+1];
                while(right>=0){
                        if(num < a[right])
                        {
                                a[right+1] = a[right];
                                right--;
                        }
                        else{
                                break;
                        }
                }
                a[right+1] = num;
        }

}

希尔排序

归并排序

快速排序

堆排序

计数排序

基本思想：找到无序序列的最大值max，动态申请一个大小为max的数组，之后遍历待排序的无序数组（12,45,3,6,99,1,37,78），遇到第一个数字12时，就新数组的第11个位置加一，这样可以统计原来序列的所有数据，最后将新数组有序输出。特殊地，如果待排序的序列中有相同的数据，记得单独拎出来判断。

/**************************************************
*    count排序
*    待排序序列：12,45,3,6,99,1,37,78（从小到大）
**************************************************/

#include <stdio.h>
void count_sort(int a[],int size)
{
        int i = 0, j = 0;
        int max = 0;

        for(i = 0; i < size; i++)
        {
                if(a[i]>=max)
                {
                        max = a[i];
                }
        }
        int *b = (int *)malloc(max*sizeof(int));

        for(i = 0; i < size; i++)
        {
                b[a[i]-1] = a[i]
        }

        for(j = 0;j < max; j++)
        {
                if(b[j] != 0)
                {
                        a[]
                }
        }
}

桶排序

基数排序

时间复杂度对比