01.排序

01Class

1. 选择排序

假定一个最小的数，是起始位置的，如果发现后面的数中有比这个数小的数，就交换位置，这时还没有结束，第一层循环还是在第一个位置，直到找到最小的一个数，将其交换位置，放到最开始的位置，依次类推，第二小的就放在后面。

/**
@about:  选择排序
*/
public class Demo02 {

    public static void selectSort(int[] arr){
        // 考虑边界条件
        if(arr == null || arr.length < 2){
            return ;
        }
        int n = arr.length;
        for(int i = 0; i < n ; i++){
            int minValueIndex = i ;
            for(int j = i+1 ; j < n; j++){
                minValueIndex = arr[j] < arr[minValueIndex]?j:minValueIndex ;

            }
            swap(arr,i,minValueIndex);
        }
    }
    public static void printArray(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }
    public static void swap(int[] arr, int i ,int j ){
        int tmp = arr[j] ;
        arr[j] = arr[i] ;
        arr[i] = tmp ;
    }
    public static void main(String[] args){
        int[] arr = {5,1,2,6,4,8,6,4,7,15} ;
        printArray(arr);
        selectSort(arr);
        printArray(arr);
    }
}

2. 冒泡排序

不受数据左右

//每一趟只能确定将一个数归位，第一次将末位上的数归位，第二次倒数第二，直到结束，最大的数放到最后面。第一趟最后一个数有了就可以不用在排，所以外层循环用n-1。
public static void b ubbleSort(int[] arr){
    if (arr == null || arr.length < 2){
        return;
    }
    //0~ n-1
    //0~ n-2
    //0~ n-3
    //0~ end
    int n = arr.length;
    for(int end = n-1 ;end >= 0; end--){
        for(int second = 1; second <= end; second++ ){
            if(arr[second-1] > arr[second]){
                swap(arr,second,second-1) ;
            }
        }
    }

}
//冒泡排序的关键步骤，其他的和上面的排序是一样的。

3.插入排序

举例：

数组在0-0范围内，是有序的，

0-1范围内，如果 1位置上的数小于0位置上的数，将他们两个互换

0-2范围内，如果2位置上的数小于1位置上的数，互换，如果1位置上的数比0位置的数还小，继续互换。

0-3范围内，如果3位置上的数小于2位置上的数，这两个数互换位置，如果2位置上新换的数比1位置上的数小，继续换位置，知道不小于前一个数为止

0-4范围内，如果4位置上的数大于或者等于3位置上的数，结束，这一范围不用动，继续下一范围的数0-5

…….

0 - end（arr.length)

//其余部分都是一样的，插入排序的实现代码
//while 循环里面是终止条件，分别是打0位置或者后面的数大于前面的数了
public static void insertSort(int[] arr){
    int n = arr.length ;
    for(int end = 1; end < n; end++){
        int newNumIndex = end ;
        while(newNumIndex - 1 >= 0 && arr[newNumIndex-1] > arr[newNumIndex]){
            swap(arr,newNumIndex,newNumIndex-1);
            newNumIndex-- ;
        }
    }
}

// 也可以这样写 ， 用两个for循环
public static void insertSort2(int[] arr){
    int n = arr.length ;
    for(int end = 1; end < n ; end++){
        for(int pre= end ; pre-1 >=0 && arr[pre-1] > arr[pre] ; pre-- ){
            swap(arr,pre-1,pre);
        }
    }
}

总结

以上三种排序的时间复杂度是一样的 O（n**2）

常数复杂度： O（1），插入排序优于另外两种排序

4. 二分法

一般是在一个有序数组上，开展二分搜索

时间复杂度； O（log n）—》 log2 N

注意：有序不是二分的必要条件，只要能构建正确的左右两侧的淘汰逻辑，就可以二分。

4.1 二分法查找有序数组中是否存在某一数

public class Demo05 {
    public static boolean exist(int[] sortedArr, int num){
        if(sortedArr == null || sortedArr.length == 0){
            return false ;
        }
        int L = 0 ;
        int R = sortedArr.length-1 ;
        int mid = 0 ;
        while (L < R ) {  // 至少有两个数的时候
            mid = L + ((R-L) >> 1) ;
//等同于 （L+R）/2 ,因为这样写不安全，数特别大的时候会溢出
//为了防止溢出，改写为 （L+ （R-L）/2) ,根据位运算，除2，可以写为带符号右移1位。            
            if(sortedArr[mid] == num){
                return true ;
            }else if(sortedArr[mid] > num){
                R = mid - 1 ;
            }else {
                L = mid + 1 ;
            }
        }
        return sortedArr[L] == num ;
    }

    public static void main(String[] args){
        int[] arr = {1,2,3,4,4,5,7,7,8,15} ;
//        exist(arr,4) ;
        System.out.println(exist(arr,9));
    }
}

4.2 在数组中，找满足 >= 指定value值的最左位置

public static int nearestIndex(int[] arr, int value) {
    int L = 0;
    int R = arr.length - 1;
    int index = -1;  // 记录最左的对号
    int mid = 0;
    while (L <= R) {  // 小于等于，至少有一个数
        mid = L + ((R - L) >> 1);
        if (arr[mid] >= value) {
            index = mid;
            R = mid - 1;
        } else {
            L = mid + 1;
        }
    }
    return index ;
}

4.3 找到满足 <= 指定value值的最右位置

public static int nearestIndex(int[] arr, int value){
       int L = 0 ;
       int R = arr.length - 1 ;
       int mid = 0 ;
       int index = -1 ;
       while (L <= R){
           mid = L + ((R-L) >> 1) ;
           if(arr[mid] <= value){
               index = mid ;
               L = mid + 1 ;
           }else{
               R = mid - 1 ;
           }
       }
       return index ;
   }

4.4 局部最小值问题

特点：任意两个相邻位置的数一定不相等。

如果是边界的条件需要小于后一个，或者前一个。如果是中间的值必须比前一个，后一个小，才叫局部最小。

public static int getLessIndex(int[] arr){
        if(arr == null || arr.length == 0 ) {
            return -1;
        }
        if(arr[0] < arr[1]){
            return 0 ;
        }
        if(arr[arr.length-1] < arr[arr.length - 2]){
            return arr.length - 1 ;
        }
        int l = 0 ;
        int r = arr.length - 1 ;
        int mid = 0 ;
        while(l < r){  // 至少有两个数
            mid = l + ((r - l) >> 1) ;
            if(arr[mid] > arr[mid + 1]){
                l = mid + 1 ;
            }else if (arr[mid] > arr[mid - 1]){
                r = mid - 1;
            }else {
                return mid ;
            }
        }
        return l ;  // 返回 l 是因为最少需要有两个值，如果没有l<r的话就返回左边的边界。
    }