插入排序、希尔排序、冒泡排序、快速排序、简单选择排序、堆排序、归并排序、基数排序的C语言实现

#include <stdio.h>
#include <stdlib.h>
 
// 插入排序
void InsertSort(int A[], int n) {
    int i, j, temp;
    for (i = 1; i < n; i++) {
        temp = A[i];
        j = i - 1;
        while (j >= 0 && A[j] > temp) {
            A[j + 1] = A[j];
            j--;
        }
        A[j + 1] = temp;
    }
}
 
// 二分插入排序
void InsertSort2(int A[], int n) {
    int i, j, low, high, mid, temp;
    for (i = 1; i < n; i++) {
        temp = A[i];
        low = 0;
        high = i - 1;
        while (low <= high) {
            mid = (low + high) / 2;
            if (A[mid] > temp)
                high = mid - 1;
            else
                low = mid + 1;
        }
        for (j = i - 1; j >= high + 1; --j)
            A[j + 1] = A[j];
        A[high + 1] = temp;
    }
}
 
// 希尔排序
void ShellSort(int A[], int n) {
    int i, j, gap;
    for (gap = n / 2; gap > 0; gap /= 2) {
        for (i = gap; i < n; i++) {
            int temp = A[i];
            for (j = i; j >= gap && A[j - gap] > temp; j -= gap) {
                A[j] = A[j - gap];
            }
            A[j] = temp;
        }
    }
}
 
// 冒泡排序
void BubbleSort(int A[], int n) {
    int i, j, temp;
    for (i = 0; i < n - 1; i++) {
        for (j = 0; j < n - i - 1; j++) {
            if (A[j] > A[j + 1]) {
                temp = A[j];
                A[j] = A[j + 1];
                A[j + 1] = temp;
            }
        }
    }
}
 
// 快速排序（递归实现）
void QuickSort(int A[], int low, int high) {
    int i = low, j = high;
    int pivot = A[(low + high) / 2];
    int temp;
    while (i <= j) {
        while (A[i] < pivot) i++;
        while (A[j] > pivot) j--;
        if (i <= j) {
            temp = A[i];
            A[i] = A[j];
            A[j] = temp;
            i++;
            j--;
        }
    }
    if (low < j) QuickSort(A, low, j);
    if (i < high) QuickSort(A, i, high);
}
void QuickSortWrapper(int A[], int n) {
    QuickSort(A, 0, n - 1);
}
 
// 简单选择排序
void SelectionSort(int A[], int n) {
    int i, j, minIdx, temp;
    for (i = 0; i < n - 1; i++) {
        minIdx = i;
        for (j = i + 1; j < n; j++) {
            if (A[j] < A[minIdx]) {
                minIdx = j;
            }
        }
        temp = A[i];
        A[i] = A[minIdx];
        A[minIdx] = temp;
    }
}
 
// 堆排序（最大堆）
void Heapify(int A[], int n, int i) {
    int largest = i;
    int left = 2 * i + 1;
    int right = 2 * i + 2;
    if (left < n && A[left] > A[largest])
        largest = left;
    if (right < n && A[right] > A[largest])
        largest = right;
    if (largest != i) {
        int swap = A[i];
        A[i] = A[largest];
        A[largest] = swap;
        Heapify(A, n, largest);
    }
}
void HeapSort(int A[], int n) {
	int i;
    for (i = n / 2 - 1; i >= 0; i--)
        Heapify(A, n, i);
    for (i = n - 1; i > 0; i--) {
        int swap = A[0];
        A[0] = A[i];
        A[i] = swap;
        Heapify(A, i, 0);
    }
}
// 注意：上面的Heapify函数在HeapSort中被错误地调用了，因为Heapify的原型应该是接受父节点索引，
// 但在HeapSort中我们需要重新堆化从0到i-1的子树，所以我们需要一个不同的方法或者调整Heapify的调用方式。
// 下面的HeapSort修正版使用了一个辅助函数来调整堆。
void HeapAdjust(int A[], int n, int i) {
    int largest, left, right;
    largest = i;
    left = 2 * i + 1;
    right = 2 * i + 2;
    if (left < n && A[left] > A[largest])
        largest = left;
    if (right < n && A[right] > A[largest])
        largest = right;
    if (largest != i) {
        int swap = A[i];
        A[i] = A[largest];
        A[largest] = swap;
        HeapAdjust(A, n, largest);
    }
}
void HeapSortFixed(int A[], int n) {
	int i;
    for ( i = n / 2 - 1; i >= 0; i--)
        HeapAdjust(A, n, i);
    for ( i = n - 1; i > 0; i--) {
        int swap = A[0];
        A[0] = A[i];
        A[i] = swap;
        HeapAdjust(A, i, 0);
    }
}
 
// 归并排序（递归实现）
void Merge(int A[], int left, int mid, int right) {
    int n1 = mid - left + 1;
    int n2 = right - mid;
	int i,j,k;
    int* L = (int*)malloc(n1 * sizeof(int));
    int* R = (int*)malloc(n2 * sizeof(int));
    for ( i = 0; i < n1; i++)
        L[i] = A[left + i];
    for ( j = 0; j < n2; j++)
        R[j] = A[mid + 1 + j];
    i = 0, j = 0, k = left;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            A[k] = L[i];
            i++;
        } else {
            A[k] = R[j];
            j++;
        }
        k++;
    }
    while (i < n1) {
        A[k] = L[i];
        i++;
        k++;
    }
    while (j < n2) {
        A[k] = R[j];
        j++;
        k++;
    }
    free(L);
    free(R);
}
void MergeSort(int A[], int left, int right) {
    if (left < right) {
        int mid = left + (right - left) / 2;
        MergeSort(A, left, mid);
        MergeSort(A, mid + 1, right);
        Merge(A, left, mid, right);
    }
}
void MergeSortWrapper(int A[], int n) {
    MergeSort(A, 0, n - 1);
}


int main() {
    int A[10] = {2, 35, 1, 45, 51, 3, 56, 12, 8, 5};
	int i;
    // 输出排序后的数组
	HeapSortFixed(A,10);
    for (i = 0; i < 10; i++) {
        printf("%d ", A[i]);
    }
    printf("\n");

    return 0;
}