Java实现快速排序和堆排序的示例代码

Java实现快速排序和堆排序是经常被面试官提问的面试题目之一。下面是一份攻略，来帮助大家快速掌握这两种排序算法。

快速排序

快速排序（Quick Sort）是一种基于分治思想实现的排序算法，其主要思路是通过分区（Partition）操作将一个数组分成两个子数组，再分别对子数组进行排序，从而达到整个数组有序的目的。

以下是Java实现快速排序的示例代码：

public void quickSort(int[] arr, int left, int right) {
  if (left >= right) {
    return;
  }
  int pivot = partition(arr, left, right);
  quickSort(arr, left, pivot - 1);
  quickSort(arr, pivot + 1, right);
}

public int partition(int[] arr, int left, int right) {
  int pivot = arr[right];
  int i = left - 1;
  for (int j = left; j < right; j++) {
    if (arr[j] < pivot) {
      i++;
      swap(arr, i, j);
    }
  }
  swap(arr, i + 1, right);
  return i + 1;
}

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

在这个示例代码中，我们使用了两个函数：quickSort和partition，其中，quickSort函数用于快速排序整个数组，partition函数用于实现分区操作，把整个数组分成两个子数组（其中一个小于基准值，一个大于基准值）。

示例：

int[] arr = {3, 5, 2, 7, 1, 8, 4};
quickSort(arr, 0, arr.length - 1);
for (int i : arr) {
  System.out.print(i + " ");
}

该示例输出结果为：1 2 3 4 5 7 8。

堆排序

堆排序（Heap Sort）是一种基于堆的排序算法，其主要思路是先将待排序的序列建成一个大根堆或小根堆，然后将堆顶元素（即最大值或最小值）与堆的最后一个节点交换，然后再在剩下的节点中调整堆，使其重新成为堆。重复此过程，直到整个序列有序。

以下是Java实现堆排序的示例代码：

public void heapSort(int[] arr) {
  int len = arr.length;
  // 构建大根堆
  for (int i = len / 2 - 1; i >= 0; i--) {
    adjustHeap(arr, i, len);
  }
  // 排序
  for (int i = len - 1; i > 0; i--) {
    swap(arr, 0, i);
    adjustHeap(arr, 0, i);
  }
}

public void adjustHeap(int[] arr, int i, int len) {
  int temp = arr[i];
  for (int j = 2 * i + 1; j < len; j = 2 * j + 1) {
    if (j + 1 < len && arr[j] < arr[j + 1]) {
      j++;
    }
    if (arr[j] > temp) {
      arr[i] = arr[j];
      i = j;
    } else {
      break;
    }
  }
  arr[i] = temp;
}

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

在这个示例代码中，我们使用了三个函数：heapSort，adjustHeap和swap，其中，heapSort函数用于堆排序整个数组，adjustHeap函数用于调整堆，使其符合大根堆或小根堆的特点，swap函数用于交换两个节点的值。

示例：

int[] arr = {3, 5, 2, 7, 1, 8, 4};
heapSort(arr);
for (int i : arr) {
  System.out.print(i + " ");
}

该示例输出结果为：1 2 3 4 5 7 8。