本文共 2612 字,大约阅读时间需要 8 分钟。
Given an array of integers nums, sort the array in ascending order.
快排模板
注意!!!为了使左右指针错开,以防止死循环,快排的所有判断都要带等号!class Solution { public ListsortArray(int[] nums) { quickSort(nums, 0, nums.length - 1); List res = new ArrayList<>(); for(int i = 0; i < nums.length; i++) { res.add(nums[i]); } return res; } private void quickSort(int[] nums, int start, int end) { if(start >= end) { return; } int left = start, right = end; int pivot = nums[(start + end) / 2]; while(left <= right) { while(left <= right && nums[left] < pivot) { left++; } while(left <= right && nums[right] > pivot) { right--; } if(left <= right) { int temp = nums[left]; nums[left] = nums[right]; nums[right] = temp; left++; right--; } } quickSort(nums, start, right); quickSort(nums, left, end); }}
归并模板
注意!!!在merge数组时,因为是在每段内排序,index是从start开始的!class Solution { public ListsortArray(int[] nums) { int[] temp = new int[nums.length]; mergeSort(nums, 0, nums.length - 1, temp); List res = new ArrayList<>(); for(int i = 0; i < nums.length; i++) { res.add(nums[i]); } return res; } private void mergeSort(int[] nums, int start, int end, int[] temp) { if(start >= end) { return; } mergeSort(nums, start, (start + end) / 2, temp); mergeSort(nums, (start + end) / 2 + 1, end, temp); merge(nums, start, end, temp); } private void merge(int[] nums, int start, int end, int[] temp) { int middle = (start + end) / 2; int leftIndex = start; int rightIndex = middle + 1; //注意!!!是在每段内排序,index是从start开始的!!! int index = start; while(leftIndex <= middle && rightIndex <= end) { if(nums[leftIndex] < nums[rightIndex]) { temp[index++] = nums[leftIndex++]; } else { temp[index++] = nums[rightIndex++]; } } while(leftIndex <= middle) { temp[index++] = nums[leftIndex++]; } while(rightIndex <= end) { temp[index++] = nums[rightIndex++]; } //同上 for(int i = start; i <= end; i++) { nums[i] = temp[i]; } }}
转载地址:http://jyqvb.baihongyu.com/