Java选择排序、冒泡排序、直接插入排序与二分查找

介绍一下四种Java的经典算法，这四种算法是非常基础的算法，学算法对我们深入理解程序有很大帮助。

• 选择排序
• 冒泡排序
• 插入排序
• 二分查找

选择排序

初始时第一个元素依次和后面的元素比较，在序列中找到最小元素并记录其下标，第一轮比较完毕后把最小元素交换到序列的起始位置作为已排序序列，然后再从剩下的未排序元素中找到最小元素，放到已排序序列末尾，直到所有元素排列完毕。

选择排序.gif

示例代码：

    public void selectSort(int[] array) {
        for (int i = 0; i < array.length - 1; i++) {//第i个元素
            int num = array[i];
            int index = i;
            for (int j = i + 1; j < array.length; j++) {//第i+1个元素
                if (array[j] < num) {//比较
                    num = array[j];
                    index = j;   //选出最小的值记录下标
                }
            }
            array[index]=array[i];//交换位置
            array[i]=num;
        }
    }

冒泡排序

重复的访问要排序的元素，依次比较相邻的两个元素，如果需要交换就交换他们的位置，直到没有元素再需要交换，每一轮交换之后都会有一个最值冒泡出来，所以此方法形象的称为冒泡排序。

冒泡排序.gif

示例代码：

    public void bubbleSort(int[] array){
        int temp;
        for(int i = 0; i < array.length - 1; i++){//外层循环控制轮数
            for(int j = 0; j < array.length - 1 - i; j++){//内层循环控制次数
                if(array[j] > array[j + 1]){   //比较相邻元素，如果需要就两两交换
                        temp = array[j];
                    array[j] = array[j + 1];
                array[j + 1] = temp;
                }
            }
        }
    }

直接插入排序

从第二个元素开始，把待排序的元素和此元素之前的元素从后向前依次比较，将大于此元素的逐个后移一位，找到合适位置并插入进去，直到所有的元素插入完毕为止，得到一个新的有序序列。

直接插入排序.gif

示例代码：

    public void insertSort(int[] array){
        int insertNum;  //要插入的数
        for(int i = 1; i < array.length; i++){  //从数组第2个元素开始遍历
            insertNum = array[i];  
            int j = i - 1;  //已经排序好的序列元素个数
            while(j >= 0 && array[j] > insertNum){  //序列从后到前循环，将大于insertNum的数向后移动一格
                array[j + 1] = array[j];  //array[j]的值后移
                j--;                      //j前移
            }
            array[j + 1] = insertNum;  //将需要插入的数放在要插入的位置。
        }
    }

二分查找

二分查找又称折半查找，查找一个有序数组中的元素。首先，假设数组元素是按升序排列，将数组中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将数组分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。

折半查找.jpg

示例代码：

    int binarySearches(int[] array, int key) {
        int startIndex = 0;    //开始查找的下标位置0
        int endIndex = array.length - 1;  //结束查找的下标位置为数组的最后一个元素

        while (startIndex <= endIndex) {
            int midIndex = (startIndex + endIndex) / 2;
            if (array[midIndex] < key){
                startIndex = midIndex + 1;
            }else if (array[midIndex] > key){
                endIndex = midIndex - 1;
            }else{
                return midIndex; // 找到了，返回元素下标
            }
        }
        return -(startIndex + 1);  // 没有找到，返回开始下标加1的负值
    }