概述
Java中排序算法是非常重要的一部分，这里简单分析下冒泡排序和快速排序的实现思路及其代码实现。
常见排序算法时间复杂度表
排序法 平均时间复杂度 最差情形 稳定度 额外空间 备注
冒泡排序 O(n^2) O(n^2) 稳定 O(1) n小时较好
选择排序 O(n^2) O(n^2) 不稳定 O(1) n小时较好
插入排序 O(n^2) O(n^2) 稳定 O(1) 大部分已排序较好
快速排序 O(nlogn) O(n^2) 不稳定 O(nlogn) n大时较好
shell排序 O(nlogn) O(n^s)1<s<2 不稳定 O(1) s是所选分组
归并排序 O(nlogn) O(nlogn) 稳定 O(1) n大时较好
堆排序 O(nlogn) O(nlogn) 稳定 O(1) n大时较好
基数排序 O(logrB) O(logrB) 稳定 O(n) B为真数(0-9),r为基数(个十百)
冒泡排序（从小到大排序）
冒泡排序(Bubble Sorting)的基本思想：从数组的左端开始遍历，依次比较前后相邻的两个元素，如果发现前一个元素比后一个元素大则进行交换，使得值大的向数组的右端移动，值小的向数组的左端移动。
有时候我们在冒泡过程中已经有序，不会进行交换，所以可以设置一个flag标记位，判断本次遍历是否进行了交换，如果没有进行交换则说明该数组已经是一个有序的数组了，可以退出循环。
冒泡排序图解
代码实现[Java] 纯文本查看 复制代码 public class BubbleSort {
public static void bubbleSort(int[] array) {
if (array == null || array.length <= 0) {
throw new IllegalArgumentException();
}
int temp = 0;
boolean flag = false;
for (int i = 0;i < array.length - 1;i++) {
for (int j = 0; j < array.length - i - 1;j++) {
if (array[j] > array[j + 1]) {
temp = array[j];
array[j] = array[j + 1];
array[j + 1] = temp;
flag = true;
}
}
if (flag == false) {
break;
} else {
flag = true;
}
}
}
}
快速排序（从小到大）
快速排序的思想：在数组中选一个数作为基准，将比这个基准大的数移动到它的右边，将比这个基准小的数移动到左边，然后通过递归的方式最后达到有序的状态。 代码实现
[Java] 纯文本查看 复制代码 public class QuickSort {
public static void main(String[] args) {
int[] array = {69,62,89,37,97,17,28,49,-1};
quickSort(array,0,array.length-1);
System.out.println(Arrays.toString(array));
}
public static void quickSort(int[] arr, int left, int right) {
if (arr == null || arr.length <= 0) {
throw new IllegalArgumentException();
}
int l = left;
int r = right;
// 我选择的是以中间值作为基准进行排序
int pivot = arr[(l + r)/2];
int temp = 0;
while (l < r) {
// 在基准的左边挑选出比它大的元素
while (arr[l] < pivot) {
l++;
}
// 在基准的右边挑选出比它小的数
while (arr[r] > pivot) {
r--;
}
// 当两个指针找到一块，则退出循环
if (l >= r) {
break;
}
// 将挑出的两个值进行交换
temp = arr[l];
arr[l] = arr[r];
arr[r] = temp;
// 左指针值等于中间值时，说明在上一步循环中基准的左边都是比它小的数，是等于pivot才退出循环的
if (arr[l] == pivot) {
r--;
}
// 右指针值等于中间值时，说明在上一步循环中基准的右边都是比它大的数，是等于pivot才退出循环的
if (arr[r] == pivot) {
l++;
}
}
if (l == r) {
l++;
r--;
}
// 向左递归
if (left < r) {
quickSort(arr, left, r);
}
if (right > l) {
quickSort(arr, l, right);
}
}
}
| 
收藏
淘帖
踩
