java 实现快速排序

原理

快速排序利用了分治思想。

首先在数组中选择一个基准数 pivot，然后在数组的首尾分别设置 left，right 指针；

从右向左开始扫描，如果扫描到的数大于或者等于 pivot 并且右指针大于左指针 ，right 就左移一位，否则就停止扫描；

然后从左向右开始扫描，如果扫描到的数小于或者等于 pivot 并且指针大于左指针，left 就右移一位，否则就停止扫描；

两边都扫描完成后，如果 left 小于 right 就将 left 和 right 指向的元素交换，然后继续循环，直到 left 等于 right 为止；

最后循环结束将 pivot 与 left 和 right 指向的元素交换，这样第一轮循环就结束了，时间复杂度为 O(n)。

一般情况下需要循环log(n)轮，所以总的时间复杂度为 O(nlogn)。

快速排序之递归方式实现 public class QuickSort { public void sort(int[] array, int leftIndex, int rightIndex) { if(leftIndex>=rightIndex){ return; } int pivotIndex = partition(array, leftIndex, rightIndex); sort(array,leftIndex,pivotIndex-1); sort(array,pivotIndex+1,rightIndex); } public int partition(int[] array, int leftIndex, int rightIndex) { //获取基准元素int pivotIndex = leftIndex; int pivot = array[pivotIndex]; while (leftIndex != rightIndex) { while (rightIndex > leftIndex && array[rightIndex] >= pivot) { rightIndex--; } while (leftIndex < rightIndex && array[leftIndex] <= pivot) { leftIndex++; } if(leftIndex<rightIndex){ int temp = 0; temp = array[rightIndex]; array[rightIndex] = array[leftIndex]; array[leftIndex] = temp; } } array[pivotIndex] = array[rightIndex]; array[rightIndex] = pivot; return rightIndex; } }

测试：

public static void main(String[] args) { int[] array = new int[10000]; Random random = new Random(); for (int i = 0; i < 10000; i++) { array[i] = random.nextInt(10000); } //计时开始 long start = System.currentTimeMillis(); QuickSort quickSort = new QuickSort(); quickSort.sort(array,0,array.length-1); //计时结束 long end = System.currentTimeMillis(); System.out.println("共耗时" + (end - start) + "毫秒"); System.out.print(Arrays.toString(array)); }

10000个随机数排序耗时：

快速排序之非递归方式实现

递归方式实现过程就是一层层的进入方法，在一层层的返回结果，和栈的特性一摸一样，先进后出，所以完全可以用栈来代替递归实现。

public class QuickSortByStack { public void sort(int[] array, int leftIndex, int rightIndex) { Stack<Map<String, Integer>> stack = new Stack<Map<String, Integer>>(); Map<String, Integer> map = new HashMap<String, Integer>(); map.put("leftIndex", leftIndex); map.put("rightIndex", rightIndex); stack.push(map); while (!stack.empty()) { Map<String, Integer> param = stack.pop(); int pivotIndex = partition(array, param.get("leftIndex"), param.get("rightIndex")); if (pivotIndex-1 > param.get("leftIndex")) { Map<String, Integer> leftMap = new HashMap<String, Integer>(); leftMap.put("leftIndex", param.get("leftIndex")); leftMap.put("rightIndex", pivotIndex-1); stack.push(leftMap); } if ( param.get("rightIndex")-1>pivotIndex){ Map<String, Integer> rightMap = new HashMap<String, Integer>(); rightMap.put("leftIndex", pivotIndex+1); rightMap.put("rightIndex",param.get("rightIndex")); stack.push(rightMap); } } } public int partition(int[] array, int leftIndex, int rightIndex) { //获取基准元素 int pivotIndex = leftIndex; int pivot = array[pivotIndex]; while (leftIndex != rightIndex) { while (rightIndex > leftIndex && array[rightIndex] >= pivot) { rightIndex--; } while (leftIndex < rightIndex && array[leftIndex] <= pivot) { leftIndex++; } if (leftIndex < rightIndex) { int temp = 0; temp = array[rightIndex]; array[rightIndex] = array[leftIndex]; array[leftIndex] = temp; } } array[pivotIndex] = array[rightIndex]; array[rightIndex] = pivot; return rightIndex; } }

个人博客：java 实现快速排序