java排序算法(冒泡，插入，选择，快速，堆，归并，希尔，基数)

import java.util.Arrays;
import java.util.LinkedList;/*** * * 各种排序: 冒泡，插入，选择，快速，堆，归并，希尔，基数*/
public class Sorts {//1. 冒泡：//时间复杂度:n(n-1)/2=O(n^2)//1. 第一次把最大的放后面//2. 把最大的放后面。。。//3. 。。。static void BubbleSort(int arr[], int start, int end){int len = end - start + 1;for(int i = 0; i < len; i++){for(int j = 0; j < len - i - 1; j++){if(arr[j] > arr[j + 1]){int tmp = arr[j];arr[j] = arr[j+1];arr[j+1] = tmp;}}}}//2. 插入排序：//时间复杂度：最好O(n), 最坏O(n^2)//评价：稍快于冒泡//1.先认为第一个最小//2.第二个与第一个比较，如果第二个小，则交换。//3.第N次循环的时候，前面N个元素都是排好序的。static void standInsertSort(int arr[], int start, int end){int len = end - start + 1;for(int i = 1; i < len; i++){int tmp = arr[i];int j = -1;for(j = i - 1 ; j >= 0; j--){if(arr[j] > tmp){arr[j+1] = arr[j];}else{break;}}arr[j+1] = tmp;}}//3. 选择排序//时间复杂度：同插入排序，可能比冒泡快点，比插入慢点。//评价：无//1.找到最小的放在最前面//2.找到最小的放在第二位//3. ... ...static void selectSort(int arr[], int start, int end){int len = end - start + 1;int min = Integer.MAX_VALUE;for(int i = 0; i < len - 1; i++){//给arr按位赋值int mark = -1;for(int j = i; j < len; j++){//找出最小值if(arr[j] < min){min = arr[j];mark = j;}}arr[mark] = arr[i];arr[i] = min;//找到最小值min = Integer.MAX_VALUE;//重置min}}//4. 快速排序//时间复杂度：n(logn)//评价：比插入排序快static void quickSort(int arr[], int start, int end){int sStore = start, eStore = end;int len = end - start + 1;switch(len){case 0:case 1:return;case 2:arr[0] = arr[0]^arr[1];arr[1] = arr[0]^arr[1];arr[0] = arr[0]^arr[1];return;}int mark = arr[start];//需要从右面找一个比mark小的值来填充arr[start]//System.out.println("Sorts.quickSort() 时间复杂度为 " + len);while(start < end){while(arr[end] > mark && end > start){end--;}if(end > start){//找到了，则填充arr[start]arr[start] = arr[end];start++;//start值确定所以，加一。}else{//没有找到，这表示start右面的值全都比mark大了。。此时end == start，循环结束}//此时，arr[start]与arr[end]重复了。。需要从左面找一个比mark大的值来填充arr[end]。//方法同上while(arr[start] < mark&& end > start){start++;}if(end > start){//找到了,填充arr[end]arr[end] = arr[start];end--;//end值确定，所以减一。}else{//没找到，这表示start左面的值全部比mark小了。。}}//我们知道，每次按照算法计算一次循环之后，数组中都会出现2个相同的值，所以会缺少一个值，这个值就是mark。//因为我们从开头把mark提取之后，就没有把它赋回。//所以mark应该放哪呢？//因为循环结束只有一种可能，就是(start == end)这意味着什么？//意味着：start的左面全部比mark小，end的右面全部比mark大。//结果明确了吧。把start赋值成mark就恰好达到我们的要求了。arr[start] = mark;//至此，数组从0-->start的值，全部比start+1 --> end的值要小了。//果断递归quickSort(arr, sStore, start - 1);//之前写的不是start-1而是start，结果数据若超过65536会栈溢出。quickSort(arr, start+1, eStore);}//5. 堆排序//时间复杂度: n/2 + log(n) + log(n-1) + ...+ log1 ==> n(logn)static class heapSort{private static void swapArrayElement(int array[], int a, int b){if(a == b){return;}array[a] = array[a]^array[b];array[b] = array[a]^array[b];array[a] = array[a]^array[b];}private static void judgeHeap(int array[], int i, int len){//调整第i个元素为顶的3元大根堆int lChild = 2*i + 1;int rChild = 2*i + 2;if(lChild > len - 1){return;}if(rChild > len - 1){if(array[i] < array[lChild]){swapArrayElement(array, i, lChild);}return;}int max = i;if(array[i] < array[lChild]){max = lChild;}if(array[max] < array[rChild]){max = rChild;}if(max != i){swapArrayElement(array, max, i);judgeHeap(array, max, len);}}static void hSort(int array[], int from, int to) {int len = to - from + 1;if (len <= 1) {return;}for (int i = len - 1; i >= 0; i--) {//创建初始堆，从最后一个元素开始作为3元堆顶，//使其满足堆定义。这样总能把最大元素推到堆顶。judgeHeap(array, i, len);}for(int i = 0; i < len; i++){swapArrayElement(array, 0, len - i - 1);//把最大元素放到末尾。judgeHeap(array, 0, len - i - 1);//改变的元素可能不符合堆定义。}}}//6.归并//分治法//>如果问题缩小到一定规模可以很容易求解//>可以分解成相同的子问题//>问题可由子问题的结果合并而得出。(是否使用分治法，完全取决于此点)//>各个子问题之间是相互独立的，不包含公共子问题。(动态规划)//晕了 搞了好久。。这样是不是占用空间太大了阿。。fak//时间复杂度：n(logn)static class MergerSort{static void printArr(String tag, int arr[], int f, int to){}static int[] merge(int arr1[],int arr2[]){int l1 = arr1.length;int l2 = arr2.length;int re[] = new int[l1 + l2];int o = 0;int t = 0;for(int i = 0; i < re.length; i++){if(o > l1 - 1){re[i] = arr2[t];t++;}else if(t > l2 - 1){re[i] = arr1[o];o++;}else if(arr1[o] < arr2[t]){re[i] = arr1[o];o++;}else{re[i] = arr2[t];t++;}}return re;}static int [] mSort(int []arr, int from, int to){int len = to - from + 1;if(len == 1){return new int[]{arr[from]};}int mid = (from + to) / 2;int[] l = mSort(arr, from, mid);int[] r = mSort(arr, mid+1, to);return merge(l, r);}}// 7.希尔static void shellSort(int arr[], int from, int to) {int len = to - from + 1;if (len == 1) {return;}int d = len % 2 == 0 ? len / 2 : len / 2 + 1;while (d >= 1) {//下面是一个典型插入排序for (int i = d; i < len; i++) {int tmp = arr[i];int j = -1;for (j = i - d; j >= 0; j -= d) {if (arr[j] > tmp) {arr[j + d] = arr[j];} else {break;// !!}}arr[j + d] = tmp;// 因为最后一位}d = d % 2 == 0 || d == 1 ? d / 2 : d / 2 + 1;}}//8.基数//基数排序很厉害哇//时间复杂度: 2 * n * (最大的数的位数)static class RadixSort{private static class list{LinkedList<Integer> l = new LinkedList<Integer>();LinkedList<Integer> getL(){return l;}public list(){}void add(int value){l.add(value);}void clear(){l.clear();}int size(){return l.size();}}private static class lists{private static list []l = new list[10];static void reset(){//重置所有的桶for(int i = 0; i < l.length; i++){if(l[i] != null && l[i].size()!=0){l[i].clear();}if(l[i] == null){l[i] = new list();}}}static list get(int index){//得到一个桶return l[index];}static void set(int index, int value){//往某个桶中添加数据l[index].add(value);}}static void rSort(int arr[], int from, int to){int len  = to - from + 1;if(len <= 1){return;}int times = 1;int currentTime = 0;int label = 1;while(currentTime < times){label = 10 * label;lists.reset();boolean timesMark = false;for(int i = 0; i < len; i++){//进桶int invalue = (arr[i]%label)/(label/10);//计算当前数放到哪个桶lists.set(invalue, arr[i]);if(!timesMark && arr[i]/label >= 1){//支持数值最大值为(9,9999,9999)否则。label超过Integer.MAX_VALUE会出错。times++;timesMark = true;}}int i = 0;for(int j = 0; j < 10; j++){for(Integer value: lists.get(j).getL()){arr[i] = value;i++;}}currentTime++;}}}public static void main(String[] args) {//测试int arr[] = {8, 91, 411, 2222, 33333, 744444, 6555555, 56666666,1010101010,1010101011, 15554444, 212112211,};//int arr[] = {81, 19, 44, 222, 323, 712, 56, 523, 15, 12,};System.out.println("Sorts.main() before");System.out.println(Arrays.toString(arr));//BubbleSort(arr, 0, arr.length - 1);//arr = insertSort(arr, 0, arr.length - 1);//arr = selectSort(arr, 0, arr.length - 1);//quickSort(arr, 0, arr.length - 1);
//		heapSort.hSort(arr, 0, arr.length-1);//arr = MergerSort.mSort(arr, 0, arr.length-1);//standInsertSort(arr, 0, arr.length-1);//selectSort(arr, 0, arr.length-1);
//		shellSort(arr, 0, arr.length-1);RadixSort.rSort(arr, 0, arr.length-1);System.out.println("Sorts.main() after");System.out.println(Arrays.toString(arr));int x[] = new int[8000000];for(int i = 0; i < x.length; i++){x[i] = (int)(Math.random()* (Integer.MAX_VALUE/100));}long currentTime = System.currentTimeMillis();System.out.println("Sorts.main() startTime = " + currentTime);//selectSort(x, 0, x.length - 1);//quickSort(x, 0, x.length - 1);//heapSort.hSort(x, 0, x.length - 1);
//		MergerSort.mSort(x, 0, x.length-1);
//		shellSort(x, 0, x.length-1);RadixSort.rSort(x, 0, x.length-1);//发现不如快速排序快。。估计是用了ArrayList的缘故。。System.out.println("Sorts.main() consumeTime = " + (System.currentTimeMillis() - currentTime));}
}