排序算法（一）（时间复杂度均为O(n*n)）

对于一个int数组，请编写一个选择排序算法，对数组元素排序。

给定一个int数组A及数组的大小n，请返回排序后的数组。

测试样例：

[1,2,3,5,2,3],6

[1,2,2,3,3,5]

冒泡排序：

 1 package test;
 2 
 3 public class BubbleSort {
 4     public int[] bubbleSort(int[] A, int n) {
 5         int temp;
 6         for (int j = 0; j < n - 1; j++) {
 7             for (int i = 0; i < n - 1 - j; i++) {
 8                 if (A[i + 1] < A[i]) {
 9                     temp = A[i];
10                     A[i] = A[i + 1];
11                     A[i + 1] = temp;
12                 }
13             }
14         }
15         return A;
16     }
17 
18     public static void main(String[] args) {
19         BubbleSort bubSort = new BubbleSort();
20         int[] A = { 1, 2, 3, 5, 2, 3 };
21         int[] ASort = bubSort.bubbleSort(A, A.length);
22         for (int i = 0; i < ASort.length; i++) {
23             System.out.println(ASort[i]);
24         }
25 
26     }
27 
28 }

运行结果如下：

1 2 2 3 3 5

时间复杂度为O(n*n);两两相互比较，较小的元素向上冒泡，较大的元素沉到水底。

选择排序：

 1 package test;
 2 
 3 public class SelectionSort {
 4       public int[] selectionSort(int[] A, int n) {
 5             // write code here
 6           int temp;
 7           for (int j=0;j<n-1;j++)
 8           {
 9           for (int i=j+1;i<n;i++)
10           {
11               if (A[j]>A[i])
12               {
13                   temp=A[j];
14                   A[j]=A[i];
15                   A[i]=temp;
16               }
17           }
18           }
19           return A;
20         }
21       
22         public static void main(String[] args) {
23             SelectionSort selSort = new SelectionSort();
24             int[] A = { 1, 2, 3, 5, 2, 3 };
25             int[] ASort = selSort.selectionSort(A, A.length);
26             for (int i = 0; i < ASort.length; i++) {
27                 System.out.println(ASort[i]);
28             }
29         }
30 
31 }

运行结果如下：

1 2 2 3 3 5

时间复杂度为O(n*n);第一位存储最小的元素，第二位存储第二小的元素，以此类推。

插入排序：

 1 package test;
 2 
 3 public class InsertionSort {
 4     public int[] insertionSort(int[] A, int n) {
 5         int temp;
 6         for (int j = 1; j < n; j++) {
 7             for (int i = j; i > 0; i--) {
 8                 if (A[i] < A[i - 1]) {
 9                     temp = A[i];
10                     A[i] = A[i - 1];
11                     A[i - 1] = temp;
12                 }
13             }
14         }
15         return A;
16     }
17 
18     public static void main(String[] args) {
19         InsertionSort insSort = new InsertionSort();
20         int[] A = { 1, 2, 3, 5, 2, 3 };
21         int[] ASort = insSort.insertionSort(A, A.length);
22         for (int i = 0; i < ASort.length; i++) {
23             System.out.println(ASort[i]);
24         }
25     }
26 }

运行结果如下： 1 2 2 3 3 5

时间复杂度为O(n*n)，第二个数同第一个数比，如果比第一个小，就交换位置，然后第三个数同第二个数比，如果小就交换位置，并且继续同第一个数比较大小，如果小就交换位置，以此类推。