算法基础（一）

          做为数学专业的我，其实一直特别喜欢数学，只不过大学的数学课程让我有点失望，所以选择了专心学习另一个行业计算机，但是随着学习的不断深入，感觉到了数学魅力，数学可以运用到几乎所有的行业，它无处不在，在计算机中一个看似复杂的问题，其实在数学中也平凡不过。去年参加软考中设计了算法，因为当时时间比较紧，而且为了应付考试，所以算法学习的不够深入，仅仅是理论上的理解，还没有真正的运用到代码上边，更或者，还不知道如何在软件运用中让它发挥它的威力。但是基础总是要打的，从今天开始，利用业余时间学习学习算法，希望自己能坚持下去！

    这里先看看我的以前的一篇关于数据结构的总括博客：软考（1）——看图心想数据结构

          当然了，最开始这篇关于算法的博客，还是从最基础，最常用的几种算法入手，虽然比较简单，但是确实我们必须需要掌握的。简单看一下冒泡排序，简单选择排序，二分查找三种基础算法。

 

          一，冒泡排序，看到这种算法，我就想起一句话“小数上浮，大数下沉”，通过层层的比较使小数浮出水面，而使大数“石沉水底”。从而达到排序的效果。具体原理不再阐述，看代码看注释：

[java] view plain copy

print?

1. /** 
2.  * 冒泡排序的java小例子 
3.  * @author Administrator 
4.  */  
5. public class BubberSort {  
6.     public static void main(String[] args) {  
7.         // 给定要排序的数组  
8.         int[] a = { 3, 1, 6, 5, 2,9,7 };  
9.   
10.         // 开始排序，冒泡排序遵循小数上浮，大数下沉的思想  
11.         // 循环变量取出数组最后一个数a[i]，依次进行循环  
12.         for (int i = a.length - 1; i > 0; i--) {  
13.             // 取出a[i]前边的数，和a[i]进行比较  
14.             for (int j = 0; j < i; j++) {  
15.                 // 如果a[j]大于a[j+1],则进行交换数据，小数向上浮动，达到冒泡的效果  
16.                 if (a[j] > a[j + 1]) {  
17.                     // 借助第三者达到位置的变化  
18.                     int temp;  
19.                     temp = a[j + 1];  
20.                     a[j + 1] = a[j];  
21.                     a[j] = temp;  
22.                 }  
23.             }  
24.         }  
25.         //打印排序后的数组  
26.         for (int i = 0; i < a.length; i++) {  
27.             System.out.println(a[i]);  
28.         }  
29.     }  
30. }  

        分析总结:由于嵌套了两层循环，所以数据量无限大时，可以看做时间复杂度按为O(N^2).

 

          二，简单选择排序，这个就是咱们人最初的思维了，在一堆数中我们通过一次筛选选中最小的，然后从剩下的数中再此筛选，选出最小的……这样我们就排好了！好，来看一下简单选择排序的小例子：

[java] view plain copy

print?

1. /** 
2.  * 简单选择排序 
3.  * @author Administrator 
4.  */  
5. public class selectSort {  
6.     public static void main(String[] args) {  
7.         int[] a = { 4, 3, 6, 1, 5, 7, 9, 2 };  
8.         // 开始排序，拿出第一个数据做为目前已知最小的，和其他每个数据依次进行比较，  
9.         // 碰到比自己小的，相互交换位置，直到找到最小的数据，也就成为了第一个元素  
10.         for (int i = 0; i < a.length - 1; i++) {  
11.             int min = i;  
12.             // 进行比较，循环找最小的数据  
13.             for (int j = i + 1; j < a.length; j++) {  
14.                 //如果比较的比我们最初设定的最小数小，则进行最小数min的重新制定  
15.                 if (a[min] > a[j]) {  
16.                     min = j;  
17.                 }  
18.             }  
19.             // 如果比较的元素比min小，则进行互换位置  
20.             if (min != i) {  
21.                 int temp;  
22.                 temp = a[i];  
23.                 a[i] = a[min];  
24.                 a[min] = temp;  
25.             }  
26.         }  
27.         //测试打印输出  
28.         for (int i = 0; i < a.length; i++) {  
29.             System.out.println(a[i]);  
30.   
31.         }  
32.     }  
33.   
34. }  

          分析总结：这个也是循环嵌套了两层，所以说时间复杂度也是O(N^2),但是和冒泡排序比起来，它还是有优势的，因为它交换的次数少，找出一个最小的数据只需要一次交换，二冒泡排序可就多了，只不过他俩的比较次数是等级别的，因为交换也需要时间的消耗，所以简单选择排序还是有一定优势的，尤其是数据量相对来说少的时候。

 

          三，二分法查找：上边两个是排序中的基础算法，排好顺序了，也需要我们查找我们想要的数据了，而二分法查找就是其中常用的，节时的，基础的一种算法。二分查找就是从排序好数据的中间位置进行查找比较，类似于木棒的中间对砍，所以又叫折半查找，来看如何从上边排好的数组中进行查找：

[java] view plain copy

print?

1. /** 
2.  * 二分法查找有序数列 
3.  * @author Administrator 
4.  */  
5. public class binary {  
6.     //测试调用  
7.     public static void main(String[] args) {  
8.         int[] a={1,3,4,6,7,8,12};  
9.         boolean isOk=binarySort(a, 12);  
10.         System.out.println(isOk);  
11.     }  
12.   
13.     /** 
14.      * 二分法查找的核心 
15.      * @param a  存储数据的数组 
16.      * @param destElement 想要查找的数据 
17.      * @return boolean,是否找到了 
18.      */  
19.     public static boolean binarySort(int[] a, int destElement){  
20.         //第一个数据，和最后一个数据  
21.         int begin =0;  
22.         int end=a.length-1;  
23.           
24.         //只要小数不超过大数就一直循环  
25.         while(begin<=end){  
26.             //这是折半的，从中间查找  
27.             int mid=(begin+end)/2;  
28.             //如果是要查找的数据，则返回  
29.             if(a[mid]==destElement){  
30.                 return true;  
31.                 //如果要查找的数据，比中间的数据小，则从前一半中查找  
32.             }else if(a[mid]>destElement){  
33.                 end=mid-1;  
34.                 //如果要查找的数据，比中间的数据大，则从后一半中查找  
35.             }else if( a[mid]<destElement){  
36.                 begin=mid+1;  
37.             }  
38.         }  
39.         return false;  
40.     }  
41. }  

         分析总结：查找算法中，二分法是速度最快的，但是必须是有序的序列。分块查找，顺序查找的效率其次的。

 

 

        总之，这些都是算法的基础中的基础，还需要我们下大功夫来试验，来总结，来吸收，算法学习的坚持中……