Comprehensive Overview of Common Sorting Algorithms with C Code Examples

Sorting algorithms are frequently asked in technical interviews; this article summarizes several classic sorts, discusses their stability and time complexities, and provides complete C implementations for each algorithm.

1 Insertion Sort

Insertion sort performs well on nearly sorted data, achieving O(N) best‑case time; its average and worst cases are O(N²). The following C code implements it:

/**
 * 插入排序
 */
void insertSort(int a[], int n)
{
    int i, j;
    for (i = 1; i < n; i++) {
        /* 循环不变式：a[0...i-1]有序。每次迭代开始前，a[0...i-1]有序，
         * 循环结束后i=n，a[0...n-1]有序 */
        int key = a[i];
        for (j = i; j > 0 && a[j-1] > key; j--) {
            a[j] = a[j-1];
        }
        a[j] = key;
    }
}

2 Shell Sort

Shell sort repeatedly applies insertion sort on sub‑arrays with decreasing gaps (N/2, N/4, …, 1) to achieve overall ordering.

/**
 * 希尔排序
 */
void shellSort(int a[], int n)
{
    int gap;
    for (gap = n/2; gap > 0; gap /= 2) {
        int i;
        for (i = gap; i < n; i++) {
            int key = a[i], j;
            for (j = i; j >= gap && key < a[j-gap]; j -= gap) {
                a[j] = a[j-gap];
            }
            a[j] = key;
        }
    }
}

3 Selection Sort

Selection sort repeatedly selects the smallest remaining element and places it at the current position; both best and worst cases are O(N²).

/**
 * 选择排序
 */
void selectSort(int a[], int n)
{
    int i, j, min, tmp;
    for (i = 0; i < n-1; i++) {
        min = i;
        for (j = i+1; j < n; j++) {
            if (a[j] < a[min])
                min = j;
        }
        if (min != i)
            tmp = a[i], a[i] = a[min], a[min] = tmp; // 交换a[i]和a[min]
    }
}

4 Bubble Sort

Bubble sort performs n‑1 passes, bubbling the smallest element to the front each pass; its worst‑case complexity is O(N²). An optimized version stops early when no swaps occur.

/**
 * 冒泡排序-经典版
 */
void bubbleSort(int a[], int n)
{
    int i, j, tmp;
    for (i = 0; i < n; i++) {
        for (j = n-1; j >= i+1; j--) {
            if (a[j] < a[j-1])
                tmp = a[j], a[j] = a[j-1], a[j-1] = tmp;
        }
    }
}
/**
 * 冒泡排序-优化版
 */
void betterBubbleSort(int a[], int n)
{
    int tmp, i, j;
    for (i = 0; i < n; i++) {
        int sorted = 1;
        for (j = n-1; j >= i+1; j--) {
            if (a[j] < a[j-1]) {
                tmp = a[j], a[j] = a[j-1], a[j-1] = tmp;
                sorted = 0;
            }
        }
        if (sorted)
            return;
    }
}

5 Counting Sort

Counting sort works when the input range is limited; it runs in O(N) time by counting occurrences of each value.

/**
 * 计数排序
 */
void countingSort(int a[], int n)
{
    int i, j;
    int *b = (int *)malloc(sizeof(int) * n);
    int k = maxOfIntArray(a, n); // 求数组最大元素
    int *c = (int *)malloc(sizeof(int) * (k+1));  // 辅助数组

    for (i = 0; i <= k; i++)
        c[i] = 0;

    for (j = 0; j < n; j++)
        c[a[j]] = c[a[j]] + 1; // c[i]包含等于i的元素个数

    for (i = 1; i <= k; i++)
        c[i] = c[i] + c[i-1];  // c[i]包含小于等于i的元素个数

    for (j = n-1; j >= 0; j--) {  // 赋值语句
        b[c[a[j]]-1] = a[j]; // 结果存在b[0...n-1]中
        c[a[j]] = c[a[j]] - 1;
    }

    for (i = 0; i < n; i++) {
        a[i] = b[i];
    }

    free(b);
    free(c);
}

6 Merge Sort

Merge sort uses a divide‑and‑conquer strategy; the recursive version splits the array, sorts each half, then merges. Time complexity is O(N log N).

/*
 * 归并排序-递归
 */
void mergeSort(int a[], int l, int u)
{
    if (l < u) {
        int m = l + (u-l)/2;
        mergeSort(a, l, m);
        mergeSort(a, m + 1, u);
        merge(a, l, m, u);
    }
}
/*
 * 归并排序合并函数
 */
void merge(int a[], int l, int m, int u)
{
    int n1 = m - l + 1;
    int n2 = u - m;
    int left[n1], right[n2];
    int i, j;
    for (i = 0; i < n1; i++)
        left[i] = a[l + i];
    for (j = 0; j < n2; j++)
        right[j] = a[m + 1 + j];
    i = j = 0;
    int k = l;
    while (i < n1 && j < n2) {
        if (left[i] < right[j])
            a[k++] = left[i++];
        else
            a[k++] = right[j++];
    }
    while (i < n1)
        a[k++] = left[i++];
    while (j < n2)
        a[k++] = right[j++];
}

Non‑recursive (bottom‑up) merge sort repeatedly merges sub‑arrays of size 2, 4, 8, … until the whole array is sorted.

/**
 * 归并排序-非递归
 */
void mergeSortIter(int a[], int n)
{
    int i, s = 2;
    while (s <= n) {
        i = 0;
        while (i + s <= n) {
            merge(a, i, i + s/2 - 1, i + s - 1);
            i += s;
        }
        // 处理末尾残余部分
        merge(a, i, i + s/2 - 1, n - 1);
        s *= 2;
    }
    // 最后再从头到尾处理一遍
    merge(a, 0, s/2 - 1, n - 1);
}

7 Radix Sort and Bucket Sort

Radix sort processes each digit of the numbers using a stable sort (e.g., counting sort), achieving linear time when the number of digits is constant and the range of each digit is O(N). Bucket sort distributes uniformly distributed inputs into N buckets and sorts each bucket (typically with insertion sort), also running in linear time under uniform distribution.

Both algorithms are covered briefly; detailed implementations can be found in Chapter 8 of "Introduction to Algorithms".

Reference

《算法导论》 https://www.cnblogs.com/liushang0419/archive/2011/09/19/2181476.html