二分查找算法 排序算法(冒泡排序,选择排序,插入排序)_二分法排序

二分查找算法

什么是二分查找算法

二分查找也称折半查找（Binary Search），它是一种效率较高的查找方法。但是，折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列。(从数组中进行查找切数组内容必须牌序了)
   
    
顺序存储结构是存储结构类型中的一种，该结构是把逻辑上相邻的结点存储在物理位置上相邻的存储单元中，结点之间的逻辑关系由存储单元的邻接关系来体现。
    
 线性表是最基本、最简单、也是最常用的一种数据结构。线性表（linear list）是数据结构的一种，一个线性表是n个具有相同特性的数据元素的有限序列。
线性表中数据元素之间的关系是一对一的关系，即除了第一个和最后一个数据元素之外，其它数据元素都是首尾相接的（注意，这句话只适用大部分线性表，而不是全部。比如，循环链表逻辑层次上也是一种线性表（存储层次上属于链式存储，但是把最后一个数据元素的尾指针指向了首位结点）。

二分查找算法的前提:

1. 顺序存储结构的线性表 -- 数组

2. 容器中的元素必须实现了排序

二分查找算法的实现过程:

获取数组最中间位置的元素,和目标元素进行比较
    - 相等,表示查找成功,返回该元素下标
   	- 大于,到中间元素右侧的区间上继续查找最中间元素比较
    - 小于,到中间元素左侧的区间上继续查找最中间元素比较
最后,若找到目标元素,返回下标;若找不到目标元素,返回-1

排序算法

冒泡排序(BubbleSort)

排序规则:

        相邻元素两两比较,大的往后排,一轮比较结束,最大值出现在了最大下标处.

图片示例:

 代码示例:

  //冒泡排序  升序
        for (int i=0;i<ary.length-1;i++){
            for (int j=0;j<ary.length-1-i;j++){
                if (ary[j]>ary[j+1]){
                    int tmp = ary[j];
                    ary[j] = ary[j+1];
                    ary[j+1] = tmp;
                }
            }
        }
//冒泡排序  降序
        for (int i=0;i<ary.length-1;i++){
            for (int j=0;j<ary.length-1-i;j++){
                if (ary[j]<ary[j+1]){
                    int tmp = ary[j];
                    ary[j] = ary[j+1];
                    ary[j+1] = tmp;
                }
            }
        }
 

选择排序(Selection Sort)

排序规则:

        从未排序部分选择最小值/最大值,放到序列的第一个位置,之后再次从未排序部分选择最小值/最大值,填充到排好序部分的末尾,直到序列排序完成.

图片示例:

代码示例:

//        选择排序
//        i表示对该位置求最小值
        int[] ary = {1,3,65,7,12,89,0,65};
        //i表示对i位置求最小值
        for (int i=0;i<ary.length-1;i++){
            int min=i;  //min表示最小值的下标
            for (int j=i+1;j<ary.length;j++){
                if (ary[j]<ary[min]){
                    min = j;
                }
            }
            //将min位置的值与i位置的值进行互换
            int tmp = ary[i];
            ary[i] =ary[min];
            ary[min] = tmp;
        }

注意点:选择排序是不稳定的排序算法

选择排序是给每个位置选择当前元素最小的，比如给第一个位置选择最小的，在剩余元素里面给第二个元素选择第二小的，依次类推，直到第n-1个元素，第n个元素不用选择了，因为只剩下它一个最大的元素了。那么，在一趟选择，如果一个元素比当前元素小，而该小的元素又出现在一个和当前元素相等的元素后面，那么交换后稳定性就被破坏了。举个例子，序列5 8 5 2 9，我们知道第一遍选择第1个元素5会和2交换，那么原序列中两个5的相对前后顺序就被破坏了，所以选择排序是一个不稳定的排序算法。

插入排序

排序规则:

      将数列分为排好序和未排序部分,对未排序部分进行遍历,将遍历到的元素插入到之前排好序部分正确的位置.
    
百度百科描述:
插入排序，一般也被称为直接插入排序。对于少量元素的排序，它是一个有效的算法  。插入排序是一种最简单的排序方法，它的基本思想是将一个记录插入到已经排好序的有序表中，从而一个新的、记录数增1的有序表。  

 三种排序算法的性能高低

通过多次测试得出平均值
1. 数组的长度为10000
    冒泡排序:122ms
    选择排序:46ms
    插入排序:23ms      
2. 数组的长度为100000
     冒泡排序:15387ms
     选择排序:4328ms
     插入排序:1527ms
3. 数组的长度为200000
     冒泡排序:61826ms
     选择排序:16621ms
     插入排序:5899ms