数据结构与算法

数据结构与算法入门

• 大o记法：大 O 记法用来表示时间复杂度，只保留最大趋势公式，指数 > 线性 > 对数 > 常数。

• 时间复杂度是以步作为基础单位，空间复杂度是以一个基础数据类型值当做基础单位。

• 二分法查找（有序顺序数组）

  public static int find(int[] array, int aim) {
      // 初始化left = 最左侧, right = 最右侧
      int left = 0;
      int right = array.length - 1;
      int index=-1;
  
      // 当left > right则表示遍历完成
      while (left <= right) {
          // 获取中间的值
          int middle = (left + right) / 2;
          int middleValue = array[middle];
          if (middleValue == aim) {
              // 已经找到目标
             index=middle;
             break;
          } else if (middleValue < aim) {
              // 目标在middle的右侧，重置left
              left = middle + 1;
          } else {
              // 目标在middle的左侧，重置right
              right = middle - 1;
          }
      }
      return index;
  }
  

• 标记法解决二次问题

  public static ArrayList<Integer> repeat(int[] array) {
      ArrayList<Integer> result = new ArrayList<>();
      int[] exists = new int[11];
      for (int i = 0; i < array.length; i++) {
          int value = array[i];
          // 只有当前位置已经为1，标示重复，并且输出，>1情况则不输出了
          if (exists[value] == 1) {
              result.add(value);
          }
          // 用exists标示记录
          exists[value]++;
      }
      return result;
  }
  

• 冒泡排序（顺序）

  // 冒泡排序
  public static void bubbleSort(int[] array) {
      // 1. 每次循环，都能冒泡出剩余元素中最大的元素，因此需要循环 array.length 次
      for (int i = 0; i < array.length; i++) {
          // 2. 每次遍历，只需要遍历 0 到 array.length - i - 1中元素，因此之后的元素都已经是最大的了
          for (int j = 0; j < array.length - i - 1; j++) {
              //3. 交换元素
              if (array[j] > array[j + 1]) {
                  int temp = array[j + 1];
                  array[j + 1] = array[j];
                  array[j] = temp;
              }
          }
      }
  }
  

• 冒泡排序（逆序）

  // 冒泡排序
    public static void bubbleSort(int[] array) {
      // 每次循环，都能冒泡出剩余元素中最大的元素，因此需要循环 array.length 次
      for (int i = 0; i < array.length; i++) {
        // 每次遍历，只需要遍历 i 到 array.length - 2中元素。
        for (int j = array.length -2; j >=i; j--) {
          // 交换元素
          if (array[j] < array[j + 1]) {
            int temp = array[j + 1];
            array[j + 1] = array[j];
            array[j] = temp;
          }
        }
      }
    }
  

• 选择排序（顺序）

  // 选择排序
    public static void selectSort(int[] array) {
  
      for (int i = array.length-1;i>0 ;  i--) {
        int maxIndex=0;
        int max=array[0];
        for (int j = 0; j <= i; j++) {
          if (max<array[j]){
            max=array[j];
            maxIndex=j;
          }
          }
        //3. 交换元素
        int tem=array[i];
        array[i]=array[maxIndex];
        array[maxIndex]=tem;
        }
      }
  

• 时间复杂度与冒泡排序一样都是O（N^2）但选择比冒泡快一倍

• 冒泡排序相比较而言肯定是较差的。 选择排序和插入排序得分情
  况而定，如果原始数组本身有很多元素按希望的顺序排好序，则选
  择插入排序(如上面最好极限情况，接近 O(N))，否则选择选择排
  序。

• 插入排序

  public static void insertSort(int[] array) {
      for(int i= array.length-2;i>=0;i--){
        int temp=array[i];
        for (int j=i+1;j< array.length;j++)
        {
          if(temp>array[j])
          {
            array[j-1]=array[j];
            if(j== array.length-1)
            {
              array[j]=temp;
            }
          }
          if(temp<array[j])
          {
            array[j-1]=temp;
            break;
          }
        }
      }
    }
  

• 二分插入排序

  // 查找应该插入的索引位置
  public static int searchIndex(int[] array, int left, int right, int aim) {
      // 循环查找节点位置
      while (left < right) {
          int middle = (left + right) / 2;
          int value = array[middle];
          if (value < aim) {
              left = middle + 1;
          } else {
              right = middle - 1;
          }
      }
      // #1. 如果最终元素仍然大于目标元素，则将索引位置往左边移动一个
      if(array[left] > aim){
          return left -1;
      }
      // 否则就是当前位置
      return left;
  }
  
  // 插入排序
  public static void insertSort(int[] array) {
      // 从倒数第二位开始，遍历到底0位，遍历 N-1 次
      for (int i = array.length - 2; i >= 0; i--) {
          // 存储当前抽离的元素
          int temp = array[i];
          int index = searchIndex(array, i + 1, array.length - 1, temp);
  
          // #1. 根据插入的索引位置，进行数组的移动和插入
          int j = i + 1;
          while (j <= index) {
              array[j - 1] = array[j];
              j++;
          }
          array[index] = temp;
      }
  }
  

• 递归思想

   (1) 找出基准条件（递归结束条件）。
  （2）思考在基准条件下，会出现什么情况。
  （3）思考基准条件前一步的情况，或者函数执行情况。
  （4）配合递归公式,继续往前推进。
  （5）最后实现完善的代码。
  

• 快速排序

  void quickSort(int[] nums, int l, int r) {
      // 子数组长度为 1 时终止递归
      if (l >= r) return;
      // 哨兵划分操作
      int i = partition(nums, l, r);
      // 递归左（右）子数组执行哨兵划分
      quickSort(nums, l, i - 1);
      quickSort(nums, i + 1, r);
  }
  
  int partition(int[] nums, int l, int r) {
      // 以 nums[l] 作为基准数
      int i = l, j = r;
      while (i < j) {
          while (i < j && nums[j] >= nums[l]) j--;//右指针在前，左指针在后
          while (i < j && nums[i] <= nums[l]) i++;
          swap(nums, i, j);
      }
      swap(nums, i, l);
      return i;
  }
  
  void swap(int[] nums, int i, int j) {
      // 交换 nums[i] 和 nums[j]
      int tmp = nums[i];
      nums[i] = nums[j];
      nums[j] = tmp;
  }
  
  // 调用
  int[] nums = { 4, 1, 3, 2, 5 };
  quickSort(nums, 0, nums.length - 1);
  

• 归并排序

  void mergeSort(int[] nums, int l, int r) {
      // 终止条件
      if (l >= r) return;
      // 递归划分
      int m = (l + r) / 2;
      mergeSort(nums, l, m);
      mergeSort(nums, m + 1, r);
      // 合并子数组
      int[] tmp = new int[r - l + 1]; // 暂存需合并区间元素
      for (int k = l; k <= r; k++)
          tmp[k - l] = nums[k];
      int i = 0, j = m - l + 1;       // 两指针分别指向左/右子数组的首个元素
      for (int k = l; k <= r; k++) {  // 遍历合并左/右子数组
          if (i == m - l + 1)
              nums[k] = tmp[j++];
          else if (j == r - l + 1 || tmp[i] <= tmp[j])
              nums[k] = tmp[i++];
          else {
              nums[k] = tmp[j++];
          }
      }
  }
  
  // 调用
  int[] nums = { 3, 4, 1, 5, 2, 1 };
  mergeSort(nums, 0, len(nums) - 1);