参考资料：
http://blog.csdn.net/morewindows/article/details/6684558
http://ahalei.blog.51cto.com/4767671/1365285
冒泡排序
冒泡排序是一种简单的交换排序
按照从大到小排序一个数组：
每一次，从底到上遍历，比较2个元素，并把较少的元素，逐步的冒上来，经过一轮遍历有，顶上即为最小的元素；
思想一是两两比较，将较小的冒上去
实现代码：
public static void main(String[] args) {
int b[] = {1, 5, 9, 3, 2, 0, 4, 7, 6, 8};
sort3(b);
}
public static void sort3(int a[]) {
Utils.print("排序前:\t\t");
Utils.printArray(a);
int len = a.length;
// 外循环
for (int out = 0; out < len; out++) {
// 内循环,从后往前查找,不断冒泡
for (int inner = len - 1; inner > out; inner--) {
if (a[inner] < a[inner - 1]) { // 两两比较,并交换
int tmp = a[inner];
a[inner] = a[inner - 1];
a[inner - 1] = tmp;
Utils.print(String.format("冒泡数:\t%s\t", tmp));
Utils.printArray(a);
}
}
}
Utils.print("排序后: \t\t");
Utils.printArray(a);
}
输出：
Paste_Image.png
优化冒泡排序一，减少比较次数##
如果内循环在某一个循环中，没有发生交换，说明序列已经有序了，直接退出即可；
代码：
public static void main(String[] args) {
int a[] = {1,5,9,20,0,-3,8,10,56,33,22,30};
boolean swap = true;
for (int i = 0; i < a.length - 1; i++) {
swap = false; // 每次还原成 false
for (int j = a.length - 1; j > i; j--) {
if(a[j] < a[j - 1]) {
int tmp = a[j];
a[j] = a[j-1];
a[j-1] = tmp;
swap = true;
}
}
Utils.printArray(a);
// 没有交换,直接结束,退出循环
if(!swap) {
break;
}
}
}
输出：
Paste_Image.png
如果不优化，减少比较次数，输出为：
Paste_Image.png
=====================================================
快速排序
冒泡排序，是相邻的2个数进行比较，并交换传递，有些不合理；
快排，就是来消除这种不太合理的操作；
基本思路
1.从数组中取出一个基准数，base；
2.分区，将数组中，比base小的数，全放入它的左边，比它大或*等于*数，放入其右边；
3.对左右分期，重复1，2操作，直到区间的数，只有一个为止，也就是不断化小分区
实现思路
0. 从初始化数组，取第一个元素，设置为 基数 base；
1. 从数组，最右侧开始，从右往左查找，找到比 base 小的数（类似冒泡）但是不交换，下标记为right;
2. 从左往后查找，找到比base大的数，下标记为 left;
3. 交换 left 与 right 下标数值；
4. right 继续 往左走，left 往右走，重复查找、交换的过程，直到 left = right,
5. 当 left = right 时，交换 基数 与 下标 left 的数值，至此，第一轮 查找交换结束；
6. 分治法，划分区间，在区间内重复 1到5的过程；
** 代码实现 **
int list[] = {6, 5, 2, 1, 7, 4, 5, 8, 3};
Utils.print("排序前\t\t");
Utils.printArray(list);
quickSort2(list, 0, list.length - 1);
Utils.print("排序后\t\t");
Utils.printArray(list);
private void quickSort2(int a[], int left, int right) {
// 前置检查
if (left > right) {
return;
}
// 记录,参数值
int i, j, baseValue, t;
baseValue = a[left];
i = left;
j = right;
while (i < j) {
// 从右往左,查找大于base的数 (下标 j 对应的数)
while (a[j] >= baseValue && i < j) {
j--;
}
// 从左往右,查找小于base的数 (下标 i 对应的数)
while (a[i] <= baseValue && i < j) {
i++;
}
// 【交换部分】交换2个数
if (i < j) {
t = a[i];
a[i] = a[j];
a[j] = t;
}
}
// 【交换部分】基数归位
a[left] = a[i];
a[i] = baseValue;
System.out.format("base = %d:\t", a[i]);
printPart(a, left, right);
// 分治,减小区间
quickSort2(a, left, i - 1); // 处理左边的
quickSort2(a, i+1, right); // 处理右边的
}
// 打印序列
public void printPart(int[] list, int begin, int end) {
for (int i = 0; i < begin; i++) {
System.out.print("\t");
}
for (int i = begin; i <= end; i++) {
System.out.print(list[i] + "\t");
}
System.out.println();
}
输出：
Paste_Image.png
