在android中会经常使用一些算法来实现一些复杂的逻辑;
在这片博文中主要介绍五种算法:
1.选择排序;
2.插入排序（冒泡）;
3.快速排序;
4.合并排序;
5.堆排序;
1.选择排序
从数组一端选择一个数组中的一个元素,通过比较对比取出最小值(或者最大值)放在array的左边(右边 这里主要视遍历的开始为左还是右);逐个遍历;
下面看代码:
/**选择排序
*遍历数组 然后每次遍历到一个元素之后 继续遍历该元素之后的所有元素 然后找到最小的元素 和其换位置
*/
public static int[] select(int[] array){
for (int i = 0; i < array.length; i++) {
int minPos = i;
for (int j = i + 1; j < array.length; j++) {
if (array[j] < array[minPos]){
minPos = j;
}
}
if (array[i] > array[minPos]) {
int temp = array[i];
array[i] = array[minPos];
array[minPos] = temp;
}
}
return array;
}
2.插入排序
同样逐个遍历数组,每次两两比较,排列所遍历元素及其之前的元素;遍历完成,排序亦完成;
/**插入排序
*相当于 从0开始一直++ 然后一直排列索引跟之前的元素
*/
public static int[] insert(int[] array) {
for (int i = 1; i < array.length; i++) {
int temp = array[i];
for (int j = i - 1; j >= 0 ; j--) {
if (array[j] > temp ) {
array[j + 1] = array[j];
array[j] = temp;
}
}
}
return array;
}
3.快速排序
下面来看快速排序;选择一个元素(一般取array的第一个元素),然后作为目标元素,将array中比目标元素小的放在目标元素左边,比目标元素大的放在目标元素右边;
然后继续用相同方式排列左右两边的array; 下面来看代码:
/**
* 快速排序
* 在快排中要设定分水岭 就是随机一个元素 然后比他小的放置到其左边 比其大的在有边 循环往复
*/
public static int[] quick(int[] array) {
int length = array.length - 1;
sortQuick(array, 0, length);
return array;
}
private static void sortQuick(int[] array, int low, int length) {
if (low < length) {
int div = firstRun(array, low, length);
sortQuick(array, 0, div - 1);
sortQuick(array, div + 1, length);
}
}
private static int firstRun(int[] array, int low, int length) {
int base = array[low];
while (low < length) {
while (array[length] > base) {
length--;
}
swrap(array, low, length);
while (array[low] < base) {
low++;
}
swrap(array, low, length);
}
return low;
}
private static void swrap(int[] array, int low, int length) {
int temp = array[length];
array[length] = array[low];
array[low] = temp;
//return array;
}
4.合并排序
合并排序就是将数组拆分,然后比较多的再用插入排序的方式实现排序;用于处理元素或者较为复杂的情况;
/**
* 合并排序
* 一直在分割
* 然后 两部分 一直分割 然后一直递归
*/
public static int[] mesh(int[] array) {
int length = array.length - 1;
int[] mysort = mysort(array, 0, length);
return mysort;
}
private static int[] mysort(int[] array, int low, int length) {
int mid = (length + low) / 2;
if (low < length) {
mysort(array, low, mid);
mysort(array, mid + 1, length);
merge(array, low, mid, length);
}
return array;
}
private static void merge(int[] array, int low, int mid, int length) {
int[] temp = new int[length - low + 1];
int i = low;
int j = mid + 1;
int n = 0;
while (i <= mid && j <= length) {
if (array[i] > array[j]) {
temp[n++] = array[j++];
} else {
temp[n++] = array[i++];
}
}
while (i <= mid) {
temp[n++] = array[i++];
}
while (j <= length) {
temp[n++] = array[j++];
}
//合并的逻辑 赋值给array
for (int k = 0; k < temp.length; k++) {
array[low + k] = temp[k];
}
}
5.堆排序
首先介绍下堆:堆就是一个具备任何根元素大于(或者小于)左右孩子的完全的二叉树
堆排序其实就是一直构建大顶堆或者小顶堆,然后把堆顶和最后的元素调换,然后排除堆顶,重构其他元素为顶堆,再次替换顶元素,再替换,这么一个循环往复的过程;
下面看代码:
/**
* 堆算法 大顶堆 小顶堆
* 每次取堆定 然后放入数组 重构堆 再取再重构
*/
public static int[] heap(int[] array) {
int length = array.length - 1;
for (int i = 0; i < length; i++) {
buildHeap(array, length - i);
swapHeap(array, 0, length - i);
}
return array;
}
private static void swapHeap(int[] array, int a, int b) {
int temp = array[b];
array[b] = array[a];
array[a] = temp;
}
private static void buildHeap(int[] array, int lastIndex) {
//获取左孩子和右孩子
int pos = (lastIndex - 1) / 2;
for (int i = pos; i >= 0; i--) {
int childL = i * 2 + 1;
int childR = i * 2 + 2;
int maxIndex = childL;
if (childR <= lastIndex) {
//有右孩子
if (array[childL] < array[childR]) {
maxIndex++;
}
} else if (childL <= lastIndex) {
//有左孩子
}
if (array[i] < array[maxIndex]) {
swapHeap(array, i, maxIndex);
}
}
}
网友评论