一、快速排序思路
1.快速排序采用分而治之的思想,将问题拆分为更小规模进行递归调用,从而求解大规模问题。即选取一个数组中的一个key(一般选择左边或右边)key,当拆分一次后(low >= right),产生一个标志flag,将数组拆分为 [low,flag-1]和[flag+1,right]。
2.例如:
6 3 9 2 6 2 7 2 8
(1)选取左边 key = 6
(2)将比标志位小的数放到左边,比标志位大的数放到右边
*一次调用*
6 3 9 2 6 2 7 2 8
i j
i j
6 3 2 2 6 2 7 9 8
i j
i(j)
flag = i;
3.快速排序图
二、代码实现
package com.daxiong.day3;
public class QuickSort {
public static void main(String[] args) {
QuickSort qs = new QuickSort();
int data[] = { 44, 22, 2, 32, 54, 22, 88, 77, 99, 11 };
// int[] data = { 3, 2, 3, 4, 0 };
qs.quickSort(data, 0, data.length - 1);
for (int i = 0; i < data.length; i++) {
System.out.print(data[i]);
System.out.print(" ");
}
}
// 快速排序递归调用
public void quickSort(int[] data, int low, int hight) {
if (low < hight) {
int result = partition(data, low, hight); // 拆分获取标志索引
quickSort(data, low, result - 1); // 将问题拆分 low -- result-1,递归调用
quickSort(data, result + 1, hight); // 将问题拆分 result+1 -- right,递归调用
}
}
// 快速排序拆分
private int partition(int data[], int low, int hight) {
int key = data[low];
while (low < hight) {
while (low < hight && data[hight] >= key) // 当右边的值小于标志时停止
hight--;
data[low] = data[hight]; // 将右边值给到左边
while (low < hight && data[low] <= key) // 当左边的值大于标志时停止
low++;
data[hight] = data[low]; // 将左边值给到右边
}
data[low] = key; // 将标志给到左边
return low;
}
}
cs