插入,冒泡,选择,快速排序,二分查找(Java版) 2

一. 直接插入排序
void insertSort(int[] a){
      for(int i=1;i<a.length; i++){
           if (a[i]<a[i-1]){
               temp = a[i];  //1
               a[i] = a[i-1]; //2

               // 继续和前面的进行比较
               for(int j=i-2; j>=0; j--){
                    if(temp < a[j])
                         a[j+1] =a[j];//3
               }
               a[j+1] = temp;//4
           }
      }
}

算法(简要描述):
1. temp保存被比较的数值
2. 前一位数值移动到被比较的数值的位置
3. 前面的继续往后移动
4. 把被比较的数值放到适当的位置
直接插入排序


二.冒泡排序
  冒泡排序，就是从最底那个开始往上比较，遇到比它小的就交换，相当于过五关看六将，不断地向前冲。接着循环第二个...
+-----+    void bubbleSort(int[] a){
| a[6] |            //每个都进行冒泡(一个一个来)
+-----+            for (int i=0; i<a.length; i++){
| a[5] |   
+-----+                    //和后面的每个都进行比较(过五关看六将)
| a[4] |                    for (int j=i; j<a.length-1; j++){
+-----+                            if (a[j]>a[j+1]){
| a[3] |                                    temp = a[j];
+-----+                                    a[j] = a[j+1];
| a[2] |                                    a[j+1] = temp;
+-----+                            }
| a[1] |                    }
+-----+            }
| a[0] |    }
+-----+

三.选择排序
  选择排序，就是选择最小的，然后置换，循环再找到最小的，再置换...
void selectSort(int[] a){
        for (int i=0; i<a.length; i++){
                small = i;

                //找出最小的
                 for (int j=i+1; j<a.lenth; j++){
                        if (a[small]>a[j]){
                                small = j;
                        }
                }

                //置换位置
                 if (i != small){
                        temp = a[small];
                        a[small] = a[i];
                        a]i] = temp;
                }
        }
}

四.快速排序
  快速排序的基本过程:
  得到枢轴索引：compare首先从high位置向前搜索找到第一个小于compare值的索引，并置换(这时high索引位置上的值为compare值)；然后从low位置往后搜索找到第一个大于compare值的索引，并与high索引上的值置换(这时low索引位置上的值为compare值)；重复这两步直到low=high为止。
  得到枢轴索引后，则递归进行枢轴两边的队列的排序....
void quickSort(int[] a, int low, int high) {
        p = get(a, low, high);
        quickSort(a, low, p-1);
        quickSort(a, p+1, high);
}

int get(int[] a, int low, int high){
     compare = a[low];

     while(low < high){ //无论如何置换, 被置换的都包含compare的值
         while(low<high && a[high]>=compare)   
              high--;

         //在 low<high 的情况下找到a[high]<compare并置换
         temp = a[low];
         a[low] = a[high];
         a[high] = temp;

         while(low<high && a[low]<=compare)
              low++;

         //在 low<high 的情况下找到a[low]>compare并置换
          temp = a[low];
          a[low] = a[high];
          a[high] = temp;
     }
     return low; //while(low==hight)停止循环, 并返回枢轴位置
}

五.二分查找
  二分查找原理很容易懂，想象为二叉查找树就明白了。
int binarySearch(int[] a, int value){
        int low = 0;
        int high = a.length-1;
       
        while(low <= high){
                mid = (low+high)/2; //**
                if (a[mid] == value)
                        return mid;
                else if (a[mid] > value)
                        high = mid-1;
                else
                        low = mid +1;
        }
        return -1;
}
    ** mid = (low + high) / 2; 有问题，当low + high大于int范围时就会溢出的。Sun的jdk里面的二分查找源码原先也有同样的问题。
    解决的方法是mid = low/2 + high/2。这样用2先除一下，就不会溢出了。

本文出自 “学习Android” 博客，请务必保留此出处http://android.blog.51cto.com/268543/130450