Open
Description
算法名称
快速排序
实现思路
将数组的第一个数字作为基准，最后使得基准数字位于数组中间某个位置，它的左边的数字都比它小，它的右边的数字都比它大。
细节：设置两个分别指向数组头部和尾部的指针i和j，首先向左移动j，使得array[j] 小于基准。然后向右移动i，使得array[i] 大于基准，交换这两个元素。当i 和j 的值相等时，交换基准与位置i上的元素，然后对i左边以及右边的元素分别进行快速排序。
具体实现
Javascript实现
function quickSort(left, right, array) {
var temp = array[left];
if (left > right) return;
var i = left;
var j = right;
while (i < j) {
while (array[j] >= temp && j > i) {
j--;
}
while (array[i] <= temp && i < j) {
i++;
}
var current = array[i];
array[i] = array[j];
array[j] = current;
}
array[left] = array[i];
array[i] = temp;
quickSort(left, i - 1, array);
quickSort(j + 1, right, array);
}
var array = [6, 2, 3, 5, 7, 2, 4, 8, 9, 12, 3, 4, 6, 9];
quickSort(0, array.length - 1, array);
console.log(array);Java 实现
import java.util.Arrays;
public class quickSort {
public static void _quickSort(int left, int right, int[] array) {
if (left > right) return;
int temp = array[left];
int i = left, j = right;
while (i < j) {
while (array[j] >= temp && j > i) {
j--;
}
while (array[i] <= temp && i < j) {
i++;
}
int current = array[i];
array[i] = array[j];
array[j] = current;
}
array[left] = array[i];
array[i] = temp;
_quickSort(left, i - 1, array);
_quickSort(j + 1, right, array);
}
public static void main(String[] args) {
int[] array = {6, 2, 3, 5, 7, 2, 4, 8, 9, 12, 3, 4, 6, 9};
_quickSort(0, 13, array);
System.out.println(Arrays.toString(array));
}
}Metadata
Metadata
Assignees
Labels
No labels