Description
Given an integer array, sort it in ascending order. Use selection sort, bubble sort, insertion sort or any O(n2) algorithm.
Example
Example 1:
Input: [3, 2, 1, 4, 5]
Output: [1, 2, 3, 4, 5]
Explanation:
return the sorted array.
Example 2:
Input: [1, 1, 2, 1, 1]
Output: [1, 1, 1, 1, 2]
Explanation:
return the sorted array.
Solution1 - Bubble Sort
//version1
public void sortIntegers(int[] A) {
if (A == null || A.length <= 1)
return;
for (int i = A.length - 1;i>0 ;i-- ){
for (int j = 0; j<i ;j++ ){
if(A[j]>A[j+1]){
int tmp = A[j];
A[j] = A[j+1];
A[j+1] = tmp;
}
}
}
}
//version2
public void sortIntegers(int[] A) {
if (A == null || A.length <= 1)
return;
int lastIndex = A.length - 1;
for (int i = 0; i< lastIndex; i++){
for (int j =0;j<lastIndex - i ; j++) {
if(A[j] > A[j+1]){
int tmp = A[j];
A[j] = A[j+1];
A[j+1] = tmp;
}
}
}
}
Solution2 - Selection Sort
public void sortIntegers(int[] A) {
if (A == null || A.length == 0)
return;
for (int i = 0; i<=A.length-1 ;i++ ){
int maxIndex = 0;
int j;
for (j = 0; j<=A.length -1 -i ; j++) {
if(A[j] > A[maxIndex]){
maxIndex = j;
}
}
j--;
int tmp = A[maxIndex];
A[maxIndex] = A[j];
A[j] = tmp;
}
}
Solution3 - Insertion Sort
public void sortIntegers(int[] A) {
if (A == null || A.length == 0)
return;
for (int i =1; i<= A.length -1 ;i++ ){
int j = i;
while(j >= 1){
if(A[j] > A[j-1])
break;
int tmp = A[j];
A[j] = A[j-1];
A[j-1] = tmp;
j--;
}
}
}