簡單排序-選擇排序、直接插入排序、冒泡排序

 簡單排序（選擇排序、直接插入排序、冒泡排序）演算法都是n^2量級的比較（n是元素個數）

 選擇排序動態圖：

 1 package com.inbreak.cnblogs.sort;
 2 
 3 /**
 4  * 選擇排序：
 5  * 如果有N個元素需要排序，那麼首先從N個元素中找到最小的那個(稱為第0小的)放在第0個位子上(和原來的第0個位子上的元素交換位置)，
 6  * 然後再從剩下的N-1個元素中找到最小的放在第1個位子上，然後再從剩下的N-2個元素中找到最小的放在第2個位子上……直到所有的元素都就位。
 7  *
 8  * @author inbreak
 9  * @create 2018-07-10
10  **/
11 
12 import com.inbreak.cnblogs.Helper;
13 
14 public class SelectionSort {
15 
16     public static void main(int a[], int len) {
17         Helper.printArray(a);
18         for (int i = 0; i < len - 1; i++) {
19             //保存第i次的值
20             int tmpMin = i;
21             //後面j~len（最後一項）
22             for (int j = i+1; j < len ; j++) {
23                 if(a[j] <  a[tmpMin]) {
24                     tmpMin = j;
25                 }
26             }
27             if (i == tmpMin) {
28                 //當前位置已經是最小值
29                 continue;
30             }
31             //找到j~len中最小的位置tmpMin,然後與當前的位置i交換
32             Helper.swap(a, i, tmpMin);
33         }
34 
35         Helper.printArray(a);
36     }
37 
38 }

直接插入排序動態圖：

 1 package com.inbreak.cnblogs.sort;
 2 
 3 import com.inbreak.cnblogs.Helper;
 4 
 5 /**
 6  * 直接插入排序 的思想：
 7  * 1.將整個數組分為 "有序" 和 "無序" 兩個部分，有序部分在左邊，無序部分在右邊。
 8  * 2.初始時 只有第一個元素a[0]時有序的，其餘為無序部分。
 9  * 3.取出從無序部分的第一個值插入到有序部分的合適位置p [如第一個無序部分就是a[1]與a[0]比較，找到a[1]應該放的位置p（可能是第0位，第1位）],
10  *     而後有序部分位置p以及p之後的元素都往後移一位。
11  * 4.直到無序部分沒有元素為止。
12  *
13  * @author inbreak
14  * @create 2018-07-10
15  */
16 public class InsertionSort {
17 
18     public static void main(int a[], int size) {
19         Helper.printArray(a);
20         //i迴圈是對無序部分的便利
21         for (int i = 1; i < size; i++) {
22             int tmp = a[i];
23             //j迴圈是對有序部分
24             for (int j = 0; j < i; j++) {
25                 if(tmp < a[j]) {
26                     //k迴圈是對有序部分的數組移動
27                     for (int k = i; k > j; k--) {
28                         a[k] = a[k-1];
29                     }
30                     //找到i要插入的位置
31                     a[j] = tmp;
32                     break;
33                 }
34             }
35         }
36         Helper.printArray(a);
37     }
38 }

冒泡排序動態圖：

 1 package com.inbreak.cnblogs.sort;
 2 
 3 import com.inbreak.cnblogs.Helper;
 4 
 5 /**
 6  * 冒泡排序：
 7  * 將整個數組a 分為有序部分和無序部分的兩個部分，無序在上面，有序在下麵。（感覺垂直方向形象點）
 8  * 開始時，整個數組時無序的，有序部分沒有元素。
 9  * 每趟使得無序部分的最大元素移動到有序部分的最上面的元素的上邊
10  *
11  * @author inbreak
12  * @create 2018-07-10
13  */
14 public class BubbleSort {
15 
16     public static void main(int[] a, int size) {
17         Helper.printArray(a);
18         //i迴圈是一共需要多少趟，倒敘計算
19         for (int i = size - 1; i > 0; i--) {
20             //j迴圈是對無序部分的數組元素兩兩比較交換
21             for (int j = 0; j < i; j++) {
22                 if (a[j] > a[j+1]) {
23                     Helper.swap(a, j, j+1);
24                 }
25             }
26 
27         }
28         Helper.printArray(a);
29     }
30 
31     public static void main2(int[] a, int size) {
32         Helper.printArray(a);
33         //i迴圈是一共需要多少趟，正序計算
34         for (int i = 0; i < size; i++) {
35             //j迴圈是對無序部分的數組元素兩兩比較交換
36             for (int j = 0; j < size -i-1; j++) {
37                 if (a[j] > a[j+1]) {
38                     Helper.swap(a, j, j+1);
39                 }
40             }
41 
42         }
43         Helper.printArray(a);
44     }
45 }