Android - 记录一些简单的算法

本人一直觉得，算法对于android应用开发来说并不是必须的。但是作为一个Java语言吃饭的人，掌握一些简单的算法，还是有必要的。

冒泡排序：

过程：

1. 从后往前，相邻的两个数进行比较，若前面的数大于后面的数，则前面的数往后沉，后面的数往前冒。即交换位置。知道最前面的两个数字比较结束，则第一个数即为最小数。
2. 重复上面的比较，对剩下的数据进行操作。

平均时间复杂度： O(n2)

代码实现：

public void MaoPao(int[] array){
    int temp;
    boolean flag;
    for(int i = 0; i < array.length - 1; i++){
        flag = false;
        for(int j = array.length - 1; j > i; j--){
            if (array[j] < array[j-1]){
                temp = array[j-1];
                array[j-1] = array[j];
                array[j] = temp;
                flag = true;
            }
        }
        if (!flag) break;
    }
}

选择排序：

过程：

长度为n的数组，首先整个循环一遍，选择出最小的数，与第一个数字交换。再循环n-1个数，选择最小的数，与第二个数交换。第n-1次遍历，找到最小的数值与第n-1个元素交换，排序完成。

平均时间复杂度：O(n2)

代码实现：

public void XuanZe(int[] array){
    for (int i = 0; i < array.length; i ++){
        int minIndex = i;
        for (int j = i+1; j < length-1; j ++){
            if (array[j] < array[minIndex]){
                minIndex = j;
            }
        }
        if (minIndex != i){
            int temp = array[i];
            array[i] = array[minIndex];
            array[minIndex] = temp;
        }
    }
}

插入排序：

过程：

假定第1个数已经排好序，现将后相邻的数在已经排好序的数组中从后往前遍历插入其中，如此反复，将全部排序完成。

平均时间复杂度：O(n2)

代码实现：

public void XuanZe(int[] array){
    int temp;
    for(int i = 1; i < array.length; i ++){
        for (int j = i; j > 0; j--){
            if (array[j] < array[j-1]){
                temp = array[j];
                array[j] = array[j-1];
                array[j-1] = temp;
            }
        }
    }
}