c语言直接插入排序

直接插入排序

#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]即可