冒泡排序
1 package com.cxx.cebc;
2
3 import java.util.Arrays;
4
5 /*
6 * 冒泡排序：
7 *從 arr[0]起，前一個依次和後一個比，誰大誰放後面，直到最後一個元素，确定最大的
8 *從 arr[0]起，前一個依次和後一個比，誰大誰放後面，直到次後個元素，确定第二二的
9 *從 arr[0]起，前一個依次和後一個比，誰大誰放後面，直到次次後個元素，确定第三大的
10 *..........
11 * .........
12 */
13 public class BubblingSort {
14 public static void main(String[] args) {
15 int[] arr = {6, 1, 2, 7, 9, 3, 4, 5, 10, 8};
16
17 System.out.println(Arrays.toString(arr) + " 原始資料。。。。。");
18 sort(arr);
19 System.out.println(Arrays.toString(arr) + "排序完成。。。。。。");
20 }
21
22 /*
23 * 冒泡排序算法
24 */
25 public static void sort(int[] arr) {
26 //記錄交換次數
27 int count = 0;
28 //外層for循環
29 for (int i = 0; i < arr.length; i++) {
30 //前後兩數比較，滿足條件則交換
31 for (int j = 1; j < arr.length - i; j++) {
32 if (arr[j - 1] > arr[j]) {
33 arr[j] = arr[j - 1] + arr[j];
34 arr[j - 1] = arr[j] - arr[j - 1];
35 arr[j] = arr[j] - arr[j - 1];
36 count++;
37 System.out.println(Arrays.toString(arr) + " 正在排序中.........");
38 }
39 }
40 }
41 System.out.println("排序後的數組:" + Arrays.toString(arr) + "\n 排序次數：" + count);
42 }
43 } 執行結果
[6, 1, 2, 7, 9, 3, 4, 5, 10, 8] 原始資料。。。。。
[1, 6, 2, 7, 9, 3, 4, 5, 10, 8] 正在排序中.........
[1, 2, 6, 7, 9, 3, 4, 5, 10, 8] 正在排序中.........
[1, 2, 6, 7, 3, 9, 4, 5, 10, 8] 正在排序中.........
[1, 2, 6, 7, 3, 4, 9, 5, 10, 8] 正在排序中.........
[1, 2, 6, 7, 3, 4, 5, 9, 10, 8] 正在排序中.........
[1, 2, 6, 7, 3, 4, 5, 9, 8, 10] 正在排序中.........
[1, 2, 6, 3, 7, 4, 5, 9, 8, 10] 正在排序中.........
[1, 2, 6, 3, 4, 7, 5, 9, 8, 10] 正在排序中.........
[1, 2, 6, 3, 4, 5, 7, 9, 8, 10] 正在排序中.........
[1, 2, 6, 3, 4, 5, 7, 8, 9, 10] 正在排序中.........
[1, 2, 3, 6, 4, 5, 7, 8, 9, 10] 正在排序中.........
[1, 2, 3, 4, 6, 5, 7, 8, 9, 10] 正在排序中.........
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10] 正在排序中.........
排序後的數組:[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
排序次數：13
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]排序完成。。。。。。 優化後的冒泡排序
1 package com.cxx.cebc;
2
3 import java.util.Arrays;
4
5 public class OptimizeBubblingSort {
6 public static void main(String[] args) {
7 int[] arr = {6, 1, 2, 7, 9, 3, 4, 5, 10, 8};
8
9 System.out.println(Arrays.toString(arr) + " 原始資料。。。。。");
10 sort(arr);
11 System.out.println(Arrays.toString(arr) + "排序完成。。。。。。");
12 }
13
14 /*
15 * 冒泡排序算法
16 */
17 public static void sort(int[] arr) {
18 //記錄交換次數
19 int count = 0;
20 //外層for循環
21 for (int i = 0; i < arr.length; i++) {
22 //記錄下最大數的下标，預設目前序列尾部元素最大
23 int index = arr.length - 1 - i;
24 //查找目前序列真實的最大的數下标
25 for (int j = 1; j < arr.length - i; j++) {
26 if (arr[j - 1] > arr[index]) {
27 index = j - 1;
28 }
29 }
30 //如果不是尾部元素最大，則交換并記錄交換次數
31 if (index != arr.length - 1 - i) {
32 arr[arr.length - 1 - i] = arr[index] + arr[arr.length - 1 - i];
33 arr[index] = arr[arr.length - 1 - i] - arr[index];
34 arr[arr.length - 1 - i] = arr[arr.length - 1 - i] - arr[index];
35 count++;
36 System.out.println(Arrays.toString(arr) + " 正在排序中.........");
37 }
38 }
39 System.out.println("排序次數：" + count);
40 }
41 } [6, 1, 2, 7, 9, 3, 4, 5, 10, 8] 原始資料。。。。。
[6, 1, 2, 7, 9, 3, 4, 5, 8, 10] 正在排序中.........
[6, 1, 2, 7, 8, 3, 4, 5, 9, 10] 正在排序中.........
[6, 1, 2, 7, 5, 3, 4, 8, 9, 10] 正在排序中.........
[6, 1, 2, 4, 5, 3, 7, 8, 9, 10] 正在排序中.........
[3, 1, 2, 4, 5, 6, 7, 8, 9, 10] 正在排序中.........
[2, 1, 3, 4, 5, 6, 7, 8, 9, 10] 正在排序中.........
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10] 正在排序中.........
排序次數：7
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]排序完成。。。。。。 選擇排序
1 package com.cxx.cebc;
2
3 import org.junit.Test;
4
5 import java.util.Arrays;
6
7 /*
8 * 選擇排序：
9 * arr[0]依次和arr[1]...arr[arr.length-1]比較，記錄下最小的數，與arr[0]交換位置
10 * arr[1]依次和arr[2]...arr[arr.length-1]比較，記錄下最小的數，與arr[1]交換位置
11 * arr[2]依次和arr[3]...arr[arr.length-1]比較，記錄下最小的數，與arr[2]交換位置
12 * .........
13 *
14 * .........
15 */
16 public class SelectionSort {
17 public static void main(String[] args) {
18 int[] arr = {6, 1, 2, 7, 9, 3, 4, 5, 10, 8};
19
20 System.out.println(Arrays.toString(arr) + " 原始資料。。。。。");
21 sort(arr);
22 System.out.println(Arrays.toString(arr) + "排序完成。。。。。。");
23 }
24
25 /*
26 * 選擇排序算法
27 */
28 @Test
29 public static void sort(int[] arr) {
30 //記錄交換次數
31 int count = 0;
32 //外層循環
33 for (int i = 0; i < arr.length; i++) {
34 //記錄最小的元素下标，預設頭部元素最小
35 int index = i;
36 //查找目前序列中最小的元素下标
37 for (int j = i + 1; j < arr.length; j++) {
38 if (arr[j] < arr[index]) {
39 index = j;
40 }
41 }
42 //如果不是頭部元素最小，則交換并記錄交換次數
43 if (index != i) {
44 arr[index] = arr[index] + arr[i];
45 arr[i] = arr[index] - arr[i];
46 arr[index] = arr[index] - arr[i];
47 count++;
48 System.out.println(Arrays.toString(arr) + " 正在排序中.........");
49 }
50
51 }
52 System.out.println("排序次數：" + count);
53 }
54
55 } [6, 1, 2, 7, 9, 3, 4, 5, 10, 8] 原始資料。。。。。
[1, 6, 2, 7, 9, 3, 4, 5, 10, 8] 正在排序中.........
[1, 2, 6, 7, 9, 3, 4, 5, 10, 8] 正在排序中.........
[1, 2, 3, 7, 9, 6, 4, 5, 10, 8] 正在排序中.........
[1, 2, 3, 4, 9, 6, 7, 5, 10, 8] 正在排序中.........
[1, 2, 3, 4, 5, 6, 7, 9, 10, 8] 正在排序中.........
[1, 2, 3, 4, 5, 6, 7, 8, 10, 9] 正在排序中.........
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10] 正在排序中.........
排序次數：7
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]排序完成。。。。。。 對比總結
1、冒泡排序是相鄰兩個數比，這兩個比較的數一緻在向右移動，選擇排序是固定一個位置的數和其後的數比，隻
有一個數在移動。優化過後的冒泡排序實際上就是選擇排序。
2、對于數組從小到大排序
冒泡排序第X趟下來确定第X大的元素，放在數組的倒數第X個位置
選擇排序第X趟下來确定第X小的元素，放在數組的順數第X個位置
冒泡排序一趟會交換很多次，是穩定的。
選擇排序一趟隻交換一次，是不穩定的。
穩定和不穩定：
比如對于數組5，6，2，8,1
原本5,6順序符合要求，但選擇排序第一趟下來，2和5交換位置，5,6的從小到大順序比打亂這就是不穩定。
而對于選擇排序，則不會出現打亂已有的滿足條件的順序，是穩定的。
穩不穩定其實取決于一趟交換幾次，交換一次肯定不穩定，優化過後的冒泡排序交換一次，不穩定。