直接插入排序
#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]即可