选择排序
//selection sort an array a[] with size n
void selectionSort(int a[], int n) {
int global, temp;
for(in i = 0; i < n-1; i++) {
global = i;
for (int j = i +1; j < n; j++) {
if(a[j] < a[global]) {
global = j; //record the index of the smallest element
}
}
temp = a[i];
a[i] = a[global];
a[global] = temp;
}
}
time complexity O(n^2)
归并排序
ArrayList<int> mergeSort(ArrayList<int> a, int left, int right){
ArrayList<int> solution;
if(left == right){
solution.add(a.get[left]);
return solution;
}
int mid = left + (right - left) / 2;
ArrayList<int> solution_left = mergeSort(a, left, mid);
ArrayList<int> solution_right = mergeSort(a, mid + 1, right);
solution = combine(solution_left, solution_right);
return solution;
}
ArrayList<int> combine(ArrayList<int> a1, ArrayList<int> a2) {
int ia = 0;
int ib = 0;
ArrayList<int> solution;
while (ia < a1.size() && ib < a2.size()) {
if (a1.get(ia) < a2.get(ib)) {
solution.add(a1.get(ia));
}
else {
solution.add(a2.get(ib));
}
}
while(ia < a1.size()){
solution.add(a1.get(ia);
}
while(ib < a2.size(){
solution.add(a2.get(ib));
}
return solution;
}