1.选择排序
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28
| class Solution { public int[] sortArray(int[] nums) {
int n = nums.length; for (int i = 0; i < n; i++) { int minIdx = i; for (int j = i + 1; j < n; j++) { if (nums[j] < nums[minIdx]) minIdx = j; } swap(nums, i, minIdx); } return nums; }
private void swap(int[] nums, int i, int j) { int t = nums[i]; nums[i] = nums[j]; nums[j] = t; } }
|
2.插入排序
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
| class Solution { public int[] sortArray(int[] nums) {
int n = nums.length; for (int i = 1; i < n; i++) { int t = nums[i]; int j = i; while (j > 0 && nums[j - 1] > t) { nums[j] = nums[j - 1]; j--; } nums[j] = t; } return nums; } }
|
3.冒泡排序
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33
| class Solution { public int[] sortArray(int[] nums) {
int n = nums.length; for (int i = n - 1; i >= 0; i--) { boolean sorted = true; for (int j = 0; j < i; j++) { if (nums[j] > nums[j + 1]) { swap(nums, j, j + 1); sorted = false; } } if (sorted) break; } return nums; }
private void swap(int[] nums, int i, int j) { int t = nums[i]; nums[i] = nums[j]; nums[j] = t; } }
|
4.快速排序
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52
| class Solution { public int[] sortArray(int[] nums) {
int n = nums.length; quickSort(nums, 0, n - 1); return nums; }
private void quickSort(int[] nums, int low, int high) { if (low >= high) return; int l = low, r = high; int pivot = nums[low]; while (l < r) { while (l < r && nums[r] > pivot) r--; while (l < r && nums[l] <= pivot) l++; if (l < r) { int t = nums[l]; nums[l] = nums[r]; nums[r] = t; } } nums[low] = nums[l]; nums[l] = pivot; quickSort(nums, low, r - 1); quickSort(nums, r + 1, high); } }
|
5.归并排序
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48
| class Solution { int[] t;
public int[] sortArray(int[] nums) {
int n = nums.length; t = new int[n]; mergeSort(nums, 0, n - 1); return nums; }
private void mergeSort(int[] nums, int l, int r) { if (l >= r) return; int mid = l + (r - l) / 2; mergeSort(nums, l, mid); mergeSort(nums, mid + 1, r); merge(nums, l, mid, r); }
private void merge(int[] nums, int l, int mid, int r) { int idx = l; int i = l, j = mid + 1; while (i <= mid && j <= r) { if (nums[i] <= nums[j]) { t[idx++] = nums[i++]; } else { t[idx++] = nums[j++]; } } while (i <= mid) t[idx++] = nums[i++]; while (j <= r) t[idx++] = nums[j++]; System.arraycopy(t, l, nums, l, r - l + 1); } }
|
6.堆排序
堆是具有以下性质的完全二叉树:每个结点的值都大于或等于其左右孩子结点的值,称为大顶堆;
或者每个结点的值都小于或等于其左右孩子结点的值,称为小顶堆。如下图:

参考资料:堆排序(超详细图解 java 版)
主要步骤:
1.将无序序列构建成一个堆,根据升序降序需求选择大顶堆或小顶堆(升序一般用大顶堆)
2.将堆顶元素与末尾元素交换,将最大元素"沉"到数组末端
3.重新调整结构,使其满足堆定义,然后继续交换堆顶元素与当前末尾元素
4.反复执行调整+交换步骤,直到整个序列有序
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58
| class Solution { public int[] sortArray(int[] nums) {
int n = nums.length; for (int i = n / 2 - 1; i >= 0; i--) { sink(nums, i, n - 1); } for (int end = n - 1; end > 0; end--) { swap(nums, 0, end); sink(nums, 0, end - 1); } return nums; }
private void sink(int[] nums, int target, int end) { int idx = target; int t = nums[target]; while (2 * idx + 1 <= end) { int maxLR = 2 * idx + 1; if (maxLR + 1 <= end && nums[maxLR + 1] > nums[maxLR]) maxLR++; if (nums[idx] < nums[maxLR]) { swap(nums, idx, maxLR); } else { break; } idx = maxLR; } }
private void swap(int[] nums, int i, int j) { int t = nums[i]; nums[i] = nums[j]; nums[j] = t; } }
|