常用排序面试常考排序

O(n²)

冒泡

外层循环i用来控制：排序次数，需要注意：排数组长度减一次，因为最后一个不需要排。内层循环j用来控制：每次比较到多少。需要注意：外层每循环一次，会排序好一个到最后，所以每次需要减去已经排序好的元素i，由于我们是用j和j+1比较，所以arr.length还需要减一 public void sort(int[] arr) { // 排数组长度减一次，因为最后一个不需要排 for (int i = 0; i < arr.length - 1; i++) { // 每次排序 for (int j = 0; j < arr.length - 1 - i; j++) { if (arr[j] > arr[j + 1]) { int tmp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = tmp; } } } }

插入

每次划分为左右两部分，左边表示已经排序好的部分，右边表示没有排序好的部分。 每次从已经排序好的最右边比较，这样可以一次移动元素。

/** * 每次划分为左右两部分，左边表示已经排序好的部分，右边表示没有排序好的部分。 * 每次从已经排序好的最右边比较，这样可以一次移动元素。 * @param arr */ public void sort(int[] arr) { for (int i = 0; i < arr.length; i++) { // 当前的值 int key = arr[i]; // 已经排序好的末尾 int idx = i - 1; while (idx >= 0 && arr[idx] > key) { // 把大的移动到后面，因为我们用key记住了当前的值，所以没事 arr[idx + 1] = arr[idx]; idx--; } // 放到它该放的位置 arr[idx + 1] = key; } }

O(n * log(n))

快速

每次把数组分为两部分，分别对这两部分进行排序。

public void sort(int[] arr) { int s = 0, e = arr.length - 1; sort(arr, s, e); } private void sort(int[] arr, int s, int e) { if (s < e) { // 中间点左右都排序好了 int mid = partition(arr, s, e); // 分别把中间点的左右部分都进行排序 sort(arr, s, mid); sort(arr, mid + 1, e); } } private int partition(int[] arr, int s, int e) { // 基准值 int pivot = arr[s]; int i = s, j = e; while (i < j) { // 从右向左找比当前基准值小的数 while (i < j && arr[j] >= pivot) { j--; } if (i < j) { arr[i++] = arr[j]; } while (i < j && arr[i] <= pivot) { i++; } if (i < j) { arr[j--] = arr[i]; } } arr[i] = pivot; return i; }

归并

把待排序数组分为左右两部分，再分

最后合并

public void sort(int[] arr) { partition(arr, 0, arr.length - 1); } private void partition(int[] arr, int s, int e) { if (s < e) { int m = s + (e - s) / 2; partition(arr, s, m); partition(arr, m + 1, e); merge(arr, s, m, e); } } // 合并两个有序数组 private void merge(int[] arr, int s, int m, int e) { // [1,2,3]传来的s和e是0和2，那么需要创建 e-s+1 长度的数组 int[] res = new int[e - s + 1]; int resIdx = 0; // i 从 s 到 m，j 从 m+1 到 e int i = s, j = m + 1; while (i <= m && j <= e) { if (arr[i] <= arr[j]) { res[resIdx++] = arr[i++]; } else { res[resIdx++] = arr[j++]; } } while (i <= m) { res[resIdx++] = arr[i++]; } while (j <= e) { res[resIdx++] = arr[j++]; } int arrIdx = s; for (int k = 0; k < resIdx; k++) { arr[arrIdx++] = res[k]; } }

堆排

建堆，每次把0和末尾元素交换，把剩下的再堆化调整

public void sort(int[] arr) { sort(arr, 0, arr.length - 1); } private void sort(int[] arr, int s, int e) { buildHeap(arr, s, e); int n = e; for (int i = e; i >= s; i--) { swap(arr, s, n); heapify(arr, s, s, --n); } } private void buildHeap(int[] arr, int s, int e) { for (int i = e / 2; i >= s; i--) { heapify(arr, i, s, e); } } private void heapify(int[] arr, int i, int s, int e) { int maxIdx = i; int left = i * 2 + 1; int right = i * 2 + 2; if (left >= s && left <= e && arr[left] > arr[maxIdx]) { maxIdx = left; } if (right >= s && right <= e && arr[right] > arr[maxIdx]) { maxIdx = right; } if (maxIdx != i) { swap(arr, maxIdx, i); heapify(arr, maxIdx, s, e); } } private void swap(int[] arr, int i, int j) { int tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp; }