Java实现数组与单链表快速排序
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36
public class { private static final int COUNT = 1000000 ; private static final int ZONE = 200 ; public static void main (String[] args) { Random rand = new Random(); Integer[] array = new Integer[COUNT]; for (int i=0 ;i<COUNT;i++){ array[i] = rand.nextInt(ZONE); } long startTime = System.currentTimeMillis(); quickSort(array,0 ,array.length-1 ); long endTime = System.currentTimeMillis(); float time = (endTime - startTime) / 1000F ; System.out.println(time); } private static void quickSort (Integer[] array,int left,int right) { if (left>=right) return ; int i = left; int j = right; int key = array[(i+j)/2 ]; while (i<j){ for (;i<j&&array[j]>=key;j--); array[i] = array[j]; for (;i<j&&array[i]<=key;i++); array[j] = array[i]; } array[i] = key; quickSort(array,left,i-1 ); quickSort(array,i+1 ,right); } }
单链表快速排序
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87
public class LinkedQuickSort { private static final int COUNT = 100000 ; private static final int ZONE = 200 ; public static void main (String[] args) { Random rand = new Random(); Node node = new Node(0 ); Node head = node; for (int i=0 ;i<COUNT;i++){ node.next = new Node(rand.nextInt(ZONE)); node = node.next; } long startTime = System.currentTimeMillis(); quickSort(head.next); long endTime = System.currentTimeMillis(); float time = (endTime - startTime) / 1000F ; System.out.println(time); for (head=head.next;head!=null ;head=head.next){ System.out.print(head.val+" " ); } } private static Node quickSort (Node head) { if (head == null || head.next == null ) return head; Node left = new Node(0 ); Node middle = new Node(0 ); Node right = new Node(0 ); Node leftHead = left; Node middleHead = middle; Node rightHead = right; int val = head.val; for (;head!=null ;head=head.next){ if (head.val<val){ left.next = head; left = left.next; }else if (head.val>val){ right.next = head; right = right.next; }else { middle.next = head; middle = middle.next; } } left.next = null ; middle.next = null ; right.next = null ; return merge(quickSort(leftHead.next),middleHead.next,quickSort(rightHead.next)); } private static Node merge (Node left, Node middle, Node right) { Node leftTail = findTail(left); Node middleTail = findTail(middle); middleTail.next = right; if (left!=null ){ leftTail.next = middle; return left; }else { return middle; } } private static Node findTail (Node node) { Node tail = node; if (tail != null ){ while (tail.next!=null ){ tail = tail.next; } } return tail; } } class Node { int val; Node next; public Node (int val) { this .val = val; } }
本文为作者kMacro 原创,转载请注明来源:https://zkhdev.github.io/2017/03/27/algorithm-fast-array-single-linked/
近期评论