1.冒泡排序
1 package cn.itcast;
2
3 /*
4 * 冒泡排序基本思路是：
5 * 依次比較相鄰的兩個數，将小數放在前面，大數放在後面。
6 * 即在第一趟：首先比較第1個和第2個數，将小數放前，大數放後。
7 * 然後比較第2個數和第3個數，将小數放前，大數放後，如此繼續，
8 * 直至比較最後兩個數，将小數放前，大數放後。至此第一趟結束，将最大的數放到了最後。
9 * 在第二趟：仍從第一對數開始比較（因為可能由于第2個數和第3個數的交換，使得第1個數不再小于第2個數），
10 * 将小數放前，大數放後，一直比較到倒數第二個數（倒數第一的位置上已經是最大的），第二趟結束，在倒數第二的位置上得到一個新的最大數。（其實在整個數列中是第二大的數）。
11 * 如此下去，重複以上過程，直至最終完成排序。
12 */
13 public class BubbleSort {
14 public static void sort(int[] data) {
15 for (int i = 0; i < data.length - 1; i++) {
16 for (int j = 0; j < data.length - 1 - i; j++) {
17 if (data[j] > data[j + 1]) {
18 SortTest.swap(data, j, j + 1);
19 }
20 }
21 }
22 }
23 } View Code
2.選擇排序
1 package cn.itcast;
2
3 /*
4 * 選擇排序基本思路是：
5 * 把第一個元素依次和後面的所有元素進行比較。
6 * 第一次結束後，就會有最小值出現在最前面。
7 * 其餘依次類推。
8 */
9 public class SelectionSort {
10 public static void sort(int[] data) {
11 for (int x = 0; x < data.length - 1; x++) {
12 for (int y = x + 1; y < data.length; y++) {
13 if (data[y] < data[x]) {
14 SortTest.swap(data, x, y);
15 }
16 }
17 }
18 }
19 } 3.插入排序
1 package cn.itcast;
2
3 /*
4 * 插入排序基本思路是：
5 * 将n個元素的數列分為已有序和無序兩個部分，如插入排序過程示例下所示：
6 * {{a1}，{a2，a3，a4，…，an}}
7 * {{a1⑴，a2⑴}，{a3⑴，a4⑴ …，an⑴}}
8 * {{a1(n-1)，a2(n-1) ，…},{an(n-1)}}
9 * 每次處理就是将無序數列的第一個元素與有序數列的元素從後往前逐個進行比較，
10 * 找出插入位置，将該元素插入到有序數列的合适位置中。
11 */
12 public class InsertSort {
13 public static void sort(int[] data) {
14 for (int i = 1; i < data.length; i++) {
15 for (int j = i; (j > 0) && (data[j] < data[j - 1]); j--) {
16 SortTest.swap(data, j, j - 1);
17 }
18 }
19 }
20 } 4.希爾排序
1 package cn.itcast;
2
3 /*
4 * 希爾排序基本思路是：
5 先取一個小于n的整數d1作為第一個增量，
6 * 把檔案的全部記錄分成（n除以d1）個組。所有距離為d1的倍數的記錄放在同一個組中。
7 * 先在各組内進行直接插入排序；然後，取第二個增量d2<d1重複上述的分組和排序，
8 * 直至所取的增量dt=1(dt < dt-l <…< d2 < d1)，即所有記錄放在同一組中進行直接插入排序為止。
9 *
10 * 屬于插入類排序,是将整個無序列分割成若幹小的子序列分别進行插入排序。
11 * 排序過程：先取一個正整數d1<n，把所有序号相隔d1的數組元素放一組，
12 * 組内進行直接插入排序；然後取d2<d1，重複上述分組和排序操作；直至di=1， 即所有記錄放進一個組中排序為止 。
13 * 初始：
14 * d=5 49 38 65 97 76 13 27 49 55 04
15 * 49 13 |-------------|
16 * 38 27 |-------------|
17 * 65 49 |---------------|
18 * 97 55 |---------------|
19 * 76 04 |--------------|
20 * 一趟結果 13 27 49 55 04 49 38 65 97 76
21 *
22 * d=3 13 27 49 55 04 49 38 65 97 76
23 * 13 55 38 76 |--------|--------|--------|
24 * 27 04 65 |--------|--------|
25 * 49 49 97 |--------|--------|
26 * 二趟結果 13 04 49 38 27 49 55 65 97 76
27 *
28 * d=1 13 04 49 38 27 49 55 65 97 76
29 * |--|--|--|--|--|--|--|--|--|
30 * 13 04 49 38 27 49 55 65 97 76
31 * 三趟結果 04 13 27 38 49 49 55 65 76 97
32 */
33 public class ShellSort {
34 public static void sort(int[] data) {
35 for (int i = data.length / 2; i > 2; i /= 2) {
36 for (int j = 0; j < i; j++) {
37 insertSort(data, j, i);
38 }
39 }
40 insertSort(data, 0, 1);
41 }
42
43 /**
44 * @param data
45 * @param j
46 * @param i
47 */
48 private static void insertSort(int[] data, int start, int inc) {
49 for (int i = start + inc; i < data.length; i += inc) {
50 for (int j = i; (j >= inc) && (data[j] < data[j - inc]); j -= inc) {
51 SortTest.swap(data, j, j - inc);
52 }
53 }
54 }
55 } 5.快速排序
1 package cn.itcast;
2
3 /*
4 * 快速排序基本思路是：
5 * 一趟快速排序的算法是：
6 * 1）設定兩個變量i、j，排序開始的時候：i=0，j=N-1；
7 * 2）以第一個數組元素作為關鍵資料，指派給key，即 key=A[0]；
8 * 3）從j開始向前搜尋，即由後開始向前搜尋（j=j-1即j--），
9 * 找到第一個小于key的值A[j]，A[i]與A[j]交換；
10 * 4）從i開始向後搜尋，即由前開始向後搜尋（i=i+1即i++），
11 * 找到第一個大于key的A[i]，A[i]與A[j]交換；
12 * 5）重複第3、4、5步，直到 i=j。
13 * (3,4步是在程式中沒找到時候，j=j-1，i=i+1，直至找到為止。
14 * 找到并交換的時候i，j指針位置不變。
15 * 另外當i=j這過程一定正好是i++或j--完成的，最後令循環結束。)
16 */
17 public class QuickSort {
18 public static void sort(int[] data) {
19 quickSort(data, 0, data.length - 1);
20 }
21
22 private static void quickSort(int[] data, int i, int j) {
23 int pivotIndex = (i + j) / 2;
24 // swap
25 SortTest.swap(data, pivotIndex, j);
26
27 int k = partition(data, i - 1, j, data[j]);
28 SortTest.swap(data, k, j);
29 if ((k - i) > 1)
30 quickSort(data, i, k - 1);
31 if ((j - k) > 1)
32 quickSort(data, k + 1, j);
33
34 }
35
36 /**
37 * @param data
38 * @param i
39 * @param j
40 * @return
41 */
42 private static int partition(int[] data, int l, int r, int pivot) {
43 do {
44 while (data[++l] < pivot)
45 ;
46 while ((r != 0) && data[--r] > pivot)
47 ;
48 SortTest.swap(data, l, r);
49 } while (l < r);
50 SortTest.swap(data, l, r);
51 return l;
52 }
53 } 6.歸并排序
1 package cn.itcast;
2
3 /*
4 * 歸并操作(merge)，也叫歸并算法，指的是将兩個已經排序的序列合并成一個序列的操作。
5 * 如設有數列{6，202，100，301，38，8，1}
6 * 初始狀态： [6] [202] [100] [301] [38] [8] [1] 比較次數
7 * i=1 [6 202 ] [ 100 301] [ 8 38] [ 1 ] 3
8 * i=2 [ 6 100 202 301 ] [ 1 8 38 ] 4
9 * i=3 [ 1 6 8 38 100 202 301 ] 4
10 */
11 public class MergeSort {
12 public static void sort(int[] data) {
13 int[] temp = new int[data.length];
14 mergeSort(data, temp, 0, data.length - 1);
15 }
16
17 private static void mergeSort(int[] data, int[] temp, int l, int r) {
18 int mid = (l + r) / 2;
19 if (l == r)
20 return;
21 mergeSort(data, temp, l, mid);
22 mergeSort(data, temp, mid + 1, r);
23
24 for (int i = l; i <= r; i++) {
25 temp[i] = data[i];
26 }
27 int i1 = l;
28 int i2 = mid + 1;
29 for (int cur = l; cur <= r; cur++) {
30 if (i1 == mid + 1)
31 data[cur] = temp[i2++];
32 else if (i2 > r)
33 data[cur] = temp[i1++];
34 else if (temp[i1] < temp[i2])
35 data[cur] = temp[i1++];
36 else
37
38 data[cur] = temp[i2++];
39 }
40 }
41 } 7.堆排序
1 package cn.itcast;
2
3 /*
4 * 堆排序基本思路是：
5 * 堆排序利用了大根堆（或小根堆）堆頂記錄的關鍵字最大（或最小）這一特征，使得在目前無序區中選取最大（或最小）關鍵字的記錄變得簡單。
6 * （1）用大根堆排序的基本思想：
7 * ① 先将初始檔案R[1..n]建成一個大根堆，此堆為初始的無序區；
8 * ② 再将關鍵字最大的記錄R[1]（即堆頂）和無序區的最後一個 記錄R[n]交換，由此得到新的無序區R[1..n-1]和有序區R[n]，且滿足R[1..n-1].keys≤R[n].key；
9 * ③ 由于交換後新的根R[1]可能違反堆性質，故應将目前無序區R[1..n-1]調整為堆。
10 * 然後再次将R[1..n-1]中關鍵字最大的記錄R[1]和該區間的最後一個記錄R[n-1]交換，由此得到新的無序區R[1..n-2]和有序區R[n-1..n]，
11 * 且仍滿足關系R[1..n-2].keys≤R[n-1..n].keys，同樣要将R[1..n-2]調整為堆。直到無序區隻有一個元素為止。
12 * （2）大根堆排序算法的基本操作：
13 * ① 初始化操作：将R[1..n]構造為初始堆；
14 * ② 每一趟排序的基本操作：将目前無序區的堆頂記錄R[1]和該區間的最後一個記錄交換，然後将新的無序區調整為堆（亦稱重建堆）。
15 */
16 public class HeapSort {
17 public static void sort(int[] data) {
18 MaxHeap h = new MaxHeap();
19 h.init(data);
20 for (int i = 0; i < data.length; i++)
21 h.remove();
22 System.arraycopy(h.queue, 1, data, 0, data.length);
23 }
24
25 private static class MaxHeap {
26
27 void init(int[] data) {
28 this.queue = new int[data.length + 1];
29 for (int i = 0; i < data.length; i++) {
30 queue[++size] = data[i];
31 fixUp(size);
32 }
33 }
34
35 private int size = 0;
36
37 private int[] queue;
38
39 public int get() {
40 return queue[1];
41
42 }
43
44 public void remove() {
45 SortTest.swap(queue, 1, size--);
46 fixDown(1);
47 }
48
49 // fixdown
50 private void fixDown(int k) {
51 int j;
52 while ((j = k << 1) <= size) {
53 if (j < size && queue[j] < queue[j + 1])
54 j++;
55 if (queue[k] > queue[j]) // 不用交換
56
57 break;
58 SortTest.swap(queue, j, k);
59 k = j;
60 }
61 }
62
63 private void fixUp(int k) {
64 while (k > 1) {
65 int j = k >> 1;
66 if (queue[j] > queue[k])
67 break;
68 SortTest.swap(queue, j, k);
69
70 k = j;
71 }
72 }
73
74 }
75 } 排序測試類
1 package cn.itcast;
2
3 import java.util.Arrays;
4
5 public class SortTest {
6
7 public static void main(String[] args) {
8 int[] arr = { 2, 5, 3, 1, 4 };
9 System.out.println("排序前：" + Arrays.toString(arr));
10 // BubbleSort.sort(arr);
11 // SelectionSort.sort(arr);
12 // InsertSort.sort(arr);
13 // ShellSort.sort(arr);
14 // QuickSort.sort(arr);
15 // MergeSort.sort(arr);
16 // HeapSort.sort(arr);
17 System.out.println("排序後：" + Arrays.toString(arr));
18 }
19
20 /*
21 * 交換數組中的兩個元素
22 */
23 public static void swap(int[] data, int i, int j) {
24 int temp = data[i];
25 data[i] = data[j];
26 data[j] = temp;
27 }
28 } 我的GitHub位址：
https://github.com/heizemingjun我的部落格園位址：
http://www.cnblogs.com/chenmingjun我的螞蟻筆記部落格位址：
http://blog.leanote.com/chenmingjunCopyright ©2018 黑澤明軍
【轉載文章務必保留出處和署名，謝謝！】