快速排序是对冒泡排序的改进，原理是选择一个基准元素，通过一次排序将要排序的元素分割成独立的两部分，一部分全部小于或等于基准元素，另一部分全部大于或等于基准元素，然后再按照此思路重复对这两部分进行排序。
复杂度分析
- 最坏情况下时间复杂度：
O(n²) - 平均时间复杂度：
O(nlogn)
Java 代码实现
1. 迭代实现一
import java.util.Arrays;
public class QuickSort {
public static void sort(int[] data, int startIndex, int endIndex) {
if (startIndex < endIndex) {
int pivotIndex = getPivotIndex(data, startIndex, endIndex);
sort(data, startIndex, pivotIndex - 1);
sort(data, pivotIndex + 1, endIndex);
}
}
private static int getPivotIndex(int[] data, int startIndex, int endIndex) {
// 将起始位置元素作为基准元素
int pivot = data[startIndex];
int left = startIndex;
int right = endIndex;
int index = startIndex;
while (left < right) {
while (right > left) {
if (data[right] < pivot) {
data[left] = data[right];
index = right;
left++;
break;
}
right--;
}
while (left < right) {
if (data[left] > pivot) {
data[right] = data[left];
index = left;
right--;
break;
}
left++;
}
}
data[index] = pivot;
return index;
}
public static void main(String[] args) {
int[] data = {34, 24, 93, 1, 32, 98, 18, 39};
sort(data, 0, data.length - 1);
System.out.println(Arrays.toString(data));
}
}
说明
(1) 选定基准元素pivot，记住Pivot位置index，设置两个指针指向数列的最左left和最右right两个元素，如：
pivot=34 : 34(index/left), 24, 93, 1, 32, 98, 18, 39(right)
(2) 从最右right开始，将指向元素与基准元素pivot对比，如果比pivot大则right向左移，直至找到比pivot小的元素，将此元素填入位置index，right变成了新的index，left也向右移了一位。
pivot=34 : 34(index/left), 24, 93, 1, 32, 98, 18(right), 39
pivot=34 : 18, 24(left), 93, 1, 32, 98, 18(right/index), 39
(3) 从left开始，将指向元素与基准元素pivot对比，如果比pivot小则left向右移，直至找到比pivot大的元素，将此元素填入位置index，left变成了新的index，right也向左移了一位。
pivot=34 : 18, 24, 93(left), 1, 32, 98, 18(right/index), 39
pivot=34 : 18, 24, 93(left/index), 1, 32, 98(right), 93, 39
(4) 按照之前的思路重复下去，直至left和right重合在同一个位置。
pivot=34 : 18, 24, 93(left/index), 1, 32(right), 98, 93, 39
pivot=34 : 18, 24, 32, 1(left), 32(right/index), 98, 93, 39
pivot=34 : 18, 24, 32, 1, 32(left/right/index), 98, 93, 39
(5) 将pivot元素放到index位置，本轮结束。
18, 24, 32, 1, 34, 98, 93, 39
(6) 然后针对18, 24, 32, 1和98, 93, 39两个序列再次按如上方法重复排序。
2. 迭代实现二
import java.util.Arrays;
public class QuickSort {
public static void sort(int[] data, int startIndex, int endIndex) {
if (startIndex < endIndex) {
int pivotIndex = getPivotIndex(data, startIndex, endIndex);
sort(data, startIndex, pivotIndex - 1);
sort(data, pivotIndex + 1, endIndex);
}
}
private static int getPivotIndex(int[] data, int startIndex, int endIndex) {
// 将起始位置元素作为基准元素
int pivot = data[startIndex];
int left = startIndex;
int right = endIndex;
while (left < right) {
while (right > left && data[right] >= pivot) {
right--;
}
while (left < right && data[left] <= pivot) {
left++;
}
swap(data, left, right);
}
swap(data, left, startIndex);
return left;
}
private static void swap(int[] data, int i, int j) {
int temp = data[i];
data[i] = data[j];
data[j] = temp;
}
public static void main(String[] args) {
int[] data = {34, 24, 93, 1, 32, 98, 18, 39};
sort(data, 0, data.length - 1);
System.out.println(Arrays.toString(data));
}
}
说明
(1) 选定基准元素pivot，设置两个指针指向数列的最左left和最右right两个元素，如：
pivot=34 : 34(left), 24, 93, 1, 32, 98, 18, 39(right)
(2) 从最右right开始，将指向元素与基准元素pivot对比，如果大于等于pivot则right左移，直至移动至小于pivot的位置，切换到left指针。
pivot=34 : 34(left), 24, 93, 1, 32, 98, 18(right), 39
(3) 切换到left开始，将指向元素与基准元素pivot对比，如果小于等于pivot则left右移，直至移动至大于pivot的位置。
pivot=34 : 34, 24, 93(left), 1, 32, 98, 18(right), 39
(4) 将left和right位置的元素进行互换。
pivot=34 : 34, 24, 18(left), 1, 32, 98, 93(right), 39
(5) 再次切换到right开始重复以上步骤，直至left和right位置重合。
pivot=34 : 34, 24, 18(left), 1, 32(right), 98, 93, 39
pivot=34 : 34, 24, 18, 1, 32(left/right), 98, 93, 39
(6) 将pivot和left、right重合位置元素进行互换。
32, 24, 18, 1, 34, 98, 93, 39
(7) 然后针对18, 24, 32, 1和98, 93, 39两个序列再次按如上方法重复排序。
3. 非迭代实现
栈实现
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.Stack;
public class QuickSort {
public static void sort(int[] data, int startIndex, int endIndex) {
if (startIndex < endIndex) {
// 用集合栈代替递归函数栈
Stack<Map<String, Integer>> stack = new Stack<>();
// 将数列的起止下标以哈希形式入栈
Map<String, Integer> rootParam = new HashMap<>();
rootParam.put("startIndex", startIndex);
rootParam.put("endIndex", endIndex);
stack.push(rootParam);
while (!stack.isEmpty()) {
Map<String, Integer> param = stack.pop();
int pivotIndex = getPivotIndex(data, param.get("startIndex"), param.get("endIndex"));
if (param.get("startIndex") < pivotIndex - 1) {
Map<String, Integer> leftParam = new HashMap<>();
leftParam.put("startIndex", param.get("startIndex"));
leftParam.put("endIndex", pivotIndex - 1);
stack.push(leftParam);
}
if (pivotIndex + 1 < param.get("endIndex")) {
Map<String, Integer> rightParam = new HashMap<>();
rightParam.put("startIndex", pivotIndex + 1);
rightParam.put("endIndex", param.get("endIndex"));
stack.push(rightParam);
}
}
}
}
private static int getPivotIndex(int[] data, int startIndex, int endIndex) {
// 将起始位置元素作为基准元素
int pivot = data[startIndex];
int left = startIndex;
int right = endIndex;
while (left < right) {
while (right > left && data[right] >= pivot) {
right--;
}
while (left < right && data[left] <= pivot) {
left++;
}
swap(data, left, right);
}
swap(data, left, startIndex);
return left;
}
private static void swap(int[] data, int i, int j) {
int temp = data[i];
data[i] = data[j];
data[j] = temp;
}
public static void main(String[] args) {
int[] data = {34, 24, 93, 1, 32, 98, 18, 39};
sort(data, 0, data.length - 1);
System.out.println(Arrays.toString(data));
}
}
网友评论