快速排序示例代码(JAVA版)

package me.yangsuosuo.java.quicksort; /** * 快速排序：分别实现了小到大和从大到小排序的算法 * * @author Lock * @date 2016年3月24日下午5:51:55 */ public class QuickSort { /** * 将无序序列sequence位于s和t之间的元素按照从小到大的顺序排序 * * @param sequence * 待排序列 * @param s * 序列的起点 * @param t * 序列的终点 */ public static void quickSort_ASC(int[] sequence, int s, int t) { int pivotloc = s; // 枢轴的位置 // 当t>s时，才有必要进行排序 if (t > s) { // 将待排序列划分成两个子序列:[s, pivotloc - 1]和[pivotloc + 1, t] pivotloc = partition_ASC(sequence, s, t); // 分别对两个子序列进行快速排序 quickSort_ASC(sequence, s, pivotloc - 1); quickSort_ASC(sequence, pivotloc + 1, t); } } /** * 将给定的序列sequence中位于low和high之间的元素划分成两个子序列，并返回枢轴所在的位置 * * @param sequence * 待划分的序列 * @param low * 参与划分的元素的下界 * @param high * 参与划分的元素的上界 * @return int 本次划分后枢轴所在的位置 */ private static int partition_ASC(int[] sequence, int low, int high) { int piovt = sequence[low]; // 枢轴 while (low < high) { // 从high位置开始向左逐个扫描，直到遇到第一个比枢轴小的元素就停止 // 然后将这个元素放到low对应的位置上 while (low < high && sequence[high] >= piovt) { high--; } sequence[low] = sequence[high]; // 接着 // 从low位置开始向右逐个扫描，直到遇到第一个比枢轴大的元素就停止 // 然后将这个元素放到high对应的位置上 while (low < high && sequence[low] <= piovt) { low++; } sequence[high] = sequence[low]; } // 直到low==high时，上面的while循环才会结束 // 此时，low==high，即为枢轴的位置 sequence[low] = piovt; // 将枢轴的值存放到它的位置上 return low; // 返回枢轴的位置 } /** * 将无序序列sequence位于s和t之间的元素按照从大到小的顺序排序 * * @param sequence * 待排序列 * @param s * 序列的起点 * @param t * 序列的终点 */ public static void quickSort_DESC(int[] sequence, int s, int t) { int pivotloc = s; // 枢轴的位置 // 当t>s时，才有必要进行排序 if (t > s) { // 将待排序列划分成两个子序列:[s, pivotloc - 1]和[pivotloc + 1, t] pivotloc = partition_DESC(sequence, s, t); // 分别对两个子序列进行快速排序 quickSort_DESC(sequence, s, pivotloc - 1); quickSort_DESC(sequence, pivotloc + 1, t); } } /** * 将给定的序列sequence中位于low和high之间的元素划分成两个子序列，并返回枢轴所在的位置 * * @param sequence * 待划分的序列 * @param low * 参与划分的元素的下界 * @param high * 参与划分的元素的上界 * @return int 本次划分后枢轴所在的位置 */ private static int partition_DESC(int[] sequence, int low, int high) { int piovt = sequence[low]; // 枢轴 while (low < high) { // 从high位置开始向左逐个扫描，直到遇到第一个比枢轴小的元素就停止 // 然后将这个元素放到low对应的位置上 while (low < high && sequence[high] <= piovt) { high--; } sequence[low] = sequence[high]; // 接着 // 从low位置开始向右逐个扫描，直到遇到第一个比枢轴大的元素就停止 // 然后将这个元素放到high对应的位置上 while (low < high && sequence[low] >= piovt) { low++; } sequence[high] = sequence[low]; } // 直到low==high时，上面的while循环才会结束 // 此时，low==high，即为枢轴的位置 sequence[low] = piovt; // 将枢轴的值存放到它的位置上 return low; // 返回枢轴的位置 } }