搜索
Java数据结构和算法第0讲综述参考教材：Java数据结构和算法（第二版），[美]Robertlafore1.数据结构的特性数据结构优点缺点数组插入快；如果知道下标，可以非常快地存取查找慢，删除慢，大小固定有序数组比无序的数组查找快删除和插入慢，大小固定栈提供后进先出方式的存取存取其他项很慢队列提供先进先出方式的存取存取其他项很慢链表插入快，删除快查找慢二叉树查找、插入、删除都快（如果树保持平衡）删除算法复杂红-黑树查找、插入、删除都快；树总是平衡的算法复杂2-3-4树查找、插入、删除都快；树总是平衡的；类似的树对磁盘存储有用算法复杂哈希表如果关键字已知，则存储极快；插入快删除慢，如果不知道关键字则存储很慢，对存储空间使用不充分堆插入、删除快；对大数据项的存取很快对其他数据项存取慢图对现实世界建模有些算法慢且复杂2.经典算法总结查找算法：线性查找和二分查找排序算法：用表展示第一讲数组1.Java中数组的基础知识1）创建数组在Java中把数组当作对象来对待，因此在创建数组时必须使用new操作符：int[]intArr=newint[10];一旦创建数组，数组大小便不可改变。2）访问数组数据项数组数据项通过方括号中的下标来访问，其中第一个数据项的下标是0：intArr[0]=123;3）数组的初始化当创建数组之后，除非将特定的值赋给数组的数据项，否则它们一直是特殊的null对象。int[]intArr={1,2,3,4,5};等效于下面使用new来创建数组并初始化：int[]intArr=newint[5];intArr[0]=1;intArr[1]=2;intArr[2]=3;intArr[3]=4;intArr[4]=5;2.面向对象编程方式1）使用自定义的类封装数组MyArray类：publicclassMyArray{privatelong[]arr;privateintsize;//记录数组的有效长度publicMyArray(){arr=newlong[10];}publicMyArray(intmaxSize){arr=newlong[maxSize];}//向数组中插入数据publicvoidinsert(longelement){arr[size]=element;size++;}//显示数组中的数据publicvoidshow(){for(inti=0;isize;i++){if(i==0){System.out.print([+arr[i]+,);}elseif(i==size-1){System.out.println(arr[i]+]);}else{System.out.print(arr[i]+,);}}}//根据值查找索引（出现该值的第一个位置）：线性查找publicintqueryByValue(longelement){inti;for(i=0;isize;i++){//linearsearchif(arr[i]==element)break;}if(i==size){return-1;}else{returni;}}//根据索引查找值publiclongqueryByIndex(intindex){if(index=size||index0){thrownewArrayIndexOutOfBoundsException();}else{returnarr[index];}}//删除数据publicvoiddelete(intindex){if(index=size||index0){thrownewArrayIndexOutOfBoundsException();}else{//当size=maxSize，删除最后一个数时，不会执行forfor(inti=index;isize-1;i++){arr[index]=arr[index+1];System.out.println(for);}size--;}}//更新数据publicvoidupdate(intindex,longvalue){if(index=size||index0){thrownewArrayIndexOutOfBoundsException();}else{arr[index]=value;}}}2）添加类方法实现数据操作测试MyArray类方法：publicvoidtestMyArray()throwsException{MyArraymyArray=newMyArray();myArray.insert(123);myArray.insert(456);myArray.insert(789);myArray.show();//[123,456,789]System.out.println(myArray.queryByValue(111));//-1System.out.println(myArray.queryByIndex(2));//789myArray.delete(2);myArray.show();//[123,456]myArray.update(0,0);myArray.show();//[0,456]}3.有序数组1）有序数组简介以及其优点有序数组是一种数组元素按一定的顺序排列的数组，从而方便使用二分查找来查找数组中特定的元素。有序数组提高了查询的效率，但并没有提高删除和插入元素的效率。2）构建有序数组将2.1中自定义的类封装数组MyArray的insert方法改为如下：//向有序数组中插入数据，按大小从前往后排列publicvoidinsert(longelement){inti;for(i=0;isize;i++){//findwhereitgoesif(elementarr[i])break;}for(intj=size;ji;j--){//movebiggeronesuparr[j]=arr[j-1];}arr[i]=element;size++;}得到有序数组的类封装MyOrderedArray类，测试该类中的insert方法：publicvoidtestMyOrderedArray()throwsException{MyOrderedArraymyOrderedArray=newMyOrderedArray();myOrderedArray.insert(999);myOrderedArray.insert(555);myOrderedArray.insert(777);myOrderedArray.show();//[555,777,999]}4.查找算法1）线性查找在查找过程中，将要查找的数一个一个地与数组中的数据项比较，直到找到要找的数。在2.1中自定义的类封装数组MyArray的queryByValue方法，使用的就是线性查找。2）二分查找二分查找（又称折半查找），即不断将有序数组进行对半分割，每次拿中间位置的数和要查找的数进行比较：如果要查找的数中间数，则表明要查的数在数组的前半段；如果要查的数中间数，则表明该数在数组的后半段；如果要查的数=中间数，则返回中间数。在有序数组的类封装类MyOrderedArray中添加binarySearch方法//根据值二分查找索引（前提：有序）publicintbinarySearch(longvalue){intmiddle=0;intleft=0;intright=size-1;while(true){middle=(left+right)/2;if(arr[middle]==value){returnmiddle;//foundit}elseif(leftright){return-1;//can'tfoundit}else{//dividerangeif(arr[middle]value){right=middle-1;//inlowerhalf}else{left=middle+1;//inupperhalf}}}}测试该二分查找方法：publicvoidtestMyOrderedArray()throwsException{MyOrderedArraymyOrderedArray=newMyOrderedArray();myOrderedArray.insert(999);myOrderedArray.insert(555);myOrderedArray.insert(777);myOrderedArray.insert(333);System.out.println(myOrderedArray.binarySearch(333));//0}第二讲简单排序本讲提到的排序算法都假定了数组作为数据存储结构，本讲所有算法的时间复杂度都是。在大多数情况下，假设当数据量比较小或基本上有序时，插入排序算法是三种简单排序算法中最好的选择，是应用最多的。对于更大数据量的排序来说，后面讲到的快速排序通常是最快的方法。1.冒泡排序1）基本思想在要排序的一组数中，对当前还未排好序的范围内的全部数，自下而上对相邻的两个数依次进行比较和调整，让较大的数往下沉，较小的往上冒。即：每当两相邻的数比较后发现它们的排序与排序要求相反时，就将它们互换。2）算法实现冒泡排序的Java代码：//bubblesortpublicstaticvoidbubbleSort(long[]arr){longtemp;for(inti=0;iarr.length-1;i++){//outerloop(forward)for(intj=arr.length-1;ji;j--){//innerloop(backward)if(arr[j]arr[j-1]){//swapthemtemp=arr[j];arr[j]=arr[j-1];arr[j-1]=temp;}}}}测试冒泡排序及输出结果：publicvoidtestBubbleSort()throwsException{long[]arr={79,91,13,52,34};Sort.bubbleSort(arr);System.out.println(Arrays.toString(arr));//[13,34,52,79,91]}2.选择排序1）基本思想在要排序的一组数中，选出最小的一个数与第一个位置的数交换；然后在剩下的数当中再找最小的与第二个位置的数交换，如此循环到倒数第二个数和最后一个数比较为止。与冒泡排序相比，选择排序将必要的交换次数从O(N*N)减少到O(N)，但比较次数仍然保持为O(N*N)。2）算法实现选择排序的Java代码：//selectsortpublicstaticvoidselectSort(long[]arr){longtemp;for(inti=0;iarr.length-1;i++){//outerloopintk=i;//locationofminimumfor(intj=i+1;jarr.length;j++){//innerloopif(arr[j]arr[k]){k=j;//anewminimumlocation}}temp=arr[i];arr[i]=arr[k];arr[k]=temp;}}测试选择排序及输出结果：publicvoidtestSelectSort()throwsException{long[]arr={79,91,13,52,34};Sort.selectSort(arr);System.out.println(Arrays.toString(arr));//[13,34,52,79,91]}3.插入排序1）基本思想在要排序的一组数中，假设前面(n-1)[n=2]个数已经是排好顺序的（局部有序），现在要把第n个数插到前面的有序数中，使得这n个数也是排好顺序的。如此反复循环，直到全部排好顺序。在插入排序中，一组数据仅仅是局部有序的；而冒泡排序和选择排序，一组数据项在某个时刻是完全有序的。2）算法实现插入排序的Jav