校招面试知识准备-排序篇
我会持续推出一些校招面试准备的帖子，希望对大家有用。本篇主要讲排序，已熟悉的可以跳过。
排序重点考察归并排序和快速排序，这两种排序要在任何时候完整快速地写出。其次才是冒泡排序、插入排序、选择排序、堆排序。
本文会依次讲解六种排序思路、图解过程、给出代码；最终会对六种排序进行复杂度和稳定性的比较。
广告位
大厂面经分享：https://www.nowcoder.com/discuss/846324，希望大家都拿到好的offer。
一、快速排序
1. 选取一个pivot value。
2. partition。
3. 在pivot两侧分别quicksort。
private void swap(int[] nums, int i, int j) {
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
private int partition(int[] nums, int lo, int hi) {
int i = lo, j = hi, pivot = lo; // nums[pivot]用于比较，是哨兵
while (i <= j) {
while (i <= j && nums[i] <= nums[pivot]) { // =号是要略过自己
i++;
}
while (i <= j && nums[j] > nums[pivot]) {
j--;
}
if (i > j) {
break;
}
swap(nums, i, j);
}
swap(nums, pivot, j); // j是最后一个小于哨兵的，pivot则是哨兵下标
return j; // 只考虑j左边和右边的
}
private void quickSort(int[] nums, int lo, int hi) {
int index = partition(nums, lo, hi);
System.out.println(index + "--" + nums[index]);
if (index > lo)
quickSort(nums, lo, index - 1);
if (index < hi)
quickSort(nums, index + 1, hi);
}
public void quickSort(int[] nums) {
quickSort(nums, 0, nums.length - 1);
} 二、归并排序
归并排序的思想是分治思想，divide and conquer。
1. 将数组分解为子数组，直到只包含一个元素，可以看成是有序的。
2. 合并有序数组，合并时保证有序。
private void mergeArray(int nums[], int lo, int mid, int hi, int tmp[]) {
int i = lo, j = mid + 1, k = 0;
while (i <= mid && j <= hi) {
if (nums[i] <= nums[j])
tmp[k++] = nums[i++];
else
tmp[k++] = nums[j++];
}
while (i <= mid)
tmp[k++] = nums[i++];
while (j <= hi)
tmp[k++] = nums[j++];
// System.out.println("lo : " + lo + "; k : " + k + "; tmp : " +
// Arrays.toString(tmp));
for (i = 0; i < k; i++)
nums[lo + i] = tmp[i];
// System.out.println("nums: " + Arrays.toString(nums));
}
private void mergeSort(int nums[], int lo, int hi, int tmp[]) {
if (lo < hi) {
// divide
int mid = lo + (hi - lo) / 2;
mergeSort(nums, lo, mid, tmp);
mergeSort(nums, mid + 1, hi, tmp);
// conquer
mergeArray(nums, lo, mid, hi, tmp);
}
}
public void mergeSort(int nums[]) {
int[] tmp = new int[nums.length];
mergeSort(nums, 0, nums.length - 1, tmp);
} 三、冒泡排序
冒泡排序的思想是：比较相邻的两个元素，将最大的元素浮到最上面。如此进行len-1轮冒泡。
public void bubbleSort(int nums[]) {
for (int i = 0; i < nums.length - 1; i++) { //len-1 circulation
boolean flag = false;
for (int j = 1; j < nums.length - i; j++) { // swap between j-1 and j, j is becoming smaller
if (nums[j - 1] > nums[j]) {
swap(nums, j - 1, j);
flag = true;
}
}
if (!flag) // if flag does not change, the nums is sorted, break;
break;
System.out.println(Arrays.toString(nums));
}
} 四、选择排序
数组由无序区和有序区构成，每次选取无序区最小的数字和当前有序区的尾部节点进行交换。
public void selectionSort(int[] nums) { // two areas, left sorted, right unsorted
int i, j, minIndex;
for (i = 0; i < nums.length - 1; i++) {
minIndex = i;
for (j = i + 1; j < nums.length; j++) {
if (nums[j] < nums[minIndex])
minIndex = j; // find the min in unsorted array
}
if (minIndex != i) { // min is not itself
swap(nums, i, minIndex); //swap i and minIndex
}
}
} 五、插入排序
数组当前值与前面的值相比较，如果小于就插入，原来的元素后移。保持前面有序，后面无序。
insertionSort是相邻两两比较。
public void insertionSort(int[] nums) {
int i, j, curr;
for (i = 1; i < nums.length; i++) {
curr = nums[i]; // store the curr
j = i;
while (j > 0 && nums[j - 1] > curr) { // keep array left of nums[i] has been ordered
nums[j] = nums[j - 1];
j--;
}
nums[j] = curr;
}
} 六、堆排序
1. 构建大顶堆。建堆时间是O(n)，是从nums[half]到nums[0]的维护大顶堆的过程。
2. 选择顶，并与第0位置元素交换。
3. 由于步骤2的的交换可能破环了最大堆的性质，第0不再是最大元素，需要调用maxHeap调整堆，调整堆的时间复杂度为logk，如果需要重复步骤2。排序时间是O(nLogn)。
构建大顶堆过程：
堆排序过程：
private void buildMaxHeap(int[] nums) {
if (nums == null || nums.length <= 1) {
return;
}
// 从没有儿子的节点开始，维持大顶堆性质
int half = nums.length / 2;
for (int i = half; i >= 0; i--) {
maxHeap(nums, nums.length, i);
}
}
private void maxHeap(int[] nums, int heapSize, int curr) {
int left = curr * 2 + 1;
int right = left + 1;
// max(自己，左儿子，右儿子)
int maxIndex = curr;
if (left < heapSize && nums[left] > nums[maxIndex]) {
maxIndex = left;
}
if (right < heapSize && nums[right] > nums[maxIndex]) {
maxIndex = right;
}
// 如果找到大儿子，则替换，并继续向下探
if (curr != maxIndex) {
swap(nums, curr, maxIndex);
maxHeap(nums, heapSize, maxIndex);
}
}
public void heapSort(int[] nums) {
if (nums == null || nums.length <= 1) {
return;
}
// 从nums[half]到nums[0]构建大顶堆
buildMaxHeap(nums);
for (int i = nums.length - 1; i >= 1; i--) {
// 从堆的最底部开始，将当前元素与堆顶即最大元素交换
swap(nums, 0, i);
// 维持大顶堆性质，这样保证每次与当前元素交换的都是堆中最大元素
maxHeap(nums, i, 0);
}
} 几种排序的比较
稳定性：能保证排序前两个相等的数据其在序列中的先后位置顺序与排序后它们两个先后位置顺序相同。举几个例子来理解下什么叫所谓的不稳定：
- 选择排序反例：5 8 5 2 9，第一趟选择第1个元素5会与2进行交换，那么原序列中两个5的相对先后顺序也就被破坏。
- 快速排序反例：5 3 3 4 3 8 9 10 11，第一趟pivot5和3交换，破坏了3的先后顺序。
- 堆排序反例：3 27 36 27，如果堆顶3先输出，则第三层的27（最后一个27）跑到堆顶，然后堆稳定，继续输出堆顶，是刚才那个27，这样说明后面的27先于第二个位置的27输出，不稳定。
查看3道真题和解析