为算法考试做准备--快速排序以及找第K大数的实现
发布时间:2020-12-14 02:22:50 所属栏目:大数据 来源:网络整理
导读:package utils;import java.util.Random;class ArrayInts{private int[] theArray;private int nElems;public ArrayInts(int maxSize) {theArray = new int[maxSize];nElems = 0;}public void insert(int value) {theArray[nElems] = value;nElems++;}public
package utils; import java.util.Random; class ArrayInts{ private int[] theArray; private int nElems; public ArrayInts(int maxSize) { theArray = new int[maxSize]; nElems = 0; } public void insert(int value) { theArray[nElems] = value; nElems++; } public void quickSort() { recQuickSort(0,nElems - 1); } public void recQuickSort(int left,int right) { if (right - left <= 0) { return; } int pivot = theArray[right]; int partition = partitionIt(left,right,pivot); recQuickSort(left,partition - 1); recQuickSort(partition + 1,right); } public int partitionIt(int left,int right,int pivot) { int leftPtr = left - 1; int rightPtr = right; while (true) { while (theArray[++leftPtr] < pivot) ; while (rightPtr > 0 && theArray[--rightPtr] > pivot) ; if (leftPtr >= rightPtr) break; else swap(leftPtr,rightPtr); } swap(leftPtr,right); return leftPtr; } public void swap(int i1,int i2) { int temp = theArray[i1]; theArray[i1] = theArray[i2]; theArray[i2] = temp; } public int findKth(int left,int k) { if (right == left) return theArray[left]; int pivot = theArray[right]; int partition = partitionIt(left,pivot); int i = partition - left; if (i == k) return theArray[k]; else if (i < k) return findKth(partition + 1,k - i); else return findKth(left,partition - 1,k); } public void display() { for (int j = 0; j < nElems; ++j) System.out.print(theArray[j] + " "); System.out.println(); } } public class MyQuickSort { public static void main(String[] args) { ArrayInts ints = new ArrayInts(20); Random rand = new Random(47); for (int i = 0; i < 20; ++i) { ints.insert(rand.nextInt(100) + 1); } System.out.println("find 0th: " + ints.findKth(0,19,0)); System.out.println("find 19th: " + ints.findKth(0,19)); System.out.println("find 9th: " + ints.findKth(0,9)); System.out.println("find 13th: " + ints.findKth(0,14)); ints.quickSort(); ints.display(); } } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |