黑马程序员技术交流社区

标题: 基础班学习的技术总结帖 [打印本页]

---

作者: HelloJav4    时间: 2017-12-28 18:58
标题: 基础班学习的技术总结帖
作为还在上JavaEE基础班的萌新，说实在也没什么技术贴能写，毕竟现在学的还不多。所以我就搜索了现在学到的知识点：一些基础语句：选择结构，循环结构之类的；面对方法中的封装；数组中的一维数组，二维数组，Arraylist；简单的IO流。差不多这样吧，之前是想写一个for循环流程的知识点，不过看了论坛上的技术贴就觉得有些简单了。不过在写快速排序之前来看看这个题，热一下身倒也可以。
下面先上题：
public class Test_01 {
    public static void main(String[] args) {
        int i = 0;
        for (method('B'); method('C') && i < 2; method('D')) {
            method('A');
            i++;
        }
    }
    public static boolean method(char c) {
        System.out.println(c);
        return true;
    }
}
问输出什么？ 这个题目呢，肯定是很基础的，除了咋一看上去有些唬人之外，内容也就是之前我们上课的时候讲过的for循环的流程。不过就是这个题，也是就业时的面试题。当然做这样的基础题只要静下心来，按部就班的走一遍流程就完成了，所以这里写一下答案过程就不提了，不会的话可以看一下for循环的流程。
答案：BCADCADC。

好了现在呢，就讲数组排序的问题了。我们这个JavaEE基础班学到的内容也足够做数组排序的问题了，特别是经典的冒泡排序和选择排序。只要告诉你它的运行方式，你大概就能写出来了。但是这两个排序方式太简单了，而且效率很低。本来我也不清楚这个效率低不低的，然后我学到了获取当前时间的方法，于是测试了三者对数组处理的速度。
我在写完快速排序之后，测试了这三种排序方式：对100000个不重复元素的数组进行排序
冒泡排序用时 15000ms左右
选择排序用时 4400ms左右
快速排序用时 10ms左右
可以看出快速排序比前两种好的太多了，特别是在处理大容量的数组的时候。然后我通过观察这三者的代码，发现冒泡排序和选择排序重复次数很高，大概需要遍历数组n/2次，n是数组长度，因为每遍历一次只能减少下次遍历一个数组元素的运算量。
冒泡排序的循环内容：
for(inti=0;i<arr.length-1;i++){//外层循环控制排序趟数
　　　　　　for(int j=0;j<arr.length-1-i;j++){//内层循环控制每一趟排序多少次
　　　　　　　　if(arr[j]>arr[j+1]){
　　　　　　　　　　int temp=arr[j];
　　　　　　　　　　arr[j]=arr[j+1];
　　　　　　　　　　arr[j+1]=temp;
　　　　　　　　}
　　　　　　}
　　　　}
可以看出遍历全部数组成员很大程度的浪费了计算力，那么就需要减少遍历的次数以及每次遍历的元素个数。快速排序就做到了这些。
关于快速排序呢，也是听学长说起过的，然后我大概了解了快排的思想方式和其中用到的递归的方式，之后写了大半天才勉强写完，然后在网上找了攻略进行了修改，当然也打了一遍更为优化的快排代码，我个人呢还是比较理解学长给我看的视频讲解，但不得不说写出来的并且优化完也没有网上的简洁，甚至网上的效率更高一些。
本来想测试一下我写的和网上的效率高低，但测试出了些问题，我先随机了一个大容量的数组，然后再赋值给另一个相同容量的数组，那么我现在有两个相同的数组，然后我用两种代码对其排序，但直接发生了内存溢出的错误，几番摆弄之后不及而终。

接下来呢，咳咳，说实在不管是快速排序的思想方式还是其中用到递归这个方式都不是我现在所学到的，所以讲解部分呢，我就搬网上所讲的内容了。

快速排序
算法思想：基于分治的思想，是冒泡排序的改进型。首先在数组中选择一个基准点（该基准点的选取可能影响快速排序的效率，后面讲解选取的方法），然后分别从数组的两端扫描数组，设两个指示标志（lo指向起始位置，hi指向末尾)，首先从后半部分开始，如果发现有元素比该基准点的值小，就交换lo和hi位置的值，然后从前半部分开始扫秒，发现有元素大于基准点的值，就交换lo和hi位置的值，如此往复循环，直到lo>=hi,然后把基准点的值放到hi这个位置。一次排序就完成了。以后采用递归的方式分别对前半部分和后半部分排序，当前半部分和后半部分均有序时该数组就自然有序了。
排序过程：

算法实现：
public static int partition(int []array,int lo,int hi){
        //固定的切分方式
        int key=array[lo];
        while(lo<hi){
            while(array[hi]>=key&&hi>lo){//从后半部分向前扫描
                hi--;
            }
            array[lo]=array[hi];
            while(array[lo]<=key&&hi>lo){从前半部分向后扫描
                lo++;
            }
            array[hi]=array[lo];
        }
        array[hi]=key;
        return hi;
    }

    public static void sort(int[] array,int lo ,int hi){
        if(lo>=hi){
            return ;
        }
        int index=partition(array,lo,hi);
        sort(array,lo,index-1);
        sort(array,index+1,hi);
    }
那么大家可以实验一下上面讲解和代码。大概的思想呢差不多就这样，我们黑马应该也有快速排序的视频大家可以找一下。

在写这个技术贴之前呢，我大概看了一下快速排序的算法思想——分治算法。嗯，好的，看不懂~这个可以在之后的学习中慢慢的去了解，不过呢可以看出来，好的算法可以让程序变的更加简洁、高效！所以在学习的过程中，我们应该尝试各种方式的去实现目标，不断的优化自己的代码，在学习的过程中养成这样的习惯，然后也需要我们了解更多的知识内容，才能想出更好的方案来。
好了好了，也写不出什么花样来，希望对比较基础的同学有那么一点点启发吧。

---

作者: 小浙姐姐    时间: 2017-12-31 10:23
在学习中有什么想法可以及时的问助教或者导师哈！你贴的快排比黑马教的复杂多了 = =，话说除了面试，实际上排序都直接调的封装好的方法。想了解什么都记得及时去问，来到黑马就不要客气。大家一起学习一起进步呢！就业班加油哦！

---

欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2