算法基础 | 交换排序
2020-10-11 本文已影响0人
icebreakeros
冒泡排序
算法描述:
比较相邻元素,如果第一个数比第二个数大,则交换两个元素
对每一对相邻元素做同样的比较,从开始第一对到结尾的最后一对,这样最后的元素应该是最大的数
针对所有元素重复以上步骤,除了最后一个
重复以上动作
public class BubbleSort {
public static void main(String[] args) {
BubbleSort bubbleSort = new BubbleSort();
Integer[] numbers = new Integer[]{10, 8, 3, 7, 9, 1, 4};
bubbleSort.sort(numbers);
Arrays.asList(numbers).stream().forEach(System.out::println);
}
public void sort(Integer[] numbers) {
if (numbers.length <= 1) {
return;
}
for (int i = 0; i < numbers.length; i++) {
for (int j = 0; j < numbers.length - i - 1; j++) {
if (numbers[j] > numbers[j + 1]) {
int t = numbers[j];
numbers[j] = numbers[j + 1];
numbers[j + 1] = t;
}
}
}
}
}
快速排序
算法描述:
从数列中挑出一个元素,称为基准pivot
重新排序数列,所有元素比基准值小的放在基准前面,所有元素比基准值大的摆在基准的后面,在这个分区退出之后,该基准就处于数列的中间位置
递归地recursive两个子数组
public class QuickSort {
public static void main(String[] args) {
QuickSort quickSort = new QuickSort();
Integer[] numbers = new Integer[]{10, 8, 3, 7, 9, 1, 4};
quickSort.sort(numbers, 0, numbers.length - 1);
Arrays.asList(numbers).stream().forEach(System.out::println);
}
public void sort(Integer[] numbers, int left, int right) {
if (left < right) {
int p = partition(numbers, left, right);
sort(numbers, left, p - 1);
sort(numbers, p + 1, right);
}
}
private int partition(Integer[] numbers, int left, int right) {
int p = numbers[left];
while (left < right) {
while (left < right && numbers[right] >= p) {
right--;
}
numbers[left] = numbers[right];
while (left < right && numbers[left] <= p) {
left++;
}
numbers[right] = numbers[left];
numbers[left] = p;
}
return left;
}
}