算法笔记-第01节课

亦凉 2022-09-11 05:28 256阅读 0赞

## 第01节课 ##

### 1. 选择排序 ###

思路：i~N-1找最小的放到第i号位置(i从0到N-1)

代码：

void selectSort(int[] arr) { 
    if (arr == null || arr.length < 2) return;
      for (int i = 0; i < arr.length; i++) { 
        int minIndex = i;
        for (int j = i; j < arr.length; j++) { 
          if (arr[j] < arr[minIndex]) minIndex = j;
        }
        swap(arr, i, minIndex);
      }
    }
    
    void swap(int[] arr, int i, int j) { 
      if (i == j) return;
      arr[i] = arr[i] ^ arr[j];
      arr[j] = arr[i] ^ arr[j];
      arr[i] = arr[i] ^ arr[j];
    }

### 2. 冒泡排序 ###

思路：在 0~N-1-i范围上，从左到右依次比较两个数大小，大的往后排

void bubbleSort(int[] arr) { 
    if (arr == null || arr.length < 2) return;
      for (int i = arr.length; i > 0; i--) { 
        for (int j = 0; j < i - 1; j++) { 
          if (arr[j] > arr[j + 1]) swap(arr, j, j + 1);
        }
      }
    }
    
    void swap(int[] arr, int i, int j) { 
      if (i == j) return;
      arr[i] = arr[i] ^ arr[j];
      arr[j] = arr[i] ^ arr[j];
      arr[i] = arr[i] ^ arr[j];
    }

### 3. 插入排序 ###

思路：每一次保证0~i上面有序(i从0到N-1)

void inserSort(int[] arr) { 
      if (arr == null || arr.length < 2) return;
      for(int i = 1; i< arr.length; i ++) { 
        for(int j = i; j > 0; j--) { 
          if(arr[j] < arr[j-1]) { 
            swap(arr, j, j - 1);
          }
        }
      }
    }
    
    void swap(int[] arr, int i, int j) { 
      if (i == j) return;
      arr[i] = arr[i] ^ arr[j];
      arr[j] = arr[i] ^ arr[j];
      arr[i] = arr[i] ^ arr[j];
    }

### 4. 二分法查找 ###

思路：

找到数组中间位置，中间位置和目标数对比，如果大于目标数，left = 中间数+1，如果小于目标数,则right = 中间数-1，如果相等，则找到返回true。

代码展示：

static boolean bsExist(int[] arr, int num) { 
      if(arr == null || arr.length == 0) { 
        return false;
      }
    
      int left = 0;
      int right = arr.length -1;
      while(left < right) { 
        int mid = left + ((right-left) >> 1);
        if(arr[mid] < num) { 
          left = mid+1;
        } else if( arr[mid] > num) { 
          right = mid -1;
        } else { 
          return true;
        }
      }
      // 表示left==right了
      return arr[left] == num;
    }
    
    static boolean exist(int[] arr, int target) { 
      if (arr == null || arr.length == 0) { 
        return false;
      }
      int L = 0;
      int R = arr.length - 1;
      int M;
      while (L < R) { 
        M = L + ((R - L) >> 1);
        if (target < arr[M]) { 
          R = M - 1;
        } else if (target > arr[M]) { 
          L = M + 1;
        } else { 
          return true;
        }
      }
      return arr[L] == target;
    }

### 5. 二分法查找大于给定值最小值位置 ###

思路：

采用二分法查找

代码展示：

static int nearLeft(int[] arr, int target) { 
      if (arr == null || arr.length == 0 || arr[arr.length - 1] < target) { 
        return -1;
      }
      int L = 0;
      int R = arr.length - 1;
      int M;
      int retIndex = -1;
      while (L <= R) { 
        M = L + ((R - L) >> 1);
        if (arr[M] > target) { 
          retIndex = M;
          R = M - 1;
        } else if (arr[M] < target) { 
          L = M + 1;
        } else { 
          return M;
        }
      }
      return retIndex;
    }

### 6. 二分法查找小于给定值最大值位置 ###

思路：

采用二分法查找

代码展示：

static int nearRight(int[] arr, int target) { 
      if (arr == null || arr.length == 0 || arr[0] > target) { 
        return -1;
      }
    
      int L = 0;
      int R = arr.length - 1;
      int M;
      int retIndex = -1;
      while (L <= R) { 
        M = L + ((R - L) >> 1);
        if (arr[M] < target) { 
          retIndex = M;
          L = M + 1;
        } else if (arr[M] > target) { 
          R = M - 1;
        } else { 
          return M;
        }
      }
      return retIndex;
    }

### 7. 局部最小（大）值 ###

思路：

采用二分法，思想类似凸函数理论，总有极小值存在

代码展示：

public static int getLessIndex(int[] arr) { 
      if(arr == null) { 
        return -1;
      }
      if(arr.length == 1) { 
        return 0;
      }
      if(arr[0] < arr[1]) { 
        return 0;
      }
      if(arr[length -1] < arr[length-2]) { 
        return arr.length - 1;
      }
    
      int L = 0;
      int R = arr.length -1;
      int M;
      int minIndex = -1;
      while(L <= R) { 
        M = L + ((R - L) >> 1);
        if(arr[M-1] < arr[M]) { 
          R = M - 1;
        } else if(arr[M] > arr[M + 1]) { 
          L = M + 1;
        } else { 
          minIndex = M;
          break;
        }
      }
      return minIndex;
    }