各种查找方法和排序方法的简单实现

查找

• 线性查找法（Linear Search）

从头至尾一个一个比较即可。复杂度计算：最差的情况，元素不在列表里，就要比较完n个元素。而期望的情况是不得不查找该列表的一般，就要查找n/2个元素。所以具有线性时间复杂度O(n)。

public static <T extends Comparable<? super T>> 
    boolean linearSearch(T[] data,int min,int max,T target){
        int index=min;
        boolean found=false;
        
        while(!found&&index<=max){
            if(data[index].compareTo(target)==0)
                found=true;
            index++;
        }
        return found;
    }

• 二分查找法(binary Search)

意思都懂，主要看程序如何实现。这里使用了递归算法。重复的调用自己。最差的情况，元素不在列表里。每次一半，就要比较log₂n次。因此，找到位于该查找池中某一元素的预期情形是大约(log₂n)/2次比较。时间复杂度为O(log₂n)。

public static <T extends Comparable<? super T>> 
    boolean binarySearch(T[] data,int min,int max,T target){
        boolean found=false;
        int midpoint=(min+max)/2; //这里的计算会自动忽略答案的小数部分
        if(data[midpoint].compareTo(target)==0)//和中间值相等即找到了
            found=true;
        else if(data[midpoint].compareTo(target)>0){ //如果中间元素大于目标元素，则在数组的左边
            if(min<=midpoint-1)  //判断最小值和中间值减一，相等的话，就是还有最小值没判断。
                found=binarySearch(data, min, midpoint-1, target);
        }
        else if(midpoint+1<=max){ //如果小于目标元素，在右边，判断两个之间是否还有没判断的元素
            found=binarySearch(data, midpoint+1, max, target);
        }
        return found;
    }

排序

• 选择排序法(selection sort)

基本思路，第一次扫描列表中的最小值与第一个位置的元素交换。第二次扫描除了第一个元素之外的元素，找出最小值与第二个位置的元素交换位置。
即选择排序算法通过反复的将某一特定的值放到它在列表中的最终已排序的位置从而完成对某一列表值的排序。

public static <T extends Comparable<? super T>> 
    void selectionSort(T[] data){
        int min;
        T temp;
        //这个index表示列表中要去被替代的位置，从0开始，往后走
        for(int index=0;index<data.length-1;index++){
            min=index;
            //这里的循环从index+1开始查找元素，有比index小的就和他交换。
            //最终能把后面最小的元素放在该放的位置。接着去到外层循环接着下一个index
            for(int scan=index+1;scan<data.length;scan++)
                if(data[scan].compareTo(data[min])<0)
                    min=scan;
            temp=data[min];
            data[min]=data[index];
            data[index]=temp;
        }
    }

• 插入排序法(insert sort)

通过反复的将某一特定值插入到该列表已经排好序的某个子集里面来完成对列表值的排序。每次一个，每一个未排序元素都被插入到这个已排序的子集中的恰当位置处，直至整个列表排好序。下面的程序中，前面的部分即为已经排好序的子集。依次把后面的元素插入到合适的位置即可。

public static <T extends Comparable<? super T>> 
    void insertSort(T[] data){
        //从第一个元素开始查看是否需要插的
        for(int index=1;index<data.length;index++){
            T key = data[index]; //保存这个可能要插入到前面的元素
            int position = index; 
            while(position>0&&data[position-1].compareTo(key)>0){ 
                //因为前面的是已经排序好的。
                //检查之前的元素是不是大于这个元素，如果大于就要往前插。直到比到第一个元素
                data[position] = data[position-1];
                //将之前比较他大的元素给往后移一位，直到他该在的位置空了出来
                position--;
            }
            data[position]=key;//这个position已经是上面减过得了，直接插进去。
        }
    }

• 冒泡排序法(bubble sort)

public static <T extends Comparable<? super T>> 
    void bubbleSort(T[] data){
        int position,scan;
        for(position=data.length-1;position>=0;position++) 
            //大循环次数，每个元素都要靠冒泡排在合适的位置。所以要length-1次
            for(scan=0;scan<-position-1;scan++) 
                //小循环，每次都会有一个正确的元素摆在最后排好位置，所以每次减1
                if(data[scan].compareTo(data[scan+1])>0)
                    swap( data, scan, scan+1); //依次交换，往后冒泡
    }