C语言之直接排序算法

目录

一 简介

二 代码实现

三 时空复杂度

A.时间复杂度：

B.空间复杂度：

C.总结：

一 简介

直接插入排序是一种简单的排序算法，其基本思想是将待排序的数组元素视为一个已排序部分和一个无序部分。开始时，假设第一个元素是有序序列，然后将后面的元素逐个插入到前面已经排序好的序列中适当的位置上，使得整个序列逐渐变得有序。

二 代码实现

// 假设有一个整型数组 ListData[] 和它的长度 ListLength

void insertionSort(int ListData[], int ListLength) {
    // 从第二个元素开始遍历数组
    for (int i = 1; i < ListLength; i++) {
        // 记录当前需要插入的值
        int currentElement = ListData[i];
        // 插入点初始化为当前元素前一个位置
        int j = i - 1;

        // 将大于当前元素的数向右移动，直到找到合适的位置或到达有序序列的起点
        while (j >= 0 && ListData[j] > currentElement) {
            // 移动数据
            ListData[j + 1] = ListData[j];
            // 向左移动一位
            j--;
        }

        // 将当前元素插入到正确位置
        ListData[j + 1] = currentElement;
    }
}

// 使用示例：
int main() {
    int arr[] = {54, 26, 93, 17, 77, 31, 44, 55, 20};
    int n = sizeof(arr) / sizeof(arr[0]);

    insertionSort(arr, n);

    // 输出排序后的数组
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }

    return 0;
}

通过上述代码，insertionSort 函数首先遍历数组中的每一个元素，对于每个未排序的元素（从索引1开始），它将其与左侧已排序部分进行比较，如果比某个元素大，则该元素后移，直至找到正确的位置并将当前元素插入。这个过程反复进行，直到所有元素都被插入到它们应有的位置，从而完成整个数组的排序。

三 时空复杂度

A.时间复杂度：

• 最好情况（即输入数组已经是有序的）：在这种情况下，每个元素只需比较一次就能找到自己的位置，因此算法需要进行n-1次比较（n为数组长度）。所以最好情况下的时间复杂度为。

• 最坏情况（即输入数组是逆序的）：对于每一个待插入的元素，都需要与前面所有元素进行比较，总共需要进行的比较次数为，这是一个等差数列求和，结果为。因此，最坏情况下的时间复杂度为。

• 平均情况：直接插入排序的平均时间复杂度也为。

B.空间复杂度：

• 直接插入排序是一种原地排序算法，它只需要一个很小的临时空间用于交换元素，不需要额外的数据结构存储数据。因此，其空间复杂度为，是非常节省空间的一种排序算法。

C.总结：

总结来说，直接插入排序在处理小规模或者近乎有序的数据时效率较高，但在处理大规模或者无序程度较高的数据时，由于其时间复杂度较高，可能不是最佳选择。