思想:
以第一个为参照元素,分别从第二个和最后一个逐一和参照元素比较,小的留在左边low区域,大的留在右边high区域
第一个元素为中轴,i代表low区,j代表high区
i的值小于中轴,则不动,如遇到大于中轴,则换j开始比较
Paste_Image.pngj的值大于中轴则不动,如果小于中轴,则和i值进行换位
Paste_Image.png换位后
Paste_Image.png按照这个规则继续循环,直至j<i时,
Paste_Image.png Paste_Image.png Paste_Image.png在重新开始
Paste_Image.pngJava实现其思想
package sortingAlgo;
import java.util.Arrays;
import java.util.Random;
/**
* @author 水皮蛋
* 思想:以第一个为参照元素,分别从第二个和最后一个逐一和参照元素比较,小的留在左边low区域,大的留在右边high区域
* 特性:unstable sort、In-place sort。
* 最坏运行时间:当输入数组已排序时,时间为O(n^2),当然可以通过随机化来改进(shuffle array 或者 randomized
* select pivot),使得期望运行时间为O(nlgn)。
* 最佳运行时间:O(nlgn) 快速排序的思想也是分治法。
*
*/
public class QuickSort {
public static void main(String[] args) {
int[] arr = createRandomArray();
System.out.println(Arrays.toString(arr));
System.out.println(Arrays.toString(quickSort(arr, 0, arr.length - 1)));
}
public static int[] quickSort(int[] arr, int low, int high) {
if (low < high) {
int privotLoc = partition(arr, low, high); // 将表一分为二
quickSort(arr, low, privotLoc - 1); // 递归对低子表递归排序
quickSort(arr, privotLoc + 1, high); // 递归对高子表递归排序
}
return arr;
}
static int partition(int[] arr, int low, int high) {
// 参照元素,我们可以叫中轴,一般多为第一个或者最后一个
int privotKey = arr[low];
// 从表的两端交替地向中间扫描
while (low < high) {
while (low < high && arr[high] >= privotKey) {
high--;
}
// 比中轴小移到低端
arr[low] = arr[high];
while (low < high && arr[low] <= privotKey) {
low++;
}
// 比中轴大移到高端
arr[high] = arr[low];
}
// 中轴移至尾端
arr[low] = privotKey;
return low;
}
/**
* 使用Random类产生随机数组的对象
*
* @return 随机数组
*/
public static int[] createRandomArray() {
Random random = new Random();
int[] array = new int[10];
for (int i = 0; i < 10; i++) {
array[i] = random.nextInt(100);
}
return array;
}
}
网友评论