首页 / 算法 / 算法导论笔记，第2章 循环不变式与插入排序

算法导论笔记，第2章 循环不变式与插入排序

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了算法导论笔记，第2章 循环不变式与插入排序，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2028字，纯文字阅读大概需要3分钟。

内容图文

本章的重点是循环不变式。也就是在一个循环中存在着某些不变的量。它类似于数学归纳法的归纳步骤：

  1. 初始化：在循环第一轮迭代开始之前，应该是正确的。
  2. 保持：如果在循环的某一次迭代开始之前它是正确的，那么在下一次迭代开始之前，它也应该保持正确。
  3. 终止：当循环结束时，不变式给了我们一个有用的性质，它有助于说明算法是正确的。

我们在设计一个算法、分析一个算法的时候，要适当应用循环不变式来简化分析工作、证明算法的正确性。

书中举例插入排序：

　n个元素的待排序数组A，下标是从1到n。 j从2开始一直遍历到大于n（此时会退出循环）。循环不变式的量是：A[1...j-1]这个子数组是已排序的。 

  1. 初始化：j=2, 此时A[1...j-1]只包含一个元素，所以它是正确的（已排序的）。
  2. 保持：通过将A[j-1], A[j-2]....等元素向右移动一个位置，直到找到A[j]的适当位置为止，来保持A[1...j-1]已排序。
  3. 终止：当j大于n时，外层for循环会结束。

通过这个简单的约束规则，可以很容易地默写出插入排序的实现代码：

                void insert_sort(int* A, int n) {
  for (int j = 1; j < n;j++) {
    int key = A[j];
    int i = j-1;
    for (; i>=0 && key < A[i]; i--) {
        A[i+1] = A[i];
    }
    A[i+1] = key;
  }
}

存在着两层for循环，所以算法的时间复杂度是O(n^2). 
只用了一个临时变量key, 所以空间复杂度是O(1)

扩展思考一下：插入排序可以对链表进行排序吗？

应该是可以的。假设存在链表list. 每次从list中摘取一个节点，将它插入到sortedList中，一直到list为空。循环不变式sortedList是有序的链表。

于是循环不变式是：

  1. 初始化：一开始sortedList是list的头结点，所以它是正确的（已排序的）。
  2. 保持：通过依次从list中摘取一个节点，在sortedList的合适位置中插入，来保持sortedList是有序的。
  3. 终止：list没有更多节点是，外层for循环会结束。

先定义一下list

typedef struct List{
  int item;
  struct List* next;
} List;
List* AddList(List* l, int item);
#include "list.h"
List* AddList(List* l, int item) {
  List* node = new(List);// (List*) malloc(sizeof(List));
  node->item = item;
  node->next = 0;
  if (l) {
    node->next = l->next;
    l->next = node;
    return l;
  }
  return node;
}

再来实现一下链表的插入排序

List* insert_sortL(List* list) {
  List* head = list;
  if (head == NULL) {
    return NULL;
  }

  List* sortedList =  head;//初始化，sortedList只有一个节点。
  List* j = head->next;
  sortedList->next = NULL;//将head从list中摘取出来for (; j != NULL;) {
    List* current = j;//注意摘取节点j(current)的次序
    j = j->next;
    current->next = NULL;
    int k = current->item;
    if (k < sortedList->item) {//如果比sortedList的头结点小，则需要更新头结点
      current->next = sortedList;
      sortedList = j;
      continue;
    }

    List* i = sortedList;//将current插入到sortedList的合适位置for (; i->next != NULL && k > i->next->item; i = i->next) {
    }
    current->next = i->next;
    i->next = current;
  }
  return sortedList;
}

 

原文：https://www.cnblogs.com/jackson-zhou/p/8322301.html

内容总结

以上是互联网集市为您收集整理的算法导论笔记，第2章 循环不变式与插入排序全部内容，希望文章能够帮你解决算法导论笔记，第2章 循环不变式与插入排序所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

扫描二维码推送至手机访问。

本文链接：https://qyyshop.com/info/1219649.html

来源：【匿名】