必须知道的C语言八大排序算法(收藏)

简介

排序算法（sorting algorithms）是计算机程序设计中处理数据的重要技术之一，常见于数据处理程序中。其功能是按照指定的方式将所输入的数据进行排序。排序算法分为内部排序和外部排序，本文主要讲解C语言中的八大内部排序算法。

八大排序算法

1. 冒泡排序
2. 选择排序
3. 插入排序
4. 希尔排序
5. 归并排序
6. 快速排序
7. 堆排序
8. 计数排序

冒泡排序

冒泡排序是一种简单的排序算法，它重复的遍历要排序的数列，一次比较两个元素，如果它们的顺序错误就交换位置。其时间复杂度为O(n^2)。

示例代码：

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

选择排序

选择排序是一种简单直观的排序算法，它的工作原理是：首先找到序列中最小的元素，其次将它放在序列的起始位置；接着，再从剩余未排序的元素中寻找最小的值，将其放在已排序序列的末尾。以此类推，直到所有元素均排列完毕。其时间复杂度为O(n^2)。

示例代码：

void selectionSort(int arr[], int n) {
    int i, j, min_idx;
    for (i = 0; i < n-1; i++) {
        min_idx = i;
        for (j = i+1; j < n; j++)
            if (arr[j] < arr[min_idx])
                min_idx = j;
        int temp = arr[i];
        arr[i] = arr[min_idx];
        arr[min_idx] = temp;
    }
}

（接下来五种算法类似的方式展开介绍）

插入排序

插入排序是一种简单直观的排序算法，它的工作原理是在已排序序列中从后向前扫描，找到相应位置并插入。其时间复杂度为O(n^2)。

示例代码：

void insertionSort(int arr[], int n) {
    int i, key, j;
    for (i = 1; i < n; i++) {
        key = arr[i];
        j = i - 1;
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j = j - 1;
        }
        arr[j + 1] = key;
    }
}

希尔排序

希尔排序是一种改进型的插入排序，其基本思路是将待排序的序列划分成若干个子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序。其时间复杂度为O(n*log2n)。

示例代码：

void shellSort(int arr[], int n) {
    int gap, i, j, temp;
    for (gap = n/2; gap > 0; gap /= 2) {
        for (i = gap; i < n; i++) {
            temp = arr[i];
            for (j = i; j >= gap && arr[j-gap] > temp; j -= gap)
                arr[j] = arr[j-gap];
            arr[j] = temp;
        }
    }
}

归并排序

归并排序是一种分治思想的排序算法，它的基本思想是将待排序序列分成若干个子序列，每个子序列都是有序的，然后再将有序子序列合并成一个有序序列。其时间复杂度为O(n*log2n)。

示例代码：

void merge(int arr[], int l, int m, int r) {
    int i, j, k;
    int n1 = m - l + 1;
    int n2 = r - m;

    int L[n1], R[n2];

    for (i = 0; i < n1; i++)
        L[i] = arr[l + i];
    for (j = 0; j < n2; j++)
        R[j] = arr[m + 1 + j];

    i = 0;
    j = 0;
    k = l;

    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k] = L[i];
            i++;
        }
        else {
            arr[k] = R[j];
            j++;
        }
        k++;
    }

    while (i < n1) {
        arr[k] = L[i];
        i++;
        k++;
    }

    while (j < n2) {
        arr[k] = R[j];
        j++;
        k++;
    }
}

void mergeSort(int arr[], int l, int r) {
    if (l < r) {
        int m = l+(r-l)/2;

        mergeSort(arr, l, m);
        mergeSort(arr, m+1, r);

        merge(arr, l, m, r);
    }
}

快速排序

快速排序是一种由C.A.R.Hoare在1960年提出的一种分治思想的原地快速排序算法。其基本思路是使用基准元素将一个序列分为左右两部分，一边存贮比该基准元素小的元素，另一边存储比该基准元素大的元素，而后递归处理这两个序列，直到这个序列不可分为止。其时间复杂度最差情况下为O(n^2)，但平均情况下为O(n*log2n)。

示例代码：

void swap(int* a, int* b) {
    int t = *a;
    *a = *b;
    *b = t;
}

int partition (int arr[], int low, int high) {
    int pivot = arr[high]; 
    int i = (low - 1);

    for (int j = low; j <= high- 1; j++) {
        if (arr[j] <= pivot) {
            i++;
            swap(&arr[i], &arr[j]);
        }
    }
    swap(&arr[i + 1], &arr[high]);
    return (i + 1);
}

void quickSort(int arr[], int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);

        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

堆排序

堆排序是一种分治思想的排序算法，它的基本思路是将待排序序列构成一个大根堆或小根堆，整个序列的最大值就是堆顶的根节点。将其移走，再从剩下的元素中构建一个新堆，反复执行上述操作，最终实现排序。其时间复杂度为O(n*log2n)。

示例代码：

void heapify(int arr[], int n, int i) {
    int largest = i;
    int l = 2*i + 1;
    int r = 2*i + 2;

    if (l < n && arr[l] > arr[largest])
        largest = l;
    if (r < n && arr[r] > arr[largest])
        largest = r;
    if (largest != i) {
        swap(&arr[i], &arr[largest]);
        heapify(arr, n, largest);
    }
}

void heapSort(int arr[], int n) {
    for (int i = n / 2 - 1; i >= 0; i--)
        heapify(arr, n, i);
    for (int i=n-1; i>=0; i--) {
        swap(&arr[0], &arr[i]);
        heapify(arr, i, 0);
    }
}

计数排序

计数排序是一种线性排序算法，其基本思路是统计待排序元素中小于等于每个元素的个数（称为元素k），最终确定该元素的位置。算法需确定待排序元素的最大和最小值。其时间复杂度为O(n+k)，k为元素范围。

示例代码：

void countSort(int arr[], int n) {
    int output[n];
    int max = arr[0];
    for (int i = 1; i < n; i++) {
        if (arr[i] > max)
            max = arr[i];
    }
    int count[max + 1];

    for (int i = 0; i <= max; ++i)
        count[i] = 0;

    for (int i = 0; i < n; i++)
        count[arr[i]]++;

    for (int i = 1; i <= max; i++)
        count[i] += count[i - 1];

    for (int i = n - 1; i >= 0; i--) {
        output[count[arr[i]] - 1] = arr[i];
        count[arr[i]]--;
    }

    for (int i = 0; i < n; i++)
        arr[i] = output[i];
}

总结

在实际应用中，我们需要考虑算法的时间复杂度、空间复杂度和稳定性这三个因素。每一种排序都有其独特的应用场景和相应的优缺点。选择合适的排序算法对于提升程序运行效率是相当必要的。