算法导论学习1

    技术2022-05-14  1

    第一章:算法在计算中的作用

     

    算法的定义:简单的说就是定义良好的计算过程,由输入得到输出!

    算法的作用:应用非常广泛,许多问题都涉及到算法!

     

    算法的重要性:是否拥有扎实的算法知识和技术基础,是区分真正熟练的程序员与新手的一项重要特征。

     

      

             第二章  算法入门

    学习算法的目的,不仅仅是很快理解算法然后编出相应的程序,很重要的一点是算法的设计上面,因为设计算法要考虑到比如时间复杂度,空间复杂度等因素,而会不会正确分析,事先估计算法的这些因此,也是非常重要的,这也是算法导论这本书重点介绍的一个内容!

     

    2.1 插入排序

    插入排序是对少量元素进行排序的有效算法!插入排序的关键在于,还是利用原来的数组,进行增量排序,首先通过比较后面的元素与已经排好顺序的数组的元素,将当前比较的元素插入到适当的位置,插入的过程其实就是移动数组元素的过程!

    其实现程序如下:

    /*------------------------------------------------- * Copyright: 2011-2013 * FileName : InsertSort.cpp * Des: C++实现插入排序算法 * * Author: 马小波 * Date: 2011-4-1 * History: 1.0 * Other : ---------------------------------------------------*/ #include <iostream> #include <assert.h> using std::cout; using std::endl; const int SORTNUM = 10;//the sort number template<class T> T* InsertSort (T* SortArray); int main (int argv, char ** argc) { int i; int SortArray[SORTNUM] = {5,2,1,6,4,3,12,11,7,9};//简单int数组,没有实现模板数组 InsertSort(SortArray); cout<<"the sorted Array :"; for (i = 0; i < SORTNUM; i++) { cout.width(3); cout<<SortArray[i]; } cout<<endl; return 0; } /*---------------------------------------------------------- * Function: InsertSort * Des: 插入排序实现函数 * Call: * Called By: main * Input: T* SortArray 待排序数组 * OutPut: * Return: T* 排好序的数组 * Author: 马小波 2011-4-1 * Other : -----------------------------------------------------------*/ template<class T> T* InsertSort (T* SortArray) { assert(SortArray != NULL); int i, j; T * temp; temp = SortArray;//copy point T key = 0;//the key volue for (j = 1; j < SORTNUM; j++) { key = temp[j];//当前要插入的键值 //已经排好序的序列 for (i = j - 1; i >= 0; i--) { if (temp[i] > key)//将当前temp[i]移向后一位 { temp[i+1] = temp[i]; } else { break;//找到要插入键值的位置 } } temp[i+1] = key;//将键值插入到当前位置 } return temp; }   

    循环不变式和插入排序的正确性分析:

    循环不变式的性质:

    1)初始化:在第一轮循环之前,应该正确。在第一次循环之前,已经排列好的子数组A[1],当然正确。

    2)保持:如果循环的某一次迭代开始前正确,那么下一次迭代开始前也应该是正确的。下标j代表要插入的元素,在每一次循环结束后,内循环代表的子数组的元素按照顺序排列好,外循环剩余的元素则是剩余没有排好顺序的,整个数组的元素也是不变的,当然除了顺序!因此可以保持在循环迭代过程中的这个性质。

    3)终止:循环全部结束后,数组已经全部排列好顺序!


    最新回复(0)