他们思想的共同之处:分治
第一次看别人写的详细快排,归并细节,可能会感觉内容很多,很难学.小生建议:看一遍详解可以但不要指望一次就搞懂全部,搞懂基本原理就行,代码也不要指望第一次就能记住全部,先将代码会写,第一次写代码肯定会很困难.然后今后做题的时候肯定会遇到,今后重复重复+重复,就行了.
功夫是靠时间磨炼出来的,欲速则不达.
package Month3;
import java.util.*;
public class Demo231412 {public static void main(String[] args) {Scanner sc = new Scanner(System.in);int[] num = new int[] {5,4,2,8,7,9};mergeSort(num,0,num.length-1);for(int i=0;i<num.length;i++) {System.out.print(num[i]);}}//归并排序:static void mergeSort(int[] num,int left,int right) {if(left >= right) return;int mid = left+(right - left)/2;
// mergeSort(num,left,mid-1);//这里有细节的,不能写成mid -1,会死递归,//如果写成mid -1,会导致right那一行死递归.mergeSort(num,left,mid);mergeSort(num,mid+1,right);int i = left,j = mid+1;int [] a = new int[num.length];int k = left;while(i<=mid && j<=right) {if(num[i]<=num[j]) {a[k++] = num[i++];}else {a[k++] = num[j++];}}while(i<=mid) a[k++] = num[i++];while(j<=right) a[k++] = num[j++];for(int x = left;x<=right;x++) {num[x] = a[x];}}//快速排序:static void qSort(int[] num,int left,int right) {if(left>=right) return;int i = left,j = right,cur = left;int key = num[left];while(cur<=j) {if(num[cur]<key) {int tmp = num[cur];num[cur] = num[i];num[i] = tmp;i++;cur++;}else if(num[cur]>key) {int tmp = num[cur];num[cur] = num[j];num[j] = tmp;j--;}else {cur++;}}qSort(num,left,i-1);qSort(num,j+1,right);}
}