对于一个int数组，请编写一个选择排序算法，对数组元素排序。
给定一个int数组A及数组的大小n，请返回排序后的数组。
测试样例：
[1,2,3,5,2,3],6
[1,2,2,3,3,5] 冒泡排序：
package test;
public class BubbleSort {
public int[] bubbleSort(int[] A, int n) {
int temp;
for (int j = 0; j < n - 1; j++) {
for (int i = 0; i < n - 1 - j; i++) {
if (A[i + 1] < A[i]) {
temp = A[i];
A[i] = A[i + 1];
A[i + 1] = temp;
}
}
}
return A;
}
public static void main(String[] args) {
BubbleSort bubSort = new BubbleSort();
int[] A = { 1, 2, 3, 5, 2, 3 };
int[] ASort = bubSort.bubbleSort(A, A.length);
for (int i = 0; i < ASort.length; i++) {
System.out.println(ASort[i]);
}
}
}
运行结果如下：
1 2 2 3 3 5
时间复杂度为O(n*n);两两相互比较，较小的元素向上冒泡，较大的元素沉到水底。
选择排序：
package test;
public class SelectionSort {
public int[] selectionSort(int[] A, int n) {
// write code here
int temp;
for (int j=0;j<n-1;j++)
{
for (int i=j+1;i<n;i++)
{
if (A[j]>A[i])
{
temp=A[j];
A[j]=A[i];
A[i]=temp;
}
}
}
return A;
}
public static void main(String[] args) {
SelectionSort selSort = new SelectionSort();
int[] A = { 1, 2, 3, 5, 2, 3 };
int[] ASort = selSort.selectionSort(A, A.length);
for (int i = 0; i < ASort.length; i++) {
System.out.println(ASort[i]);
}
}
}
运行结果如下：
1 2 2 3 3 5
时间复杂度为O(n*n);第一位存储最小的元素，第二位存储第二小的元素，以此类推。
插入排序：
package test;
public class InsertionSort {
public int[] insertionSort(int[] A, int n) {
int temp;
for (int j = 1; j < n; j++) {
for (int i = j; i > 0; i--) {
if (A[i] < A[i - 1]) {
temp = A[i];
A[i] = A[i - 1];
A[i - 1] = temp;
}
}
}
return A;
}
public static void main(String[] args) {
InsertionSort insSort = new InsertionSort();
int[] A = { 1, 2, 3, 5, 2, 3 };
int[] ASort = insSort.insertionSort(A, A.length);
for (int i = 0; i < ASort.length; i++) {
System.out.println(ASort[i]);
}
}
}
运行结果如下： 1 2 2 3 3 5
时间复杂度为O(n*n)，第二个数同第一个数比，如果比第一个小，就交换位置，然后第三个数同第二个数比，如果小就交换位置，并且继续同第一个数比较大小，如果小就交换位置，以此类推。