排序算法

1. 冒泡

思路:

• 遍历所有数，判断与之相邻数的大小关系，进而进行互换，这个遍历会执行数组长度-1次；

• 上述对整体数组的扫描，需要也需要进行数组长度-1次

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

• 上述添加了个标识变量，用来判断是否上一次一整个数组的扫描过程是否没有进行过互换；

  • 如果没有就表示，该数组已完成排序

时间复杂度：

• O（n）, n 表示数组长度。

2. 选择排序

思路：

• 扫描一次数组找到最小数排到第一位（这里以顺序排列为例）；
• 扫描二次数组找到最小数排到第二位；
• 扫描三次数组找到最小数排到第三位；
• ……

        int min = 0;
        int minIndex = 0;
        for (int i=0;i<arr.length-1;i++){
            // 这里注意循环前都需要初始化
            min = arr[i];
            minIndex = i;
            for (int j=i;j<arr.length-1;j++){
                if (min>arr[j+1]){
                    min = arr[j+1];
                    minIndex = j+1;
                }
            }
            arr[minIndex] = arr[i];
            arr[i] = min;
        }

时间复杂度：

• O（n）, n 表示数组长度。

3. 插入排序

思路：

• 从二个元素开始（以顺序排列为例），以与前面一个元素比较，如果小，那么记录该值，并将前面一个数的值赋值给当前元素
• 从三个元素开始，以与前面两个元素依次比较，
  • 先于前一个元素比较，如果小，那么记录该值，并将前面一个数的值赋值给当前元素
  • 然后当前元素索引-1，与该位置前一个元素比较，如果小，那么记录该值，并将前面一个数的值赋值给当前元素
• ….
• 依次比较，每一次从后向前扫描以跨越数组边界或者不小于前面一个元素停止

        int val = 0;
        int index = 0;
        for (int i=1;i<arr.length;i++){
            val = arr[i];
            index = i;
            // 防止数组越界
            while(index-1>=0 && val<arr[index-1]){
                arr[index] = arr[index-1];
                index--;
            }
            arr[index] = val;
        }

时间复杂度：

• O（n）, n 表示数组长度。

4. 希尔排序（互换）

思路：

• 将长度为n的数组，对半分为n/2组，对每组数进行插入排序；依次继续进行分组后进行插入排序，直至无法再分为止。

        int temp = 0;
        for (int group=arr.length/2;group>0;group/=2){
            for (int i=group;i<arr.length;i++){
                for (int j=i-group;j>=0;j-=group){
                    if (arr[j] > arr[j+group]){
                        temp = arr[j];
                        arr[j] = arr[j+group];
                        arr[j+group] = temp;
                    }
                }
            }
        }

时间复杂度：

• O（n）, n 表示数组长度。

5. 希尔排序（移位）

思路：

• 在4的基础上，将互换变为移位（保留最小的数，当比较完毕，完成所以移位操作后直接进行赋值）

        int val = 0;
        for (int group=arr.length/2;group>0;group/=2){
            for (int i=group;i<arr.length;i++){
                if (arr[i]<arr[i-group]){
                    val = arr[i];
                    int j = i;
                    while(j-group>=0 && val<arr[j-group]){
                        arr[j] = arr[j-group];
                        j-=group;
                    }
                    arr[j] = val;
                }
            }
        }

时间复杂度：

• O（n）, n 表示数组长度。

1. 二进制中1的个数

• 请实现一个函数，输入一个整数（以二进制串形式），输出该数二进制表示中 1 的个数。例如，把 9 表示成二进制是 1001，有 2 位是 1。因此，如果输入 9，则该函数输出 2。

示例 1：
输入：00000000000000000000000000001011
输出：3
解释：输入的二进制串 00000000000000000000000000001011 中，共有三位为 '1'。
示例 2：
输入：00000000000000000000000010000000
输出：1
解释：输入的二进制串 00000000000000000000000010000000 中，共有一位为 '1'。
示例 3：
输入：11111111111111111111111111111101
输出：31
解释：输入的二进制串 11111111111111111111111111111101 中，共有 31 位为 '1'。

• 输入必须是长度为 32 的 二进制串

思路：

方法一： 逐位判断

• 通过与运算 n&1 运算测试最右端是否为1这个机制
• 不断右移n，进行判断最右端是否为1，直到n=0为止

public class Solution {
    // you need to treat n as an unsigned value
    public int hammingWeight(int n) {
        int res = 0;
        while(n!=0){
            res += n&1;
            n>>>=1;
        }
        return res;
    }
}

复杂度分析：

• 时间复杂度 O(lo__g_2_n):此算法循环内部仅有 移位、与、加 等基本运算，占用 O(1) ；逐位判断需循环 log 2 次，其中 log 2 代表数字 n 最高位 1 的所在位数（例如 log 2=2, log 2=4）
• 空间复杂度： 变量 resres 使用常数大小额外空间。

方法二： 巧用n&(n-1)

• 由于 n&(n-1) 会消除n最右端的1

public class Solution {
    // you need to treat n as an unsigned value
    public int hammingWeight(int n) {
        int res = 0;
        while(n!=0){
            res++;
            n = n&(n-1);
        }
        return res;
    }
}

复杂度分析：

• 时间复杂度 O(M) ： n&(n−1) 操作仅有减法和与运算，占用 O(1) ；设 M 为二进制数字 n 中 1 的个数，则需循环 M 次（每轮消去一个 1 ），占用 O(M) 。
• 间复杂度 O(1) ： 变量 res 使用常数大小额外空间。