会python真的可以为所欲为0(回)
359天前
这里还有人吗1(回)
544天前这里还有人吗0(回)
544天前
每天面对着电脑屏幕，敲打键盘。我所面对的并不只是代码，而是一种生活方式。0(回)
769天前到处都是羊，不想上班0(回)
849天前
鸽子
0(回)
853天前/** |
* 快速排序 |
* |
* 在当前无序区R[1..H]中任取一个数据元素作为比较的"基准"(不妨记为X)，用此基准将当前无序区划分为左右两个较小的无序区： |
* R[1..I-1]和R[I+1..H]，且左边的无序子区中数据元素均小于等于基准元素，右边的无序子区中数据元素均大于等于基准元素， |
* 而基准X则位于最终排序的位置上，即R[1..I-1]≤ X.Key≤R[I+1..H](1≤I≤H)，当R[1..I-1]和R[I+1..H]均非空时， |
* 分别对它们进行上述的划分过程，直至所有无序子区中的数据元素均已排序为止。 |
*/ |
public class QuickSort { |
/** |
* 排序算法的实现，对数组中指定的元素进行排序 |
* |
* @param array |
* 待排序的数组 |
* @param from |
* 从哪里开始排序 |
* @param end |
* 排到哪里 |
* @param c |
* 比较器 |
*/ |
// 定义了一个这样的公有方法sort，在这个方法体里面执行私有方法quckSort（这种方式值得借鉴）。 |
public void sort(Integer[] array, int from, int end) { |
quickSort(array, from, end); |
} |
/** |
* 递归快速排序实现 |
* |
* @param array |
* 待排序数组 |
* @param low |
* 低指针 |
* @param high |
* 高指针 |
* @param c |
* 比较器 |
*/ |
private void quickSort(Integer[] array, int low, int high) { |
/* |
* 如果分区中的低指针小于高指针时循环；如果low=higth说明数组只有一个元素，无需再处理； 如果low > |
* higth，则说明上次枢纽元素的位置pivot就是low或者是higth，此种情况 下分区不存，也不需处理 |
*/ |
if (low < high) { |
// 对分区进行排序整理 |
// int pivot = partition1(array, low, high); |
int pivot = partition2(array, low, high); |
// int pivot = partition3(array, low, high); |
/* |
* 以pivot为边界，把数组分成三部分[low, pivot - 1]、[pivot]、[pivot + 1, high] |
* 其中[pivot]为枢纽元素，不需处理，再对[low, pivot - 1]与[pivot + 1, high] |
* 各自进行分区排序整理与进一步分区 |
*/ |
quickSort(array, low, pivot - 1); |
quickSort(array, pivot + 1, high); |
} |
} |
/** |
* 实现一 |
* |
* @param array |
* 待排序数组 |
* @param low |
* 低指针 |
* @param high |
* 高指针 |
* @param c |
* 比较器 |
* @return int 调整后中枢位置 |
*/ |
private int partition1(Integer[] array, int low, int high) { |
Integer pivotElem = array[low];// 以第一个元素为中枢元素 |
// 从前向后依次指向比中枢元素小的元素，刚开始时指向中枢，也是小于与大小中枢的元素的分界点 |
int border = low; |
/* |
* 在中枢元素后面的元素中查找小于中枢元素的所有元素，并依次从第二个位置从前往后存放 |
* 注，这里最好使用i来移动，如果直接移动low的话，最后不知道数组的边界了，但后面需要 知道数组的边界 |
*/ |
for (int i = low + 1; i <= high; i++) { |
// 如果找到一个比中枢元素小的元素 |
if ((array[i].compareTo(pivotElem)) < 0) { |
swap(array, ++border, i);// border前移，表示有小于中枢元素的元素 |
} |
} |
/* |
* 如果border没有移动时说明说明后面的元素都比中枢元素要大，border与low相等，此时是 |
* 同一位置交换，是否交换都没关系；当border移到了high时说明所有元素都小于中枢元素，此 |
* 时将中枢元素与最后一个元素交换即可，即low与high进行交换，大的中枢元素移到了 序列最 后；如果 low <minIndex< |
* high，表 明中枢后面的元素前部分小于中枢元素，而后部分大于 |
* 中枢元素，此时中枢元素与前部分数组中最后一个小于它的元素交换位置，使得中枢元素放置在 正确的位置 |
*/ |
swap(array, border, low); |
return border; |
} |
/** |
* 实现二 |
* |
* @param array |
* 待排序数组 |
* @param low |
* 待排序区低指针 |
* @param high |
* 待排序区高指针 |
* @param c |
* 比较器 |
* @return int 调整后中枢位置 |
*/ |
private int partition2(Integer[] array, int low, int high) { |
int pivot = low;// 中枢元素位置，我们以第一个元素为中枢元素 |
// 退出条件这里只可能是 low = high |
while (true) { |
if (pivot != high) {// 如果中枢元素在低指针位置时，我们移动高指针 |
// 如果高指针元素小于中枢元素时，则与中枢元素交换 |
if ((array[high].compareTo(array[pivot])) < 0) { |
swap(array, high, pivot); |
// 交换后中枢元素在高指针位置了 |
pivot = high; |
} else {// 如果未找到小于中枢元素，则高指针前移继续找 |
high--; |
} |
} else {// 否则中枢元素在高指针位置 |
// 如果低指针元素大于中枢元素时，则与中枢元素交换 |
if ((array[low].compareTo(array[pivot])) > 0) { |
swap(array, low, pivot); |
// 交换后中枢元素在低指针位置了 |
pivot = low; |
} else {// 如果未找到大于中枢元素，则低指针后移继续找 |
low++; |
} |
} |
if (low == high) { |
break; |
} |
} |
// 返回中枢元素所在位置，以便下次分区 |
return pivot; |
} |
/** |
* 实现三 |
* |
* @param array |
* 待排序数组 |
* @param low |
* 待排序区低指针 |
* @param high |
* 待排序区高指针 |
* @param c |
* 比较器 |
* @return int 调整后中枢位置 |
*/ |
private int partition3(Integer[] array, int low, int high) { |
int pivot = low;// 中枢元素位置，我们以第一个元素为中枢元素 |
low++; |
// ----调整高低指针所指向的元素顺序，把小于中枢元素的移到前部分，大于中枢元素的移到后面部分 |
// 退出条件这里只可能是 low = high |
while (true) { |
// 如果高指针未超出低指针 |
while (low < high) { |
// 如果低指针指向的元素大于或等于中枢元素时表示找到了，退出，注：等于时也要后移 |
if ((array[low].compareTo(array[pivot])) >= 0) { |
break; |
} else {// 如果低指针指向的元素小于中枢元素时继续找 |
low++; |
} |
} |
while (high > low) { |
// 如果高指针指向的元素小于中枢元素时表示找到，退出 |
if ((array[high].compareTo(array[pivot])) < 0) { |
break; |
} else {// 如果高指针指向的元素大于中枢元素时继续找 |
high--; |
} |
} |
// 退出上面循环时 low = high |
if (low == high) { |
break; |
} |
swap(array, low, high); |
} |
// ----高低指针所指向的元素排序完成后，还得要把中枢元素放到适当的位置 |
if ((array[pivot].compareTo(array[low])) > 0) { |
// 如果退出循环时中枢元素大于了低指针或高指针元素时，中枢元素需与low元素交换 |
swap(array, low, pivot); |
pivot = low; |
} else if ((array[pivot].compareTo(array[low])) <= 0) { |
swap(array, low - 1, pivot); |
pivot = low - 1; |
} |
// 返回中枢元素所在位置，以便下次分区 |
return pivot; |
} |
/** |
* 交换数组中的两个元素的位置 |
* |
* @param array |
* 待交换的数组 |
* @param i |
* 第一个元素 |
* @param j |
* 第二个元素 |
*/ |
public void swap(Integer[] array, int i, int j) { |
if (i != j) {// 只有不是同一位置时才需交换 |
Integer tmp = array[i]; |
array[i] = array[j]; |
array[j] = tmp; |
} |
} |
/** |
* 测试 |
* |
* @param args |
*/ |
public static void main(String[] args) { |
Integer[] intgArr = { 5, 9, 1, 4, 2, 6, 3, 8, 0, 7 }; |
QuickSort quicksort = new QuickSort(); |
quicksort.sort(intgArr, 0, intgArr.length - 1); |
for (Integer intObj : intgArr) { |
System.out.print(intObj + " "); |
} |
} |
} |
