參考資料：
http://blog.csdn.net/morewindows/article/details/6684558
http://ahalei.blog.51cto.com/4767671/1365285
冒泡排序
冒泡排序是一種簡(jiǎn)單的交換排序
按照從大到小排序一個(gè)數(shù)組：
每一次，從底到上遍歷旋圆，比較2個(gè)元素宠默，并把較少的元素，逐步的冒上來(lái)灵巧，經(jīng)過(guò)一輪遍歷有搀矫，頂上即為最小的元素抹沪；
思想一是兩兩比較，將較小的冒上去
實(shí)現(xiàn)代碼：
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;
// 外循環(huán)
for (int out = 0; out < len; out++) {
// 內(nèi)循環(huán),從后往前查找,不斷冒泡
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("冒泡數(shù):\t%s\t", tmp));
Utils.printArray(a);
}
}
}
Utils.print("排序后: \t\t");
Utils.printArray(a);
}
輸出：
Paste_Image.png
優(yōu)化冒泡排序一艾君，減少比較次數(shù)##
如果內(nèi)循環(huán)在某一個(gè)循環(huán)中采够，沒(méi)有發(fā)生交換，說(shuō)明序列已經(jīng)有序了冰垄，直接退出即可蹬癌；
代碼：
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);
// 沒(méi)有交換,直接結(jié)束,退出循環(huán)
if(!swap) {
break;
}
}
}
輸出：
Paste_Image.png
如果不優(yōu)化，減少比較次數(shù)虹茶，輸出為：
Paste_Image.png
=====================================================
快速排序
冒泡排序逝薪，是相鄰的2個(gè)數(shù)進(jìn)行比較，并交換傳遞蝴罪，有些不合理董济；
快排，就是來(lái)消除這種不太合理的操作要门；
基本思路
1.從數(shù)組中取出一個(gè)基準(zhǔn)數(shù)虏肾，base；
2.分區(qū)欢搜，將數(shù)組中封豪，比base小的數(shù)，全放入它的左邊炒瘟，比它大或*等于*數(shù)吹埠，放入其右邊；
3.對(duì)左右分期疮装，重復(fù)1缘琅，2操作，直到區(qū)間的數(shù)廓推，只有一個(gè)為止刷袍，也就是不斷化小分區(qū)
實(shí)現(xiàn)思路
0. 從初始化數(shù)組，取第一個(gè)元素受啥，設(shè)置為 基數(shù) base做个；
1. 從數(shù)組，最右側(cè)開(kāi)始滚局，從右往左查找，找到比 base 小的數(shù)（類(lèi)似冒泡）但是不交換顽频，下標(biāo)記為right;
2. 從左往后查找藤肢，找到比base大的數(shù)，下標(biāo)記為 left;
3. 交換 left 與 right 下標(biāo)數(shù)值糯景；
4. right 繼續(xù) 往左走嘁圈，left 往右走省骂，重復(fù)查找、交換的過(guò)程最住，直到 left = right,
5. 當(dāng) left = right 時(shí)钞澳，交換 基數(shù) 與 下標(biāo) left 的數(shù)值，至此涨缚，第一輪 查找交換結(jié)束轧粟；
6. 分治法，劃分區(qū)間脓魏，在區(qū)間內(nèi)重復(fù) 1到5的過(guò)程兰吟；
** 代碼實(shí)現(xiàn) **
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;
}
// 記錄,參數(shù)值
int i, j, baseValue, t;
baseValue = a[left];
i = left;
j = right;
while (i < j) {
// 從右往左,查找大于base的數(shù) (下標(biāo) j 對(duì)應(yīng)的數(shù))
while (a[j] >= baseValue && i < j) {
j--;
}
// 從左往右,查找小于base的數(shù) (下標(biāo) i 對(duì)應(yīng)的數(shù))
while (a[i] <= baseValue && i < j) {
i++;
}
// 【交換部分】交換2個(gè)數(shù)
if (i < j) {
t = a[i];
a[i] = a[j];
a[j] = t;
}
}
// 【交換部分】基數(shù)歸位
a[left] = a[i];
a[i] = baseValue;
System.out.format("base = %d:\t", a[i]);
printPart(a, left, right);
// 分治,減小區(qū)間
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
