.


[img]http://dl.iteye.com/upload/picture/pic/89066/a8b30215-61e2-3c45-8778-97dff13bf6b9.jpg[/img]



package com.cdl.algorithem;

import java.util.Arrays;
import java.util.Random;

/**
* 参考：

* 1.http://www.iteye.com/topic/805043

* 2.视频：舞动的排序算法 快速排序 http://www.56.com/u61/v_NjczMjQ5Nzg.html

* 3.视频： 动画http://video.sina.com.cn/v/b/43015877-1731942570.html

*
* @author ocaicai@yeah.net
* @date: 2011-4-30
*/
public class QickSortTest {

public static void main(String[] args) {
int[] emptyArray = new int[10];// 定义一个数组
int[] targetArray = initArray(emptyArray);// 初始化数组
qickSort(targetArray, 0, targetArray.length - 1);// 排序数组
System.out.println("排序后的数组：" + Arrays.toString(targetArray));// 打印最后的数组

}

/** 初始化数组：使用随机数为数组赋值 */
private static int[] initArray(int[] array) {
Random random = new Random();
for (int i = 0; i < array.length; i++) {
array[i] = random.nextInt(100) - random.nextInt(100);
}
System.out.println("排序前的数组：" + Arrays.toString(array));
return array;
}

/** 交换两索引处的值 */
private static void swap(int[] array, int oneIndex,
int anotherIndex) {
int tempValue = array[oneIndex];
array[oneIndex] = array[anotherIndex];
array[anotherIndex] = tempValue;
}

/** 对某一次找出中轴的排序 */
private static int sortOnce(int[] array, int lowIndex, int highIndex) {

int pivotIndex = lowIndex;
int pivotValue = array[pivotIndex];

while (lowIndex < highIndex) {
while (lowIndex < highIndex && pivotValue <= array[highIndex]) {
highIndex--;
}
swap(array, pivotIndex, highIndex);
pivotIndex = highIndex;

while (lowIndex < highIndex && array[lowIndex] <= pivotValue) {
lowIndex++;
}
swap(array, lowIndex, pivotIndex);
pivotIndex = lowIndex;
}
return pivotIndex;
}

/**
* 递归进行排序

* 找出中轴后然后分治成两组,分别再次递归

* */
private static void qickSort(int[] array, int lowIndex, int highIndex) {
if (lowIndex < highIndex) {
int privotIndex = sortOnce(array, lowIndex, highIndex);
qickSort(array, lowIndex, privotIndex - 1);
qickSort(array, privotIndex + 1, highIndex);
}
}
}




[color=red]输出结果：[/color]



test1:

原数组：[-41, 21, -38, 71, -26, -12, -57, -25, 19, 50]
排序后的数组：[-57, -41, -38, -26, -25, -12, 19, 21, 50, 71]

test2:

原数组：[-10, 8, 7, 31, -49, 9, 30, -79, 64, 44]
排序后的数组：[-79, -49, -10, 7, 8, 9, 30, 31, 44, 64]

...




.