1.用伪代码描述直接插入排序算法,指出循环不变 量,进而证明算法的正确性
时间: 2024-09-20 10:06:25 浏览: 15
直接插入排序是一种简单直观的排序算法,其基本思想是将数组分为已排序区和未排序区,每次从未排序区取出第一个元素,在已排序区找到合适的位置插入。以下是用伪代码描述的直接插入排序:
```pseudo
function insertionSort(array):
for i from 1 to length(array) - 1:
currentElement = array[i]
j = i - 1
// 循环不变量:前i个元素已排好序,currentElement处在正确位置或者已经找到了比它小的元素
while j >= 0 and array[j] > currentElement:
array[j + 1] = array[j]
j = j - 1
array[j + 1] = currentElement // 插入当前元素到正确位置
```
循环不变量:在第i轮迭代开始时,前i个元素按照升序排列,`array[0..i-1]`部分是有序的。同时,`array[i]`已经与`array[0..i-1]`中的元素进行了比较,并在必要时移动了位置。
算法正确性的证明:
1. 当i=1时,只有一个元素,自然有序,所以初始化时满足循环不变量。
2. 在每一次循环中,我们保证了当前元素`array[i]`会被放置在已排序的部分的正确位置,因为我们在`j`处寻找并交换大于`currentElement`的值。
3. 随着`i`递增,每一步都只影响到`array[i]`及其后面的元素,不会破坏之前已经建立的有序状态。
4. 循环结束后,整个数组都被遍历并排序完成,因此算法正确有效。
阅读全文