学编程,来源栈;先学习,再交钱
当前系列: 数据结构和算法 修改 解锁


“逻辑”概念

复习:

数组为例,在大多数语言中(C#/Java)中:

  1. 数组就是一排连续的盒子
  2. 每一个盒子都有一个地址,获取盒子里的数据(元素)需要知道它的地址
  3. 但数组这排盒子的地址是连续的,或者说,这一排盒子占用了一段连续的地址
  4. 所以我们只需要记录第一个盒子的地址(存储在数组变量名中)
  5. 当我们要取第n个盒子里的数据,只需要在第一个盒子的地址上加n,就能直接得到该盒子的地址

注意上面第4条,这是我们理解数组的关键,这也是数组被如此广泛使用的原因:我们是从数组中第1个元素开始,依次挨着数(找)第2个第3个……直到第n个,而是通过运算直接得到第n个数组元素的地址!所以,取数组中第2000个元素,并不会比取数组中第2个元素慢。

但在JavaScript中,数组的底层实现不是这样的,它实际上采用哈希表链表的方式,存储数组元素。@想一想@:为什么?

飞哥推测(为什么是推测?/捂脸.jpg:语言本身只定义语法,不管底层实现)是因为JavaScript弱/动态类型的原因。

但不管底层是如何实现,只要一个东东,能让我们从0开始按下标存取数据,它就是数组。(领会:逻辑概念)

数组一般又可分为:

  • 静态/定长数组:如C#/Java,一旦初始化就确定长度,一旦确定无法更改
  • 动态/变长数组:如JavaScript,长度可以随时变……
之后继续会学:还有一维/二维/交错……数组


冒泡排序

需求:将数组中的数字(比如:9 2 3 5 4 7 6 8 1 0),按从小到大的顺序排列

PS:憋说你一眼就看出来啦……

建议:在学习冒泡排序之前,先@想一想@自己的方案,比如,可不可以:

PS:读别人的代码,比自己写还难

  1. 准备一个同样大小的空数组(以下称为:结果数组)
  2. 原数组中找到一个最大值(max),放到结果数组第1位
  3. 原数组中删除这个最大值(不行,做不到),改成:在原数组中找到除了max以下最大(第2大)的,放到结果数组第2位
  4. 循环上述过程,在原数组中找到第3大的,放到结果数组第3位
  5. ……
然后,对比一下最经典的入门级算法:冒泡排序

PPT动画演示:


其核心就是:

  • 遍历数组
  • 相邻两个元素交换
  • 两个循环:一个从上往下,一个从下往上

光说不练假把式!上代码:

//从小到大
for(var i=0; i<arr.length-1; i++){
	if(arr[i] > arr[i+1]){
		for(var j=i+1; j>0; j--){    //j从大到小了
			if(arr[j] < arr[j-1]){
				//交换数组元素
				var temp = arr[j];
				arr[j] = arr[j-1];	
				arr[j-1] = temp;	
			}else{
				break;    //注意:提高性能!
			}
		}
	} //else nothing
}



二分查找

猜数字的游戏(1-1000),你会怎么猜?

  • 500:大了
  • 250:小了
  • 350:小了
  • 400:大了
  • 375:小了
  • 385:你特么真是个天才!

其实,你这种猜测方法,归纳出来就是二分查找法

  • 将数组中间位置的元素与查找值比较,如果两者相等,则查找成功;
  • 否则利用中间位置记录将数组分成前、后两个集合,
    • 如果中间位置元素大于查找值,则进一步在其左边/前面的元素中查找,
    • 否则在其右边/后面的元素中查找
  • 重复以上过程,直到找到满足条件的元素

以下代码演示:

  • 先准备一个数组:不要忘了前提:数组元素有有序排列的
    var arr = [3, 8, 7, 12, 23, 35, 46, 59, 70, 108];
  • 用一个变量target来表示要查找的值
    var target = 8;  
    //也可以给一个数组中不存在的值,比如72 
    //找不到  -1
  • 引入左右指针是关键:把被我们人脑“脑补”出来的东西(所谓的中间下标是怎么来的?)给代码补上
    var left = 0,
    	right =  arr.length,
    	i = Math.floor((left+right)/2);
  • 开始循环,通过left/right值的改变确定每一次循环是i的值(注意:代码有错误且不完全)
    while(target!=arr[i]){    //是这样的吗?
    
    	if(target > arr[i]){
    		//改left还是right?怎么改
    	}else if(target < arr[i]){
    		//是不是类似于:left = ?
    	}else{  //找到了
    		//找到	index
    		return i; //?
    	}
    	
    	//可以和循环前的i赋值合并么?
    	i = Math.floor((left + right)/2);
    }


快速排序

月薪18K的算法,^_^

先上PPT演示:


总结:

  • 通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都另外一部分的所有数据都要小
  • 然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行……
  • 直到:整个数据变成有序序列。

第一轮

为什么不能简单的按照上述描述进行coding?

受限于“数组”的特征:定长定位。没有int[-1]啊!数组的操作只有一个:交换(swap)

#悟#:运动是相对的。

所以,衍生出来如下方法:(PPT演示

其核心步骤包括:

  1. 选定一个基数 (通常就是数组第一个数)
  2. 设定一个左指针,一个右指针。程序运行之后,
    • 左指针从左往右移动
    • 右指针从右往左移动
    记忆:一个基数两个指针,^_^
  3. 从左往右找到比基数大的数A,从右往左找比基数小的数B:交换A和B
  4. 重复第2/3步,直到直到左右指针重合,指向最后一个终点值(飞哥自命名)这时候:
    • 左边都是比基数小的数
    • 右边都是比基数大的数
  5. 将基数和终点值比较,如果:
    • 终点值比基数小,直接交换;
    • 否则,将基数和终点值前一位数交换

演示代码:

var arr = [18, 7, 5, 9, 12, 23, 16, 32, 1, 3];
var i = 0,
	left = 1,
	right = arr.length-1;
while(left<right){    //循环条件
	while(arr[left]<arr[i]){
		if(left==right){
			break;
		}
		left++;	//一直加到 arr[left]<arr[i];
	}
	//停下来,准备交换
	
	while(arr[right]>arr[i]){
		if(left==right){
			break;
		}		
		right--;
	}
	
	if(left == right){    //如果左右指针已经重合
		if(arr[left]>arr[i]){
			swap(arr, left-1, i);
		}else{
			swap(arr, left, i);
		}
	}else{
		swap(arr, left, right);
		left++;
		right--;		
	}
}

递归调用

完成一轮排序之后,如何对其左右两部分再进行一次排序呢?而且还要将这个过程一直执行下去呢……

童鞋们,这就是典型的递归啊!

首先,将每一轮的排序抽象成方法:

function quickSort(arr, left, right){    //@想一想@:为什么要left和right参数?

小技巧:记录下每一轮排序前的oldLeft和oldRight:

int oldLeft = left, oldRight = right;

一轮排序完成之后,继续调用方法自己:

            //左边排序
            quickSort(array, oldLeft, middle - 1);

            //右边排序
            quickSort(array, middle + 1, oldRight);

特别注意,一定要想好递归结束的条件:

            ///1.递归终止条件
            if (left >= right)
            {
                return;
            }


复杂度

@想一想@:冒泡排序和快速排序哪一个更快?为什么呢?

我们使用复杂度来衡量一个(比较各个)算法的效率:



空间复杂度 S(n)

还记得飞哥自创的排序法不?用一个新数组按从小到大的顺序来装原数组……这种算法,就额外耗费了一个数组的存储空间;

而冒泡排序法,只耗费了多少额外空间?一个元素对应的临时变量而已。

这种算法所需的额外存储空间多少,就是空间复杂度。


时间复杂度 O(n)


按字面意思,是指完成某个算法需要消耗的时间。

但因为耗时受硬件影响,不够客观,我们我们通常以运算(循环)次数衡量。

PS:理解不同语义下的“复杂”:执行 v.s. 设计

同时,算法还受数据影响

  • 可能有最好的情况(比如第一次循环就找到),
  • 还有可能有最坏的情况(比如直到循环结束才找到),
  • 我们一般默认指的是通常状况,或者说算法的平均复杂度。

用大O表示,指示所需运算(循环)次数和参与运算元素之间的关系,一般包括三个量级

  • 线性:O(n),类似于 y=x
  • 指数:O(n^2),类似于 y=x^2
  • 对数:O(log(n)),类似于 y=log(x)

@想一想@:冒泡和快速排序,遍历和二分查找的复杂度。



闲话

为什么是:数据结构和算法,而不是算法和数据结构呢?揭示:

算法依赖于数据结构。

@想一想@能举一个例子么?


作业

  1. 抽象一个方法swap(),可以交换数组中的两个元素;以下作业,都要使用该方法。
  2. 改造冒泡排序:
    1. 让结果从大到小排序
    2. 将其封装成方法bubbleSort(),且该方法既能按元素本身大小比较,也能按元素的绝对值(即:数组中可能有负数)进行比较
    3. 可以指定数组中的某一个值为最大(就像斗地主有“癞子”一样)
  3. 完成二分查找法,将其封装成函数/方法:BinarySeek()
  4. 修复课堂中快排的bug,用更优雅的方式实现,提示:
    1. left-1有无可能为负数?
    2. 数组以18开头试试
    3. 能不能减少while嵌套(使用continue)
    4. 最后和基数的交换能不能放到while之外
    5. ……
    PS:一定要自己思考自己调试,这是学习数算的一个重要目的!
  5. 彻底完成快速排序!冲击月薪18K,^_^
数组 遍历 冒泡排序
觉得很 ,不要忘记分享哟!

任何问题,都可以直接加 QQ群:273534701

在当前系列 数据结构和算法 中继续学习:

我们的 特色

  • 面向就业
  • 线上线下结合
  • 同学互助
  • 师生共赢

报班 QQ群:273534701

  • 获取视频资料
  • 要求作业点评
  • 参加阶段性测试
  • 模拟面试