// ori[start,end] private static void mergeSort(int[] ori, int start, int end) { if (start == end) { return; } int m = (start+end)/2; mergeSort(ori,start,m); mergeSort(ori,m+1,end); merge(ori,start,end,m+1); } private static void merge(int [] ori,int start,int end,int middle) { int [] l = new int [middle - start]; int [] r = new int [end - middle +1]; System.arraycopy(ori, start, l, 0, middle - start); System.arraycopy(ori, middle, r, 0, end - middle +1); int i = 0,j = 0,k = start; while (k < end && (i <(middle - start)) && (j<end-middle+1)) { if (l[i] < r [j]) { ori[k] = l[i]; i++; }else { ori[k] = r[j]; j++; } k++; } while (i <(middle - start)) { ori[k++] = l [i++]; } while (j<(end-middle+1)) { ori[k++] = r[j++]; } }
快速排序:
public static void sort(int a[]) { sort0(a,0,a.length-1); } private static void sort0(int a[],int start,int end) { if (start >= end) { return; } int key = a[start]; int i= start,j = start+1; while (j<=end) { if (a[j] <= key) { i++; swap(a,i,j); } j++; } //swap a[i] and key swap(a,i,start); sort0(a,start,i-1); sort0(a,i+1,end); } private static void swap(int []a,int i,int j) { int t = a[i]; a[i]=a[j]; a[j]=t; }
排序步骤:
【1】找到中轴的位置,从start开始,将比a[start]小的扔到一边,比他大的不管。(扔到另一边) 需要2个index 标志 已经执行到的index和 下一个可替换的index。
【2】【1】执行完后,所有比a[start]小的在a[index1]前面。比大的在后面,然后swap(a,start,index) 将中轴放到正确的位置。
【3】此时中轴已经在正确的位置,然后分别对左右执行【1】、、、
快排的随机化版本:
private static void randomsort(int a[],int start,int end) { if (start >= end) { return; } int keyIndex = r.nextInt(end-start + 1) + start; int key = a[keyIndex]; //swap to ensure the first element is not need to compare swap(a,start,keyIndex); int i=start,j=start+1; while (j<=end) { if (a[j]<=key) { swap(a,++i,j); } j++; } swap(a,i,start); randomsort(a,start,i-1); randomsort(a,i+1,end); }
堆排序:
public static void sort(int a[]) { // build-max-heap buildmaxheap(a); // from n->1 for (int i = a.length - 1; i > 0; i--) { P.swap(a, 0, i); keepmaxheap(a, 0, i - 1); } } private static void buildmaxheap(int a[]) { int heapsize = a.length; for (int i = heapsize / 2 - 1; i >= 0; i--) { keepmaxheap(a, i, heapsize-1); } } // build a heap of a[i~ maxindex] private static void keepmaxheap(int a[], int i, int maxindex) { int l = (i << 1) + 1; int r = (i + 1) << 1; int largest = i; if (l <= maxindex) { largest = a[l] > a[i] ? l : i; } if (r <= maxindex) { largest = a[r] > a[largest] ? r : largest; } if (largest != i) { P.swap(a, largest, i); keepmaxheap(a, largest, maxindex); } }
排序步骤:
【1】构造一个最大堆。 如何构造? -》 从第一个有叶子的子树开始,从后往前,按照最大堆性质执行: 大的元素总是在根。-》大根堆。
【2】从最后一个元素开始,先swap 根 和最后一元素,然后 “剔除”最后一个元素,执行保持最大堆的必要操作。keepmaxheap (a,0,maxindex);
【3】在第【2】部中最后一个元素已经在正确的位置。
二叉树(非平衡)
package sort; /** * max time O(n^2) * @author Administrator * */ public class BinTreeSort { public static void sort(int a[]) { //just insert into tree Node root = new Node(a[0]); for (int i=1;i<a.length; i++) { insertTree(a[i],root); } //then left->root->right traverse traverse(root); } public static void traverse(Node root) { if (root==null) { return; } traverse(root.left); System.out.print(root.value + " "); traverse(root.right); } public static void insertTree(int value,Node root) { Node cur = root; Node lastNode = null; boolean useleft = true; while (cur!=null) { lastNode = cur; if (cur.value >= value) { cur = cur.left; useleft = true; } else { cur = cur.right; useleft= false; } } if (useleft) { lastNode.left = new Node(value); }else { lastNode.right = new Node(value); } } } class Node { Node left,right; int value; public Node(int a) { this.value=a; } }