android中常用5种排序算法

在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);
            }
        }
    }