Posts

Showing posts from 2016

SICP Note Chapter 1

Image
1. S ubstitution model 代换模型( https://mitpress.mit.edu/sicp/full-text/sicp/book/node10.html ) 并不指实际中使用的,而是用于方便理解的一个较为粗糙的syntax analysis模型 其中代换分为正则序代换(normal-order evaluation, 把所有procedure 展开成基本运算符 最后运算) 以及应用序代换(applicative-order evaluation 先计算最外层procedure里的运算数的值 然后再展开procedure) 2. S ICP里对递归和迭代的解释 递归: (define (factorial n) (if (= n 1) 1 (* n (factorial (- n 1))))) 迭代: (define (factorial n) (fact-iter 1 1 n)) (define (fact-iter product counter max-count) (if (> counter max-count) product (fact-iter (* counter product) (+ counter 1) max-count))) This type of process, characterized by a chain of deferred operations, is called a recursive process. Carrying out this process requires that the interpreter keep track of the operations to be performed later on. In the computation of n!, the length of the chain of deferred multiplications, and hence the amount of information needed to keep track of it, grows linearly with n (is propo

常见的排序算法及实现

本文配合 visualgo 食用更佳 堆排序 快速排序 归并排序 冒泡排序 选择排序 插入排序 堆排序 一般用一维数组来实现,为方便下标为0的位置空出,数据内容从下标为1开始。(如果要从0开始也是可行的) 迭代下面步骤: 调整乱序数组为一个大顶堆 交换下标为1(即最大的元素)与下标最后的元素内容,这时不满足堆的定义 调整剩余部分为大顶对 public class heapsort { public static void main ( String args []) { int [] num = new int [] { - 1 , 49 , 38 , 65 , 97 , 76 , 13 , 55 }; sort ( num ); for ( int i : num ) { System . out . print ( i + " " ); } } static void heapAdjust ( int start , int end , int [] array ) { int temp = array [ start ]; for ( int j = 2 * start ; j <= end ; j *= 2 ) { if ( j < end ) { // 说明还有右子树 if ( array [ j ] < array [ j + 1 ]) j += 1 ; // 让j指向左右子树中较大的那个 } if ( temp >= array [ j ]) // 满足大顶堆的要求不需要调整 break ; array [ start ] = array [ j ]; // 调整顶端与子树内容 start = j ; // 继续循环 } array [ start ] = temp ; } static void sort ( int [] num ) {