@[TOC]
冒泡排序
原理
每一次排序都会把大的元素移到后边
第一次排序把最大的移到了最后边,
第二次把其次第二大的移到最后边,所以才有减i的操作
时间复杂度
O(n*n)
空间复杂度
O(1)
代码
冒泡排序算是最经典的排序算法了
public static void main(String[] args) {
Integer[] a = {0,-10,-8, 8,7,9,-90};
for (int i = 0; i < a.length - 1; i++) {
for (int j = 0; j < a.length - 1 - i; j++) {
if (a[j]>a[j+1]){
int tmp = a[j];
a[j] = a[j+1];
a[j+1] = tmp;
}
}
}
// 验证
Stream.of(a).forEach(System.out::println);
}
快速排序
原理
时间复杂度
O(n log n) 最坏是O(n*n)
空间复杂度
O(log n)
代码
public static void main(String[] args) {
Integer[] a = {0,-10,-8, 8,7,9,-90};
// 快排
quickSort(a, 0,a.length-1);
// 验证
Stream.of(a).forEach(System.out::println);
}
public static void quickSort(Integer[] arr, Integer low, Integer high){
// 这个退出条件一定不能少,否则堆栈溢出
if (low>high){
return;
}
int i,j,tmp,t;
i = low; j = high; tmp=arr[low];
while (i<j){
// 先遍历j,找到比基准元素小的,找不到就一直遍历
while (arr[j]>=tmp && i<j){
j--;
}
// 然后让i,低位走,找到比基准元素tmp大的
while (arr[i]<=tmp && i<j){
i++;
}
if (i<j){
t = arr[j];
arr[j] = arr[i];
arr[i] = t;
}
}
arr[low] = arr[i];
arr[i] = tmp;
quickSort(arr, low, j-1);
quickSort(arr, j+1, high);
}
问题
快排中为什么一定是右边先开始循环?
从右边先开始的前提是我们选择序列中最左边的元素最为基准值。
先从右边开始可以保证i,j相等的时候,arr[i] = arr[j] 小于基准值p。这样交换之后才能保证基准值左右两边分别小于和大于它的值。