一、快速排序
核心：快排是一种采用分治思想的排序算法，大致分为三个步骤。
定基准——首先随机选择一个元素作为基准划分区——所有比基准小的元素置于基准左侧，比基准大的元素置于右侧递归调用——递归地调用此切分过程二、实现
实现方式一：
package sort; public class QuickSort { public static void main(String[] args) { int[] unsortedArray = new int[]{6, 5, 3, 1, 8, 7, 2, 4}; quickSort(unsortedArray); System.out.println("After sort: "); for (int item : unsortedArray) { System.out.print(item + " "); } } public static void quickSort2(int[] array, int l, int u) { for (int item : array) { System.out.print(item + " "); } System.out.println(); if (l >= u) return ; int pivot = array[l] ; // 定义一个基准，最左侧的值 int left = l + 1 ; int right = u ; while (left <= right) { // 左侧内循环自增 i, 直到遇到不小于基准元素的值为止。 while (left <= right && array[left] < pivot) { left++ ; } // 右侧内循环自减 j, 直到遇到小于基准元素的值为止。 while (left <= right && array[right] >= pivot) { right-- ; } if (left > right) break ; // swap array[left] with array[right] while left <= right int temp = array[left] ; array[left] = array[right] ; array[right] = temp ; } /* swap the smaller with pivot */ /** * （6,5,3,1,4,2,7,8） * 之后进行6和2的交换位置操作 * （2,5,3,1,4,6,7,8） * 重复进行以上操作 */ int temp = array[right] ; array[right] = array[l] ; array[l] = temp ; // System.out.println(l + " " + right + " " + u); // 0 5 7 quickSort2(array, l, right-1); quickSort2(array, right+1, u); } public static void quickSort(int[] array) { quickSort2(array, 0, array.length-1); } }实现方式二：
public class Sort { public static void main(String[] args) { int unsortedArray[] = new int[]{6, 5, 3, 1, 8, 7, 2, 4}; quickSort(unsortedArray); System.out.println("After sort: "); for (int item : unsortedArray) { System.out.print(item + " "); } } public static void quickSort1(int[] array, int l, int u) { for (int item : array) { System.out.print(item + " "); } System.out.println(); if (l >= u) return; int m = l; for (int i = l + 1; i <= u; i++) { if (array[i] < array[l]) { m += 1; int temp = array[m]; array[m] = array[i]; array[i] = temp; } } // swap between array[m] and array[l] // put pivot in the mid int temp = array[m]; array[m] = array[l]; array[l] = temp; quickSort1(array, l, m - 1); quickSort1(array, m + 1, u); } public static void quickSort(int[] array) { quickSort1(array, 0, array.length - 1); } }实现方式三：
package myTest; public class ArrayIns { private long[] theArray ; // def to array to theArray private int nElems ; // number of data items public ArrayIns(int max){ // constructor theArray = new long[max] ; // create the array nElems = 0 ; // no item yet } public void insert(long value){ // put element into array theArray[nElems] = value ; // insert it nElems++ ; // increment size } public void display(){ // display array contents System.out.print("A="); for (int i = 0; i < nElems; i++) { // for each element System.out.print(theArray[i] + " "); // display } System.out.println(""); } public void quickSort(){ recQuickSort(0, nElems-1); } public void recQuickSort(int left, int right){ if (right-left <= 0) { // if size<=1 return ; // already sorted } else{ long pivot = theArray[right] ; //rightmost item int partition = partitionIt(left,right,pivot) ; // partition range recQuickSort(left, partition-1); // sort left side recQuickSort(partition+1, right); // sort right side } } private int partitionIt(int left, int right, long pivot) { int leftPtr = left-1 ; // left (after ++) int rightPtr = right ; // right-1 (after--) while (true) { // find bigger item while (theArray[++leftPtr] < pivot) ; // find smaller item while (rightPtr > 0 && theArray[--rightPtr] > pivot) ; if (leftPtr >= rightPtr) { // if pointers cross break ; // partition done } else{ // not crossed so swap(leftPtr,rightPtr) ; // swap elements } } swap(leftPtr,right) ; // restore pivot return leftPtr ; // return pivot location } private void swap(int dex1, int dex2) { // swap two elements long temp = theArray[dex1] ; // A into temp theArray[dex1] = theArray[dex2] ; // B into A theArray[dex2] = temp ; // temp into B } }main函数：
package myTest; public class QuickSort1 { public static void main(String[] args) { int maxSize = 18 ; // array size ArrayIns arr ; arr = new ArrayIns(maxSize) ; // create array for (int i = 0; i < maxSize; i++) { // fill array with random numbers long n = (int)(java.lang.Math.random()*99) ; arr.insert(n); } arr.display(); arr.quickSort(); arr.display(); } }部分内容参考GitHub。
转载于:https://www.cnblogs.com/Wyao/p/7043711.html
相关资源：JAVA上百实例源码以及开源项目