经常使用的排序算法

一、直接插入排序

#include <stdio.h>void insert_sort(int arr[], int n){int i, j, tmp;for (i = 1; i < n; i++){tmp = arr[i];j = i - 1;while (j >= 0 && arr[j] > tmp){ // 将要插入的元素与数组中的元素比较（从后向前比）arr[j + 1] = arr[j];  // 将排列好的数组后移j--;}arr[j + 1] = tmp; // 不满足以上条件，即待插入元素tmp比数组中的某个元素大，插在它后面}
}int main(){int arr[] = {5, 2, 8, 9, 1, 3};int n = sizeof(arr) / sizeof(arr[0]);printf("Before sorting: ");for (int i = 0; i < n; i++){printf("%d ", arr[i]);}insert_sort(arr, n);printf("\nAfter sorting: ");for (int i = 0; i < n; i++){printf("%d ", arr[i]);}return 0;
}

arr是待排序的数组，n是数组的长度。算法从数组的第二个元素开始遍历，将当前元素存储到临时变量tmp中，并将j初始化为已排序序列的最后位置。然后，算法通过比较tmp和已排序序列中的元素，找到合适的插入位置，并将大于tmp的元素往后移动一位。最后，将tmp插入到合适的位置。

插入排序算法的时间复杂度为O(n^2)，不适用于大规模数据排序。但对于小规模或基本有序的数据，插入排序是一种高效的排序算法。

以上的排序是升序排序，你能把它改成降序排序吗？ >>> 把tmp<arr[j]改为tmp>arr[j]即可

二、选择排序

#include <stdio.h>void select_sort(int arr[], int n){int i, j, min_idx, tmp;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;}}// 将最小元素与当前位置交换tmp = arr[i];arr[i] = arr[min_idx];arr[min_idx] = tmp;}
}int main(){int arr[] = {5, 2, 8, 9, 1, 3};int n = sizeof(arr) / sizeof(arr[0]);printf("Before sorting: ");for (int i = 0; i < n; i++){printf("%d ", arr[i]);}selection_sort(arr, n);printf("\nAfter sorting: ");for (int i = 0; i < n; i++){printf("%d ", arr[i]);}return 0;
}

三、冒泡排序

#include <stdio.h>void bubble_sort(int arr[], int n) {for (int i = 0; i < n - 1; i++) {// 标志位，用于判断是否发生了交换操作int flag = 0;for (int 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;flag = 1;}}// 如果没有发生交换操作，说明列表已经有序，提前结束排序if (flag == 0) {break;}}
}int main() {int nums[] = {5, 2, 8, 12, 3};int n = sizeof(nums) / sizeof(nums[0]);bubble_sort(nums, n);for (int i = 0; i < n; i++) {printf("%d ", nums[i]);}return 0;
}

四、希尔排序

#include <stdio.h>// 希尔排序函数
void shell_sort(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;}}
}// 测试希尔排序
int main() {int arr[] = {64, 34, 25, 12, 22, 11, 90};int n = sizeof(arr) / sizeof(arr[0]);printf("原始数组：\n");for (int i = 0; i < n; i++) {printf("%d ", arr[i]);}shell_sort(arr, n);printf("\n排序后的数组：\n");for (int i = 0; i < n; i++) {printf("%d ", arr[i]);}return 0;
}

希尔排序的性能取决于增量序列的选择。通过使用更优化的增量序列，可以进一步提高希尔排序的性能。需要注意的是，希尔排序并不是稳定的排序算法。

五、快速排序

#include <stdio.h>void quickSort(int arr[], int low, int high) {if (low < high) {// 将数组分为两部分并获取分割点int pivot = partition(arr, low, high);// 递归对左侧子数组排序quickSort(arr, low, pivot - 1);// 递归对右侧子数组排序quickSort(arr, pivot + 1, high);}
}int partition(int arr[], int low, int high) {// 取最后一个元素作为分割点int pivot = arr[high];int i = low;for (int j = low; j < high; j++) {if (arr[j] < pivot) {// 交换 arr[i] 和 arr[j]int temp = arr[i];arr[i] = arr[j];arr[j] = temp;i++;}}// 交换 arr[i] 和 arr[high]int temp = arr[i];arr[i] = arr[high];arr[high] = temp;return i;
}int main() {int arr[] = {10, 80, 30, 90, 40, 50, 70};int n = sizeof(arr) / sizeof(arr[0]);quickSort(arr, 0, n - 1);printf("Sorted array: ");for (int i = 0; i < n; i++)printf("%d ", arr[i]);return 0;
}

在快速排序算法中，有两个关键的函数：quickSort() 和 partition()。

quickSort() 函数是快速排序算法的入口函数，它接受一个数组、起始索引 low 和结束索引 high 作为参数。该函数通过递归调用自身来实现对数组的排序。具体过程如下：

1. 如果 low 小于 high，意味着仍然存在待排序的子数组。
2. 调用 partition() 函数将数组分割为两部分，并获取分割点 pivot。
3. 递归调用 quickSort() 函数对左侧子数组进行排序（起始索引为 low，结束索引为 pivot - 1）。
4. 递归调用 quickSort() 函数对右侧子数组进行排序（起始索引为 pivot + 1，结束索引为 high）。

partition() 函数用于确定分割点，并将数组分割为左右两部分。具体过程如下：

1. 选择数组的最后一个元素 arr[high] 作为分割点 pivot。
2. 初始化索引 i 为 low。
3. 使用索引 j 遍历数组元素，从 low 到 high - 1。
4. 如果 arr[j] 小于 pivot，则交换 arr[i] 和 arr[j] 的值，并将 i 加1。
5. 遍历结束后，交换 arr[i] 和 arr[high] 的值。
6. 返回 i 作为新的分割点。

快速排序算法通过不断选择分割点，并递归处理左右两部分，最终完成整个数组的排序。

六、c语言库stdlib中自带的qsort

#include <stdio.h>
#include <stdlib.h>// 比较函数，用于qsort排序
int compare(const void *a, const void *b) {return *(int *)a - *(int *)b;
}int main() {int arr[] = {9, 5, 7, 3, 1};int size = sizeof(arr) / sizeof(int);printf("Before sorting:");for (int i = 0; i < size; i++) {printf("%d ", arr[i]);}qsort(arr, size, sizeof(int), compare);printf("\n After sorting: ");for (int i = 0; i < size; i++) {printf("%d ", arr[i]);}return 0;
}

功能：进行排序

函数原型：void qsort(void *base, size_t nitems, size_t size, int (*compare)(const void , const void))

参数：

        base - 指向要排序的数组的第一个元素的指针。

        nitems - 由 base 指向的数组中元素的个数。

        size - 数组中每个元素的大小，以字节为单位。

        compare - 用来比较两个元素的函数。（自定义）

                                        制作不易，希望大家多多点赞评论支持。