c语言插入排序_插入排序

1. 工作原理“插入排序”算法&＃xff0c;它与生活中的“扑克牌”紧密相关。相信玩过扑克牌的读者应该非常清楚&＃xff0c;每次我们仅考虑一个数据(张牌)&＃xff0c;并将其插入到已排好序的扑克适当位置中。在插入该数据(扑克牌)时候&＃xff0c;先将较大的元素一个个移到右边。我们将所有数据分为两个部分&＃xff1a;已排序部分与未排序部分。

▲图片来自HappyCoders.通俗说&＃xff1a;“插入排序的工作原理是将未排序数组中的元素插入到已排序数组的子数组中&＃xff0c;每次一项。”假如有一个数组arr&＃xff0c; 其中各元素位置以及值如下:200,  45,  3,  65,  3,  67,  120则使用“插入排序”算法对该数组元素进行升序排序时候&＃xff0c;其过程如下:(1) 将数组arr分为左侧的“已排序部分”和“右侧的未排序部分”。已排序的部分已经包含了开头的第一个元素&＃xff0c;因为具有单个元素的数组总是可以认为是已排序的。

(2)检查“未排序部分”区域的第一个元素(此处是45)&＃xff0c;将它与紧邻的“已排序”的左侧区域进行一一比较&＃xff0c;以确定其在“已排序”区域的插入位置。此处45<200&＃xff0c;因此需要将45移动到200位置的前面。

(3) 继续来看“未排序”区域的第一个元素(此处是3)。将它分别一一与“已排序”区域的元素进行比较。发现&＃xff0c;3比左侧“已排序”区域的45、200都小。因此该元素(3)需放在45的前面&＃xff0c;我们将45、200分别向后移动一个位置。流一个空间给3(编码中&＃xff0c;根据索引,即数组下标直接交换元素就行&＃xff0c;不需要移动数组元素)。

(4) 继续来看“未排序”区域的第一个元素(此处是65)。将它分别一一与“已排序”区域的元素进行比较。发现&＃xff0c;65比3大, 比200小。因此插入的位置是在45与200之间。分别将45、200向后移动一个位置空间&＃xff0c;将之前45的空间位置用于存储65。

依次类推&＃xff0c;直到“未排序”区域元素所有元素均被一一与“已排序”区域元素比较。最终结果如下&＃xff1a;

2. 实现C语言实现:

void InsertionSort(int *arr, int len){ assert(arr); int i &＃61; 0, j &＃61; 0, key &＃61; 0; for(i &＃61; 1; i 0 && arr[j-1] > arr[j]){ key &＃61; arr[j]; arr[j] &＃61; arr[j-1]; arr[j-1] &＃61; key; j--; } } }3. 时间复杂度

     插入排序算法的在最理想情况下&＃xff0c;复杂度是&＃xff1a;O(n)&＃xff1b;最极端情况下是&＃xff1a;O(n^2. 即n的平方)。

理想情况下:
     插入排序执行两种操作:扫描列表&＃xff0c;比较每对元素&＃xff0c;如果元素顺序不对&＃xff0c;则交换元素。每一次操作都会影响算法的运行时间。如果输入数组已经排好序&＃xff0c;插入排序将比较O(N)个元素&＃xff0c;并且不执行交换。因此&＃xff0c;在最好的情况下&＃xff0c;插入排序运行时间为O(N)。

     极端情况下:     当待排序的所有元素是降序排列时&＃xff0c;是最为极端情况。要插入最后一个元素&＃xff0c;我们最多需要ñ-1个 比较和最多 ñ-1个交换。要插入倒数第二个元素&＃xff0c;我们最多需要ñ-2 比较和最多 ñ-2交换等等。因此&＃xff0c;执行插入排序所需的操作数为&＃xff1a;2×(1&＃43;2&＃43;⋯&＃43;n−2&＃43;n−1)。它遵循以下规则&＃xff1a;

因此平均情况与最坏情况具有相同的时间复杂性&＃xff0c;即O(n^2. 即n的平方)。4. 空间复杂度

     插入排序是一种稳定的排序&＃xff0c;其空间复杂度为O(1)。所谓“空间复杂度(Space complexity)” &＃xff0c;它是处理算法分析时使用的一个术语。它是一个表达式&＃xff0c;描述执行算法预期要解决的任务所需的内存量(空间)。例如&＃xff0c;插入排序的空间复杂度为O(1)&＃xff0c;因为它不需要额外的内存分配来对所提供的集合进行排序。