排序算法(1)|排序算法(1) 2018-03-07
选择排序
//selection sort an array a[] with size nvoid 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;
}
}
【排序算法(1)|排序算法(1) 2018-03-07】time complexity O(n^2)
归并排序
ArrayList mergeSort(ArrayList a, int left, int right){
ArrayList solution;
if(left == right){
solution.add(a.get[left]);
return solution;
}
int mid = left + (right - left) / 2;
ArrayList solution_left = mergeSort(a, left, mid);
ArrayList solution_right = mergeSort(a, mid + 1, right);
solution = combine(solution_left, solution_right);
return solution;
}ArrayList combine(ArrayList a1, ArrayList a2) {
int ia = 0;
int ib = 0;
ArrayList 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;
}
推荐阅读
- 51号|51号 百日生涯营 day10排序日
- 画解算法（1.|画解算法：1. 两数之和）
- Guava|Guava RateLimiter与限流算法
- 一个选择排序算法
- SG平滑轨迹算法的原理和实现
- 《算法》-图[有向图]
- 排序（归并排序）
- LeetCode算法题-11.|LeetCode算法题-11. 盛最多水的容器（Swift）
- 虚拟DOM-Diff算法详解
- 《数据结构与算法之美》——队列