题解 | #排序#
排序
http://www.nowcoder.com/practice/2baf799ea0594abd974d37139de27896
package sort;
public class MySort {
public static void main(String[] args) { int[] arr = new int[]{10, 7, 2, 6, 3, 4, 5, 9, 8};
// arr = sortByBubbling(arr);
arr = sortArray(arr);
}
/** * 冒泡排序 */ public static int[] sortByBubbling(int[] arr) { for (int i = 0; i < arr.length; i++) { for (int j = 0; j < arr.length - i - 1; j++) { int tmp; if (arr[j] > arr[j + 1]) { tmp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = tmp; } } } return arr; } /** * 快速排序 start * https://www.bilibili.com/video/BV117411x72U?from=search&seid=9811547839771013274 * https://leetcode-cn.com/problems/sort-an-array/solution/dong-hua-mo-ni-yi-ge-po-dui-pai-wo-gao-l-i6mt/ */ public static int[] sortArray(int[] nums) { quickSort(nums, 0, nums.length - 1); return nums; } public static void quickSort(int[] nums, int low, int high) { if (low < high) { int index = partition(nums, low, high); quickSort(nums, low, index - 1); quickSort(nums, index + 1, high); } } public static int partition(int[] nums, int low, int high) { int pivot = nums[low]; while (low < high) { //移动high指针 while (low < high && nums[high] >= pivot) { high--; } //填坑 if (low < high) { nums[low] = nums[high]; } while (low < high && nums[low] <= pivot) { low++; } //填坑 if (low < high) { nums[high] = nums[low]; } } //基准数放到合适的位置 nums[low] = pivot; return low; }
// 快速排序 end
/** * 堆排序 */ public static int[] heapSort(int[] arr) { return arr; } /** * 归并排序 */ public static int[] mergeSort(int[] arr) { return arr; }
}