Java面试题---第十三弹 数据结构

• 数组和链表的区别。

• 顺序结构和链式结构的区别？

• 线性表查找有那几类？

• 单链表和顺序表的对比

• 顺序结构和链式结构的区别

• 度为 2 的树和二叉树的区别

• 树的存储结构

• 树的遍历

• 求二叉树的高度

• 在二叉搜索树中查找第k个最大值

• 查找与根节点距离k的节点

• 在二叉树中查找给定节点的祖先节点

• B树和B+树的区别，以一个m阶树为例

• 请比较最小生成树的算法（普里姆算法，克鲁斯卡尔算法）的异同

• 什么是平衡二叉树

冒泡排序 O(n²)

ava
public class BubbleSort implements IArraySort {
   @Override
  public int[] sort(int[] sourceArrray){
    // 对 arr 进行拷贝，不改变参数内容
    int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);
    for(int i=1;i<arr.length;i++){
      boolean flag=true;
      for(int j=0;j<arr.length-1;j++){
        if(arr[j]>arr[j+1]){
          int temp=arr[j];
          arr[j]=arr[j+1];
          arr[j+1]=temp;
          flag=false;
        }
      }
      if(flag){
        bread;
      }
    }
    return arr;
  }
}

选择排序 O(n²)

ava
public class SelectionSort implements IArraySort {

  @Override
  public int[] sort(int[] sourceArray) throws Exception {
     // 对 arr 进行拷贝，不改变参数内容
     int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);
    // 总共要经过 N-1 轮比较
    for(int i=0;i<arr.length-1;i++){
      int min=i;
      // 每轮需要比较的次数 N-i
      for(int j=i+1;j<arr.length;j++){
        if(arr[j]<arr[min]){
          min=j;
        }
      }
      // 将找到的最小值和i位置所在的值进行交换
      if(1!=min){
        int temp=arr[i];
        arr[i]=arr[min];
        arr[min]=temp;
      }
    }
    return arr;
  }
}

插入排序 O(n²)

ava
public class InsertSort implements IArraySort {

  @Override
  public int[] sort(int[] sourceArray) throws Exception {
     // 对 arr 进行拷贝，不改变参数内容
     int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);
    
     for(int i=1;i<arr.length;i++){
       
       int temp=arr[i];
       int j=i;
       
       while(j>0 && temp<arr[j-1]){
         arr[j]=a[j-1];
         j--;
       }
       
       if(j!=i){
         arr[j]=temp;
       }
     }
    return arr;
  }
}

希尔排序（插入排序的改进） O(nlogn)

ava
public static void shellSort(int[] arr) {
  int length = arr.length;
  int temp;
  for (int step = length  2; step >= 1; step = 2) {
    for (int i = step; i < length; i++) {
      
      temp = arr[i];
      int j = i - step;
      
      while (j >= 0 && arr[j] > temp) {
        arr[j + step] = arr[j];
        j -= step;
      }
      
      arr[j + step] = temp;
      
    }
  }
}

归并排序O(nlogn)

ava
public class MergeSort implements IArraySort {

  @Override
  public int[] sort(int[] sourceArray) throws Exception {
    // 对 arr 进行拷贝，不改变参数内容
    int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);

    if (arr.length < 2) {
      return arr;
    }
    int middle = (int) Math.floor(arr.length  2);

    int[] left = Arrays.copyOfRange(arr, 0, middle);
    int[] right = Arrays.copyOfRange(arr, middle, arr.length);

    return merge(sort(left), sort(right));
  }

  protected int[] merge(int[] left, int[] right) {
    int[] result = new int[left.length + right.length];
    int i = 0;
    while (left.length > 0 && right.length > 0) {
      if (left[0] <= right[0]) {
        result[i++] = left[0];
        left = Arrays.copyOfRange(left, 1, left.length);
      } else {
        result[i++] = right[0];
        right = Arrays.copyOfRange(right, 1, right.length);
      }
    }

    while (left.length > 0) {
      result[i++] = left[0];
      left = Arrays.copyOfRange(left, 1, left.length);
    }

    while (right.length > 0) {
      result[i++] = right[0];
      right = Arrays.copyOfRange(right, 1, right.length);
    }

    return result;
  }

}

快速排序 O(nlogn)

ava
public class QuickSort implements IArraySort {

  @Override
  public int[] sort(int[] sourceArray) throws Exception {
    // 对 arr 进行拷贝，不改变参数内容
    int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);

    return quickSort(arr, 0, arr.length - 1);
  }

  private int[] quickSort(int[] arr, int left, int right) {
    if (left < right) {
      int partitionIndex = partition(arr, left, right);
      quickSort(arr, left, partitionIndex - 1);
      quickSort(arr, partitionIndex + 1, right);
    }
    return arr;
  }

  private int partition(int[] arr, int left, int right) {
    // 设定基准值（pivot）
    int pivot = left;
    int index = pivot + 1;
    for (int i = index; i <= right; i++) {
      if (arr[i] < arr[pivot]) {
        swap(arr, i, index);
        index++;
      }
    }
    swap(arr, pivot, index - 1);
    return index - 1;
  }

  private void swap(int[] arr, int i, int j) {
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
  }

}

堆排序 O(nlogn)

ava
public class HeapSort implements IArraySort {

  @Override
  public int[] sort(int[] sourceArray) throws Exception {
    // 对 arr 进行拷贝，不改变参数内容
    int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);

    int len = arr.length;

    buildMaxHeap(arr, len);

    for (int i = len - 1; i > 0; i--) {
      swap(arr, 0, i);
      len--;
      heapify(arr, 0, len);
    }
    return arr;
  }

  private void buildMaxHeap(int[] arr, int len) {
    for (int i = (int) Math.floor(len  2); i >= 0; i--) {
      heapify(arr, i, len);
    }
  }

  private void heapify(int[] arr, int i, int len) {
    int left = 2 * i + 1;
    int right = 2 * i + 2;
    int largest = i;

    if (left < len && arr[left] > arr[largest]) {
      largest = left;
    }

    if (right < len && arr[right] > arr[largest]) {
      largest = right;
    }

    if (largest != i) {
      swap(arr, i, largest);
      heapify(arr, largest, len);
    }
  }

  private void swap(int[] arr, int i, int j) {
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
  }

}