java常见数据结构

gcdya

常见数据结构

1.查找、排序

稳定的排序：归并、冒泡、插入、基数

1.1二分查找

前提:数据是有序排列的

1. 定义左边界l、右边界r，循环while(l<=r)
2. 获取中间索引m=(l+r)>>1

3. 中间索引m的值与待查找的值t比较

   • arr[m]==t,表示已经找到，则返回中间索引
   • arr[m]>t,当前中间索引值右侧的其他数大于待查找的值，则r=m-1
   • arr[m]<t,当前中间索引值左侧的其他数小于待查找的值，则l=m+1
     4.当l>r时，表示没有找到，结束循环

   public static int binarySearchDemo(int[] arr, int t) {
   int l = 0;
   int r = arr.length - 1;
   int m;
   while (l <= r) {
   m = (l + r) >> 1;
   if (arr[m] == t) {
   //已找到，返回当前索引
   return m;
   } else if (arr[m] > t) {
   //中间值右侧大于t
   r = m - 1;
   } else {
   //中间值左侧小于t
   l = m + 1;
   }
   }
   return -1;
   }

选择题中考察 查找次数：   

• 奇数看中间偏左（向下取整）
• 偶数看中间

1.2冒泡排序(稳定)

• 依次比较数组中相邻两个元素大小，如a[j]>a[j+1]，则交换这两个元素。两两比较一遍称为一轮冒泡。(类似水底冒泡,气泡在上升至水面途中变的越来越大)

• 设置一个标志符，如果标识符未改变状态(未发生元素交换)则表示排序已经完成，跳出循环。

  public static void bubbleSort(int[] arr) {
      for (int i = 0; i < arr.length-1; i++) {
          boolean flag=false;
          for (int j = 0; j < arr.length-1-i; j++) {
              if(arr[j]>arr[j+1 
                  swap(arr,j,j+1);
                  flag=true;
              }
          }
          //如果没有发生交换，代表已经排序完成
          if(!flag){
              break;
          }
      }
      System.out.println(Arrays.toString(arr));
  }
  public static void swap(int[] arr, int i, int j) {
      int t = arr[i];
      arr[i]=arr[j];
      arr[j]=t;
  }

  1.3选择排序

1. 将数组分为两个子集 ，已排序的和未排序的，每一轮从未排序的子集中选出最小元素，放入已排序的子集中。循环多次，直至整个数据有序。

2. 为了减少交换次数，每一轮先找出最小值的索引。在每轮最后在交换元素。

   public static void selectionSort(int[] arr) {
   for (int i = 0; i < arr.length - 1; i++) {
   //记录最小值的索引值
   int s =i;
   //内层循环 初始值 从最小索引s+1处开始
   for (int j = s + 1; j < arr.length; j++) {
   if (arr[s] > arr[j]) {
   s = j;
   }
   }
   //如果最小值索引发生了改变则要交换位置
   if (s != i) {
   int temp = arr[0];
   temp = arr[i];
   arr[i] = arr[s];
   arr[s] = temp;
   }
   }
   System.out.println(Arrays.toString(arr));
   }

1.3选择排序

• public static void selectionSort(int[] arr) {
  for (int i = 0; i < arr.length - 1; i++) {
  //记录最小值的索引值
  int s = i;
  //内层循环 初始值 从最小循环+1索引处开始
  for (int j = s + 1; j < arr.length; j++) {
  if (arr[s] > arr[j]) {
  s = j;
  }
  }
  //如果最小值索引发生了改变则要交换位置
  if (s != i) {
  int temp = arr[0];
  temp = arr[i];
  arr[i] = arr[s];
  arr[s] = temp;
  }
  }
  System.out.println(Arrays.toString(arr));
  }

1.4插入排序(稳定)

插入排序与选择排序的比较

1. 将数据分为排序区域、未排序区域。每一轮从未排序区域中取出第一个元素，插入到排序区域(需按顺序)，循环多次直至整个数组有序。
2. 待插入元素进行比较时，遇到比子集小的元素，代表找到了插入位置，无需进行后续比较。

3. 插入时直接移动元素，而非交换

   public static void insertSort(int[] arr) {
   for (int i = 1; i < arr.length ; i++) {
   //代表待插入的元素
   int t = arr[i];
   //代表已排序区域的元素索引
   int j = i - 1;
   while (j >= 0) {
   if (t < arr[j]) {
   arr[j + 1] = arr[j];
   } else {
   //退出循环，减少比较次数
   break;
   }
   j--;
   }
   //因为j--了
   arr[j + 1] = t;
   }
   System.out.println(Arrays.toString(arr));
   }

1.5希尔排序的概念(无需掌握代码)

选择增量gap=length/2，缩小增量继续以gap = gap/2的方式，这种增量选择我们可以用一个序列来表示，{n/2,(n/2)/2...1}，称为增量序列。希尔排序的增量序列的选择与证明是个数学难题，我们选择的这个增量序列是比较常用的，也是希尔建议的增量，称为希尔增量，但其实这个增量序列不是最优的。

1.6快速排序

分而治之的思想(divide-and-conquer)

1.每一轮排序选择一个基准点(pivot)进行分区

1. 让小于基准点的元素进入一个分区，大于的进入另一个分区
2. 当分区完成时，基准点元素的位置和就是其最终位置

2.在子分区内重复多次上述过程，直到子分区元素个数为1.

单边快排(洛穆托分区方案)

1. 选择最有元素作为基准点元素
2. j指针负责找到比基准点小的元素，一旦找到则与i进行交换
3. i指针维护小于基准点元素边界，也是每次交换的目标索引

4. 最后基准点与i交换，i为分区位置

   public static void quick(int[] a, int l, int h) {
   //如果左边界大于等于右边界，结束递归
   if (l >= h) {
   return;
   }
   //p 索引值
   int p = partition(a, l, h);
   //左边分区的范围确定
   quick(a, l, p - 1);
   //右边分区的范围确定
   quick(a, p + 1, h);
   }

   /**
    * @Param arr 待排序的数组
    * @param l   左边界
    * @param h   右边界
    * @Return 本次基准点元素最终位置
    */
   private static int partition(int[] arr, int l, int h) {
       //1.基准元素
       int pv = arr[h];
       //2.左边界
       int i = l;
       for (int j = l; j < h; j++) {
           if (arr[j] < pv) {
               //3.arr[j]小于基准点则交换,放在基准点的左边
               swap(arr, i, j);
               //4，左边界+1
               i++;
           }
       }
       //5.基准点与i交换
       swap(arr, h, i);
       System.out.println(Arrays.toString(arr) + "i=" + i);
       //本次基准点元素最终位置
       return i;
   }
   
   public static void swap(int[] arr, int i, int j) {
       int temp = arr[i];
       arr[i] = arr[j];
       arr[j] = temp;
   }

1.7面试中出现的题目

1. 使用直接插入排序算法对序列18,23,19,9,23,15进行排序，第三趟排序后的结果为
   [18, 23, 19, 9, 23, 15]
   [18, 19, 23, 9, 23, 15]
   [9, 18, 19, 23, 23, 15]
   [9, 18, 19, 23, 23, 15]
   [9, 15, 18, 19, 23, 23]
2. 使用选择排序算法对序列18,23,19,9,23,15进行排序，第三趟排序后的结果为
   [9, 23, 19, 18, 23, 15]
   [9, 15, 19, 18, 23, 23]
   [9, 15, 18, 19, 23, 23]
   [9, 15, 18, 19, 23, 23]
   [9, 15, 18, 19, 23, 23]

reder

中间夹杂了php的代码实现......

gcdya

reder 发表于 2022-4-1 16:40
中间夹杂了php的代码实现......

都是java哇