C语言|工具函数

一、交换函数（数据类型可自定义）

// 交换 int
void swapInt(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

// 交换 char
void swapChar(char *a, char *b) {
    char temp = *a;
    *a = *b;
    *b = temp;
}

二、数组/字符串操作函数

1.逆置

// 逆置 数组
void reverseArray(int *nums, int start, int end) {
    while (start < end) {
        swapInt(&nums[start], &nums[end]);
        start++;
        end--;
    }
}

// 逆置 字符串
void reverseString(char *s, int start, int end) {
    while (start < end) {
        swapChar(&s[start], &s[end]);
        start++;
        end--;
    }
}

2.二分查找（要求：数组有序）

// 二分查找
int binarySearch(int *nums, int n, int target) {
    int left = 0, right = n - 1;
    while (left <= right) {
        int mid = left + ((right - left) >> 1); // 避免溢出
        if (nums[mid] == target) return mid;
        else if (nums[mid] < target) left = mid + 1;
        else right = mid - 1;
    }
    return -1; // 未找到
}

3.前缀和：区间[i,j]和 = prefix[j+1] – prefix[i]

// 前缀和
void prefixSum(int *nums, int n, int *prefix) {
    prefix[0] = 0;
    for (int i = 0; i < n; i++) {
        prefix[i+1] = prefix[i] + nums[i];
    }
}

三、数论常用函数

1.最大公约数

// 最大公约数
int gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a % b);
}

2.最小公倍数

// 最小公倍数
int lcm(int a, int b) {
    return a * b / gcd(a, b);
}

3.快速幂

// 快速幂（大数幂运算，避免溢出）
long long quickPow(long long base, int exp) {
    long long res = 1;
    while (exp > 0) {
        if (exp % 2 == 1) res *= base;
        base *= base;
        exp /= 2;
    }
    return res;
}

四、排序函数（只保留性能优秀与具有特殊作用的排序算法）

1.快速排序（性能优秀，排序的默认实现方式，不过是不稳定的排序算法）

// 快速排序
void quickSort(int *nums, int left, int right) {
    if(left>=right) return;
    int i=left,j=right;
    int pIdx=left+((right-left)>>1);
    int p=nums[pIdx];
    while(i<j){
		while(i<j && nums[j]>=p) --j;
		while(i<j && nums[i]<=p) ++i;
		if(i<j) swapInt(&nums[i],&nums[j]);
	}
	swapInt(&nums[pIdx],&nums[i]);
	quickSort(nums,left,i-1);
	quickSort(nums,i+1,right);
	return;
}

2.归并排序（稳定排序，适合需要保留相对顺序的场景）

// 归并排序
void merge(int *nums, int left, int mid, int right) {
    int len = right - left + 1;
    int *temp = (int *)malloc(len * sizeof(int));
    int i = left, j = mid + 1, k = 0;
    while (i <= mid && j <= right) {
        temp[k++] = nums[i] <= nums[j] ? nums[i++] : nums[j++];
    }
    while (i <= mid) temp[k++] = nums[i++];
    while (j <= right) temp[k++] = nums[j++];
    for (k = 0; k < len; k++) {
        nums[left + k] = temp[k];
    }
    free(temp);
}

void mergeSort(int *nums, int left, int right) {
    if (left >= right) return;
    int mid = (left + right) / 2;
    mergeSort(nums, left, mid); 
    mergeSort(nums, mid + 1, right);
    merge(nums, left, mid, right);
}

3.堆排序（TopK问题专用，无需额外空间）

// 堆排序
void heapify(int *nums, int n, int i) {
    int largest = i;
    int left = 2 * i + 1;
    int right = 2 * i + 2;
    if (left < n && nums[left] > nums[largest]) largest = left;
    if (right < n && nums[right] > nums[largest]) largest = right;
    if (largest != i) {
        swapInt(&nums[i], &nums[largest]);
        heapify(nums, n, largest);
    }
}

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