快速排序Java实现
* 快速排序
* @author admin
*
*/
public class QuickSort {
public static void quickSort(int[] array) {
recQuickSort(array, 0, array.length - 1);
for (int x : array) {
System.out.print(x + " ");
}
}
public static void recQuickSort(int[] array, int lower, int upper) {
if (lower > upper)
return;
// 返回子数组基数的下标
int pivotIndex = partition(array, lower, upper);
recQuickSort(array, lower, pivotIndex - 1);
recQuickSort(array, pivotIndex + 1, upper);
}
// 划分数组
public static int partition(int[] array, int lower, int upper) {
int pivot = array[lower]; // 选取数组第一个元素作为基数
int left = lower; // 左指针
int right = upper; // 右指针
while (left < right) {
// 指针从数组右边开始移动, 寻找到小于基数的元素停止, 要保证左指针下标小于右指针
while (left < right && array[right] >= pivot)
right--;
// 左指针开始移动, 寻找到大于基数的元素停止, 要保证左指针下标小于右指针
while (left < right && array[left] <= pivot)
left++;
// 左右指针停止移动后, 交换它们各自指向的元素
int temp = array[right];
array[right] = array[left];
array[left] = temp;
}
// 左右指针相遇, 把基数元素也就是开始的array[lower]与左右指针共同指向的元素array[right]或array[left]交换位置
// 此时基数左边的元素都小于它右边的元素都大于它
array[lower] = array[right];
array[right] = pivot;
return right;
}
public static void main(String[] args) {
int[] array = { 6, 3, 7, 2, 5, 1, 3, 9 };
System.out.println("排序开始");
long s = System.currentTimeMillis();
quickSort(array);
long e = System.currentTimeMillis();
System.out.println("\n排序结束用时"+(e-s)+"ms");
}
}
