深入学习C语言中常见的八大排序

前言

排序算法是计算机科学中的基本问题之一，是计算机领域内经典且常见的算法问题之一。排序算法对于优化数据检索、数据压缩、数据库查询效率等方面都有着重要的意义。
本文将为您详细讲解常见的八种排序算法的原理、时间复杂度以及应用场景，希望能够对您学习和了解排序算法提供帮助。

简介

排序算法是将一串数据按照一定的规则进行排列，排序算法可以归为两类：内部排序和外部排序。所谓内部排序，就是数据记录在内存中进行排序。而外部排序是指在排序过程中需要使用外部存储器。
本文主要介绍常见的内部排序算法。

具体排序算法

冒泡排序（Bubble Sort）

冒泡排序是一种基本的排序算法，它重复地走访过要排序的数列，一遍又一遍地比较相邻的两个数。每一遍排序结束后，都会将其中经过比较后较大的数交换到该循环遍历到的末尾。时间复杂度：O(n^2)。

示例：

void bubble_sort(int a[], int n){
    for(int i=0;i<n-1;i++){
        for(int j=0;j<n-i-1;j++){
            if(a[j]>a[j+1]){
                int temp=a[j];
                a[j]=a[j+1];
                a[j+1]=temp;
            }
        }
    }
}

选择排序（Selection Sort）

选择排序是一种不稳定的简单排序算法。它的工作原理是先找到序列中最小的数，将其放在序列的最前端，再从剩余未排好序的序列中找到最小值，放在已排好序的数列的后面，依此类推，直到整个序列排序完毕。时间复杂度：O(n^2)。

示例：

void selection_sort(int a[], int n){
    for(int i=0;i<n-1;i++){
        int min_index=i;
        for(int j=i+1;j<n;j++){
            if(a[min_index]>a[j]){
                min_index=j;
            }
        }
        if(min_index!=i){
            int temp=a[i];
            a[i]=a[min_index];
            a[min_index]=temp;
        }
    }
}

插入排序（Insertion Sort）

插入排序是一种简单的排序算法，它的基本思想是将未排序的元素插入已排序的元素中。时间复杂度：O(n^2)。

示例：

void insertion_sort(int a[], int n){
    for(int i=1;i<n;i++){
        int temp=a[i];
        int j=i-1;
        while(j>=0 && a[j]>temp){
            a[j+1]=a[j];
            j--;
        }
        a[j+1]=temp;
    }
}

希尔排序（Shell Sort）

希尔排序是插入排序的一种高效改进算法。希尔排序采用了分组排序的方式，使数组元素在一定程度上有序，从而更快地达到最终排序结果。时间复杂度：O(nlogn)。

示例：

void shell_sort(int a[], int n){
    for(int step=n/2;step>=1;step/=2){
        for(int i=step;i<n;i++){
            int temp=a[i];
            int j=i-step;
            while(j>=0 && a[j]>temp){
                a[j+step]=a[j];
                j-=step;
            }
            a[j+step]=temp;
        }
    }
}

归并排序（Merge Sort）

归并排序是一种稳定的排序算法。它采用了分治策略，将输入序列递归地划分为较小的序列，然后对这些子序列进行合并，最终得到完整有序序列。时间复杂度：O(nlogn)。

示例：

void merge(int a[], int left, int mid, int right){
    int i=left, j=mid+1, k=0;
    int temp[right-left+1];
    while(i<=mid && j<=right){
        if(a[i]<=a[j]){
            temp[k++]=a[i++];
        }else{
            temp[k++]=a[j++];
        }
    }
    while(i<=mid){
        temp[k++]=a[i++];
    }
    while(j<=right){
        temp[k++]=a[j++];
    }
    for(int p=0;p<k;p++){
        a[left+p]=temp[p];
    }
}

void merge_sort(int a[], int left, int right){
    if(left>=right){
        return;
    }
    int mid=left+(right-left)/2;
    merge_sort(a, left, mid);
    merge_sort(a, mid+1, right);
    merge(a, left, mid, right);
}

快速排序（Quick Sort）

快速排序是一种分治排序算法，它采用了基准值的思想，通过递归地将数据分解为基准值的左右两个子集，然后将两个子集不断递归，直到排序完成。时间复杂度：O(nlogn)。

示例：

void quick_sort(int a[], int left, int right){
    if(left>=right){
        return;
    }
    int i=left, j=right, pivot=a[left];
    while(i<j){
        while(i<j && a[j]>pivot){
            j--;
        }
        while(i<j && a[i]<=pivot){
            i++;
        }
        if(i<j){
            int temp=a[i];
            a[i]=a[j];
            a[j]=temp;
        }
    }
    a[left]=a[i];
    a[i]=pivot;
    quick_sort(a, left, i-1);
    quick_sort(a, i+1, right);
}

堆排序（Heap Sort）

堆排序是一种基于树型结构的排序算法，它是对选择排序的一种改进。堆排序将序列看作一个完全二叉树，每个节点都比其左右子树的所有节点都大或都小，然后将该序列不断调整为一个小根堆或大根堆，最后直接输出堆顶元素即可进行排序。时间复杂度：O(nlogn)。

示例：

void adjust_heap(int a[], int i, int n){
    int child=2*i+1;
    int temp=a[i];
    while(child<n){
        if(child+1<n && a[child]<a[child+1]){
            child++;
        }
        if(a[i]<a[child]){
            a[i]=a[child];
            i=child;
            child=2*i+1;
        }else{
            break;
        }
        a[i]=temp;
    }
}

void heap_sort(int a[], int n){
    for(int i=n/2-1;i>=0;i--){
        adjust_heap(a, i, n);
    }
    for(int i=n-1;i>=0;i--){
        int temp=a[0];
        a[0]=a[i];
        a[i]=temp;
        adjust_heap(a, 0, i);
    }
}

计数排序（Counting Sort）

计数排序是一种稳定的排序算法，其核心思想是：枚举数组 A 中的每个元素 x，统计数组 A 中小于等于 x 的元素个数，并将元素 x 放置到数组 B 中对应下标的位置上。计数排序性能优秀，但是要求待排序数组中的元素必须是有确切范围的整数。时间复杂度：O(n+k)。

示例：

void counting_sort(int a[], int n){
    int max_num=a[0];
    for(int i=1;i<n;i++){
        if(a[i]>max_num){
            max_num=a[i];
        }
    }
    int counting[max_num+1];
    memset(counting,0,sizeof(counting));
    for(int i=0;i<n;i++){
        counting[a[i]]++;
    }
    for(int i=1;i<=max_num;i++){
        counting[i]+=counting[i-1];
    }
    int temp[n];
    for(int i=n-1;i>=0;i--){
        temp[--counting[a[i]]]=a[i];
    }
    for(int i=0;i<n;i++){
        a[i]=temp[i];
    }
}

结尾

本文详细讲解了常见的八种排序算法的原理、时间复杂度以及应用场景。通过学习本文，相信读者可以自己实现各种排序算法，提高算法的实现能力，也希望本文能够对您有所帮助。