按要求排序(JAVA)顺便复习一下mergesort和quicksort
输入整型数组和排序标识,对其元素按照升序或降序进行排序
http://www.nowcoder.com/questionTerminal/dd0c6b26c9e541f5b935047ff4156309
很奇怪用Arrays.sort(arr, Collections.reverseOrder()) 会报错。
import java.util.*; public class Main{ public static void main(String[] args){ Scanner in = new Scanner(System.in); while (in.hasNext()){ int n = in.nextInt(); int[] arr = new int[n]; for (int i = 0; i < n; i++){ arr[i] = in.nextInt(); } int flag = in.nextInt(); helper(flag, arr); } } private static void helper(int flag, int[] arr){ StringBuilder sb = new StringBuilder(); //Arrays.sort(arr); //mergeSort(arr); quickSort(arr); if (flag == 0){ for (int i = 0; i < arr.length; i++){ sb.append(arr[i]); sb.append(' '); } }else{ for (int i = arr.length - 1; i >= 0; i--){ sb.append(arr[i]); sb.append(' '); } } System.out.println(sb.toString()); } //mergesort private static void mergeSort(int[] arr){ int[] temp = new int[arr.length]; mergeSort(arr, temp, 0, arr.length - 1); } private static void mergeSort(int[] arr, int[] temp, int l, int r){ if (l == r) return; int mid = l + (r-l)/2; mergeSort(arr, temp, l, mid); mergeSort(arr, temp, mid + 1, r); merge(arr, temp, l ,mid, r); } private static void merge(int[] arr, int[] temp, int l, int mid, int r){ for (int i = 0 ; i < arr.length; i ++){ temp[i] = arr[i]; } int p1 = l; int p2 = mid + 1; int k = l; while(p1 <= mid && p2 <= r){ if (temp[p1] < temp[p2]){ arr[k] = temp[p1]; p1++; }else{ arr[k] = temp[p2]; p2++; } k++; } while(p1 <= mid){ arr[k] = temp[p1]; p1++; k++; } } //quicksork private static void quickSort(int[] arr){ quickSort(arr, 0, arr.length-1); } private static void quickSort(int[] arr, int l, int r){ if (l >= r) return; int idx = help(arr, l, r); quickSort(arr, l, idx-1); quickSort(arr, idx+1, r); } private static int help(int[] arr, int l, int r){ int k = arr[r]; int p1 = l; int p2 = r - 1; while (p1 <= p2){ if (arr[p1] <= k){ p1++; }else if (arr[p2] > k){ p2--; }else{ int cur = arr[p1]; arr[p1] = arr[p2]; arr[p2] = cur; p1++; p2--; } } arr[r] = arr[p1]; arr[p1] = k; return p1; } }