1.冒泡排序
1.1思想
每次遍歷過(guò)程中喝峦，從頭開(kāi)始遍歷牲芋，對(duì)比每一位數(shù)組和下一位數(shù)字的大小惠险，只要發(fā)現(xiàn)下一位數(shù)字比當(dāng)前大苗傅，則交換兩個(gè)數(shù)字，這樣一次遍歷班巩，最大的元素就出現(xiàn)在了數(shù)組的末尾渣慕。下一次遍歷，依然是從頭開(kāi)始抱慌，但是第一次遍歷的末尾元素已經(jīng)不用遍歷（因?yàn)槭亲畲笤亓耍┭疯搿Ｈ绱讼氯ィ貜?fù)以上過(guò)程抑进，直至最終完成排序强经。
1.2實(shí)現(xiàn)
用兩個(gè)for循環(huán)來(lái)實(shí)現(xiàn)內(nèi)外循環(huán)，外循環(huán)（i）范圍為（0arr.len）寺渗，內(nèi)循環(huán)（j）范圍為（0arr.len-i-1）匿情。
為什么-1兰迫？因?yàn)槲覀兠看伪闅v內(nèi)循環(huán)時(shí)，需要比較的是當(dāng)前位和下一位元素的大小炬称，即a[j]與a[j+1]的大小汁果，所以需要-1。
為什么-i玲躯？因?yàn)槲覀兠看伪闅v完一次据德，則有一個(gè)最大元素已經(jīng)排序完成，拿第一次舉例跷车，第一次完成之后棘利，最大元素已經(jīng)在末尾，那么我們下一次內(nèi)循環(huán)遍歷姓赤，就不再需要遍歷末尾位置了赡译。
class Solution {
/*
* 冒泡排序
*/
public static void bubbleSort(int[] a) {
boolean flag = true;
for (int i = 0; i < a.length; i++) {
flag = false;
for (int j = 0; j < a.length - i - 1; j++) {
if (a[j + 1] < a[j]) {
int temp = a[j];
a[j] = a[j + 1];
a[j + 1] = temp;
flag = true;
}
}
//為什么需要這個(gè)flag仲吏，是一種優(yōu)化不铆，如果一次內(nèi)循環(huán)遍歷，發(fā)現(xiàn)沒(méi)有交換位置的元素了裹唆，說(shuō)明數(shù)組已經(jīng)有序誓斥，不需要再次遍歷
if (!flag) {
break;
}
}
}
public static void main(String[] args) {
int i;
int[] a = {20, 40, 30, 10, 60, 50};
System.out.printf("before sort:");
for (i = 0; i < a.length; i++)
System.out.printf("%d ", a[i]);
System.out.printf("\n");
bubbleSort(a);
System.out.printf("after sort:");
for (i = 0; i < a.length; i++)
System.out.printf("%d ", a[i]);
System.out.printf("\n");
}
}
2.快速排序
1.1思想
快排的思想精華在于，每次遍歷许帐，以選取的基準(zhǔn)值為界劳坑，都要將數(shù)組一分為二，左邊為小于基準(zhǔn)值的元素成畦，右邊為大于基準(zhǔn)值的元素距芬。然后，再按此方法對(duì)這兩部分?jǐn)?shù)據(jù)分別進(jìn)行快速排序循帐，整個(gè)排序過(guò)程可以遞歸進(jìn)行框仔，以此達(dá)到整個(gè)數(shù)據(jù)變成有序序列。
1.2實(shí)現(xiàn)
每次遍歷拄养，選取需要排序的數(shù)組的左邊第一個(gè)值為基準(zhǔn)值离斩，然后先從右邊開(kāi)始找第一個(gè)小于基準(zhǔn)值的值，找到之后瘪匿，直接將值覆蓋到基準(zhǔn)值的位置跛梗，然后從左邊開(kāi)始找第一個(gè)大于基準(zhǔn)值的值，找到之后棋弥，直接將值覆蓋到之前遍歷到的第一個(gè)小于基準(zhǔn)值的位置核偿，以此循環(huán)進(jìn)行，直到左邊界>=右邊界顽染，說(shuō)明這次遍歷完成漾岳。以當(dāng)前基準(zhǔn)值為界聂薪，左邊是小于基準(zhǔn)值的值，右邊是大于基準(zhǔn)值的值蝗羊。然后對(duì)于左右子數(shù)組藏澳，分別做快排，做遞歸循環(huán)耀找。
class Solution {
/*
* 快速排序
*/
public static void quickSort(int[] a, int l, int r) {
if (l < r) {
int i, j, x;
i = l;
j = r;
x = a[i];
while (i < j) {
while (i < j && a[j] > x)
j--; // 從右向左找第一個(gè)小于x的數(shù)
if (i < j)
a[i] = a[j];
while (i < j && a[i] < x)
i++; // 從左向右找第一個(gè)大于x的數(shù)
if (i < j)
a[j] = a[i];
}
a[i] = x;
quickSort(a, l, i - 1); /* 遞歸調(diào)用 */
quickSort(a, i + 1, r); /* 遞歸調(diào)用 */
}
}
public static void main(String[] args) {
int i;
int a[] = {30, 40, 60, 10, 20, 50};
System.out.printf("before sort:");
for (i = 0; i < a.length; i++)
System.out.printf("%d ", a[i]);
System.out.printf("\n");
quickSort(a, 0, a.length - 1);
System.out.printf("after sort:");
for (i = 0; i < a.length; i++)
System.out.printf("%d ", a[i]);
System.out.printf("\n");
}
}
