Android技能树 — 排序算法基础小结 - android

前言：

现在安卓面试，对于算法的问题也越来越多了，要求也越来越多，特别是排序，基本必考题，而且还动不动就要手写，所以陆续要写算法的文章，也正好当自己学习。o(╥﹏╥)o

Android技能书系列：

Android基础知识

Android技能树 — 动画小结

Android技能树 — View小结

Android技能树 — Activity小结

Android技能树 — View事件体系小结

Android技能树 — Android存储路径及IO操作小结

Android技能树 — 多进程相关小结

Android技能树 — Drawable小结

数据结构基础知识

Android技能树 — 数组,链表,散列表基础小结

算法基础知识

Android技能树 — 排序算法基础小结

本文主要讲算法基础知识及排序算法。

基础知识：

稳定性：

我们经常听到说XXX排序算法是稳定性算法，XXX排序算法是不稳定性算法，那稳定性到底是啥呢？

举个最简单的例子：我们知道冒泡排序中最重要的是二二进行比较，然后按照大小来换位置：

if(arr[j]>arr[j+1]){      int temp = arr[j];      arr[j] = arr[j + 1];      arr[j + 1] = temp; }

我们可以看到这里的大小判定是前一个比后一个大，就换位置，如果相等就不会进入到if的执行代码中，所以我们二个相同的数挨在一起，不会进行移动，所以冒泡排序是稳定的排序算法，但是如果我们把上面的代码改动一下if里面的判断：

if(arr[j]>=arr[j+1]){      int temp = arr[j];      arr[j] = arr[j + 1];      arr[j + 1] = temp; }

我们添加了一个等号，那这个时候就不是稳定排序算法了，因为我们可以看到相等的时候它也换了位置了。

证明某个排序是不稳定很简单，比如你只要传入{2,2}，只要换了位置就是不稳定，证明不稳定只要一种情况下是不稳定的，那么就是不稳定排序算法。

复杂度

复杂度包括了时间复杂度和空间复杂度，但是通常我们单纯说复杂度的时候都指时间复杂度。

时间复杂度

用1+2+3+...+100为例：
普通写法：

int sum = 0,  n = 100;//执行1次for(int i =1 ; i <= 100 ; i++){   //执行n+1次        sum = sum + i;       //执行n次}Log.v("demo","sum:"+sum);   //执行1次

我们可以看到一共执行了2n+3次。（我们这里是2*100+3）

高斯算法：

int sum = 0,n = 100;   //执行1次sum = (1+n)*n /2;      //执行1次Log.v("demo","sum:"+sum);   //执行1次

我们可以看到一共执行了3次。

但是当我们的n很大的时候，比如变成了1000，第一种算法就是2*1000+3，但是第二种还是3次。

在进行算法分析时，语句总的执行次数T(n)是关于问题规模n的函数，进而分析T(n)随n的变化情况并确定T(n)的数量级。算法的时间复杂度，也就是算法的时间量度，记作：T(n) = O(f(n))。它表示随问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同，称作算法的渐近时间复杂度，简称为时间复杂度。其中f(n)是问题规模n的某个函数。

我们已经根据上面的解释看到了：
T(n) = O(f(n))；

所以第一种是：2*n + 3 = O(f(n)),第二种是3 = O(f(n))；我们可以看到是增长率和f(n)的增长率相同。

我们以前学高数都知道：比如f(x) = x^3 + 2x ,随着x的变大，其实基本都是x^3的值，而2x的的值后面影响越来越小，所以有高阶的时候，其他低阶都可以随着x的变大而忽略，同理前面的相乘的系数也是一样，所以：

那我们上面的第一种就变成了O(n)（ps:只保留最高位，系数变为1,），第二种变为了O(1)（ps:常数都变为1）

常见的时间复杂度：

最坏/最好/平均情况

比如我们玩猜数字，让你在1-n范围内猜某个数字，而你是从头到尾报数，如果猜的数正好是1，则最好情况下复杂度是1，如果猜的数是n,则最坏是n,平均的话就是n/2。排序也是一样，比如2,1,3,4,5,6,7,8,9你只需要调换2,1就可以，但是如果是9,8,7,6,5,4,3,2,1让你从小到大排序，你需要调换很多次。

空间复杂度

引用《大话数据结构》中的例子，比如你要计算某一年是不是闰年，你可以写一个算法:

if(year%4==0 && year%100 != 0){      System.out.println("该年是闰年");  }else if(year % 400 == 0){      System.out.println("该年是闰年");  }else{      System.out.println("该年是平年");  }

但是如果你在内存中存储了一个2150元素的数组，然后这个数组中是index是闰年的数组设置为1，其他设置为0，这样别人比如问你2000年是不是闰年，你直接查看该数组index为2000里面的值是不是1即可。这样通过一笔空间上的开销来换取了计算时间。

一个算法的优劣主要从算法的执行时间和所需要占用的存储空间两个方面衡量。

排序算法：

排序方法分为两大类: 一类是内部排序, 指的是待排序记录存放在计算机存储器中进行的排序过程；另一类是外部排序, 指的是待排序记录的数量很大，以至于内存一次不能容纳全部记录，在排序过程中尚需对外存进行访问的排序过程。

内部排序：

冒泡排序：

冒泡排序算法的运作如下：（从后往前）
1.比较相邻的元素。如果第一个比第二个大，就交换他们两个。
2.对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
3.针对所有的元素重复以上的步骤，除了最后一个。

4.持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

我们以最简单的数组{3,2,1}来看：

我们可以看到一种二个大的蓝色步骤（ps：3 - 1），然后每个蓝色里面的交换步骤是一步步变少(ps:2,1)。

所以我们就知道是二个for循环了：

/**我们的蓝色大框一共执行（3-1）次，也就是（nums.length -1）次*/ for (int i = length -1; i > 0; i--) {          /**    我们蓝色大框交换步骤从（3-1）次开始，    且每个蓝色大框里面的交换步骤在逐步减一，    正好就是上面的蓝色大框的（i变量）    */      for (int j = 0; j < i; j++) {                    //对比逻辑代码   }}

然后在里面加上判断，如果前一个比后一个大，交换位置即可。

public void bubbleSort(int[] nums) {           //传进来的数组只有0或者1个元素，则不需要排序     int length = nums.length;     if (length < 2) {          return;      }      for (int i = length -1; i > 0; i--) {            for (int j = 0; j < i; j++) {                if (nums[j] > nums[j + 1]) {                    int data = nums[j];                    nums[j] = nums[j + 1];                    nums[j + 1] = data;                }            }        }}

快速排序：

我们会先找一个关键数据，通常为第一个数，比如我们这里的5，然后把数字小于5的数字都放在5的左边，大于5的数字都放在5右边，然后对于左边的数字使用相同的方法，取第一个为关键数据，对其排序，然后一直这么重复。

伪代码：

quickSort (  nums ){            //小于2个的数组直接返回，因为个数为0或者1的肯定是有序数组      if(nums.length < 2){            return nums;      }             //取数组第一个数为参考值        data = nums[0];       //左边的数组       smallNums = （遍历nums中比data小的数）       //右边的数组        bigNums = （遍历nums中比data大的数）                //使用递归,对左边和右边的数组分别再使用我们写的这个方法。       return quickSort(smallNums)  +  data  +  quickSort(bigNums);      }

我们一步步来看如何实现具体的代码：(我会先根据思路写一个步骤很多的写法，用于介绍，再写一个好的。)

其实要实现功能，这个很简单，我们可以新建二个数组，然后再完全遍历整个原始数组，把比参考值小的和大的分别放入二个数组。

//取第一个数为参考值int data = nums[0];//我们先获取比参考值大的数及小的数各自是多少。int smallSize = 0, bigSize = 0;for (int i = 1; i < nums.length; i++) {       if (nums[i] <= data) {             smallSize++;        } else {             bigSize++;        }}//建立相应的数组，等会用来放左边和右边的数组int[] smallNums = new int[smallSize];int[] bigNums = new int[bigSize];//遍历nums数组，把各自大于或者小于参考值的放入各自左边和右边的数组。int smallIndex = 0;int bigIndex = 0;for (int i = 1; i < nums.length; i++) {    if (nums[i] > data) {          bigNums[bigIndex] = nums[i];          bigIndex++;    }else{           smallNums[smallIndex] = nums[i];           smallIndex++;    }}//左边和右边再各自使用递归调用smallNums = quickSort(smallNums);bigNums = quickSort(bigNums);//然后再把smallNums的所有数值赋给data左边，然后nums中间为data,然后再bigNums把data右边。for (int i = 0; i < smallNums.length; i++) {      nums[i] = smallNums[i];}nums[smallNums.length] = data;for (int i = smallSize + 1; i < bigNums.length + smallSize + 1; i++) {      nums[i] = bigNums[i - smallSize - 1];}

当然这也是可以实现的，可是感觉代码很多，而且每次调用quickSort进行递归的时候，都要新建二个数组，这样后面递归调用次数越多，新建的数组对象也会很多。我们可不可以思路不变，参考值左边是小的值，参考值右边是大的值，但是不新建数组。答案是当然！！（这逼装的太累了，休息一下。）

我们在左边开始的地方标记为 i ,右边为 j ,然后因为 i 的位置已经是我们的参考值了，所以从 j 那边开始移动，
因为我们的目标是左边的数是比参考值小，右边的比参考值大，所以从 j 开始往左移动，当找到一个比5小的数字，然后停住，
然后 i 从左边开始往右移动，然后找到比参考值大的数，然后停住，
交换 i 跟 j 指向的数
重复 2,3,4 直到 i 跟 j 重合（比如index为h的地方），然后交换我们的参考值跟这个 h 交换数据。

剩下的左边和右边的数组也都通过递归执行这个方法即可。

    public static void QuickSort(int[] nums, int start, int end) {        //如果start >= end了，说明数组就一个数了。不需要排序        if(start >= end){            return;        }        //取第一个数为参考值        int data = nums[start];        int i = start, j = end;                 //当 i 和 j 还没有碰到一起时候，一直重复移动 j 和 i 等操作        while (i != j) {                        //当 j 位置比参考值大的时候，继续往左边移动，直到找到一个比参考值小的数才停下            while (nums[j] >= data && i < j) {                j--;            }             //当 i 位置比参考值小的时候，继续往右边移动，直到找到一个比参考值大的数才停下            while (nums[i] <= data && i < j) {                i++;            }                        //交换二边的数            if (i < j) {                int t = nums[i];                nums[i] = nums[j];                nums[j] = t;            }        }                //当退出上面的循环，说明 i 和 j 的位置交汇了，更换参考值与 i 位置的值。        nums[start] = nums[i];        nums[i] = data;                //左边的数组通过递归继续调用，这时候因为参考值在 i 的位置，所以左边是从start 到 i -1        QuickSort(nums, start, i - 1);        //右边的数组通过递归继续调用，这时候因为参考值在 i 的位置，所以右边是从 i -1 到 end        QuickSort(nums, i + 1, end);    }

直接插入排序：

可以看到，我们是默认把第一个数字当做是排好序的数组（废话，一个数字当然是排好序的），然后每次后一个跟前面的进行比较排序，然后重复。所以我们可以看到最外面的一共是N-1层。然后每一层里面的比较次数是跟当前层数数量相同。

比如第二层。我们的数字2要和前面的1,3比较，那就要先跟3比较（当然如果此处比3大就不需要比较了，因为前面已经是个有序数组了，你比这个有序数组最大的值都大，前面的就不需要比了。）如果比3小就要跟1比较，正好比较2次，跟层数相同。

所以基本代码肯定是：

for(int i = 1; i < n ; i ++){            if( 当前待比较的数 >= 前面的有序数组最后一个数){                continue;  //这就没必要比较了。      }            for(int j = i-1 ; j >=0 ; j--){         // 当前待比较数  与  前面的有序数组中的数一个个进行比较。然后插在合适的位置。      }}

针对这个排序，代码本来只需要像下面这个一样即可：

    public static void InsertSort(int[] nums) {        for (int i = 1; i < nums.length; i += 1) {            if (nums[i - 1] <= nums[i]) {                continue;            }            int va = i;            int data = nums[i];            for (int j = i - 1; j >= 0; j--) {                if (nums[j] > data) {                    va = j;                    nums[j + 1] = nums[j];                }            }            nums[va] = data;        }    }

因为我们这里的数字是连续的，所以间隔是1，但是为了下一个排序的讲解方便，我们假设它们的间隔是可能不是1，所以改造成下面这个：

public static void InsertSort(int[] nums, int gap) {        for (int i = gap; i < nums.length; i += gap) {            if (nums[i - gap] > nums[i]) {                int va = i;                int data = nums[i];                for (int j = i - gap; j >= 0; j -= gap) {                    if (nums[j] > data) {                        va = j;                        nums[j + gap] = nums[j];                    }                }                nums[va] = data;            }        }    }

希尔排序:

希尔排序是直接插入排序算法的一种更高效的改进版本。

我们假设现在是1-6个数字，我们取数组的<数量/2>为间隔数（ps:所以为6/2 = 3），然后按照这个间隔数分别分组：

这样我们可以当场有三组数组{3,4,}，{1,6}，{5,2}
然后对每组数组使用直接插入排序。然后我们把间隔数再除以2（PS:为 3/2 = 1,取为1）。

然后再使用直接插入排序就可以得到最后的结果了。

所以还记不记得我们上面的直接插入排序代码写成了public static void InsertSort(int[] nums, int gap),就是为了考虑上面的多个间隔不为1的数组。

所以只要考虑我们的循环了几次，每次间隔数是多少就可以了：

public void ShellSort(int[] nums) {     int length = nums.length;     for (int gap = length / 2; gap > 0; gap /= 2) {          InsertSort(nums, gap);      }}

是不是发现超级简单。

（ps:这里记录一下，比如有10个数字，因为理论上是每次除以2，比如应该是5,2,1；但是有些文章是写着5,3,1，有些文章写着5,2,1。我写的代码也是5,2,1。。。o(╥﹏╥)o到底哪个更准确点。）

选择排序：

选择排序很简单，就是每次遍历，找出最小的一个放在前面（或者最大的一个放在后面），然后接着把剩下的再遍历一个个的找出来排序。

    public void selectSort(int[] nums) {        int min;        int va;        for (int i = 0; i < nums.length; i++) {            min = nums[i];            va = i;            for (int j = i + 1; j < nums.length; j++) {                if (nums[j] < min) {                    min = nums[j];                    va = j;                }            }            int temp = nums[i];            nums[i] = min;            nums[va] = temp;        }    }

堆排序：

这里我暂时空着，因为跟二叉树有关系，所以我准备先写一篇二叉树的数据结构，然后再写这个排序。有兴趣的可以自己去搜下。

归并排序：

归并算法，指的是将两个顺序序列合并成一个顺序序列的方法。

比如有数列{6，202，100，301，38，8，1}
初始状态：6,202,100,301,38,8,1
第一次归并后：{6,202},{100,301},{8,38},{1}，比较次数：3；
第二次归并后：{6,100,202,301}，{1,8,38}，比较次数：4；
第三次归并后：{1,6,8,38,100,202,301},比较次数：4；

这个引入网络上的图片了：

根据这个我们可以看到，我们要先不停的取中间拆分，左右二边拆开，一直拆到为一个元素的时候停止，然后再合并。

    public void mergeSort(int[] nums, int L, int R) {        //如果只有一个元素，那就不用排序了        if (L == R) {            return;        } else {            int M = (R + L) / 2;//每次取中间值            mergeSort(nums, L, M);//通过递归再把左边的按照这个方式继续不停的左右拆分            mergeSort(nums, M + 1, R);//通过递归再把右边的按照这个方式继续不停的左右拆分            merge(nums, L, M + 1, R);//合并拆分的部分        }    }

我们继续通过图片来说明上图最后合并的操作：

然后重复这个操作。如果比如左边的都比较完了，右边还剩好几个，只需要把右边剩下的全部都移入即可。

    public void merge(int[] nums, int L, int M, int R) {        int[] leftNums = new int[M - L];        int[] rightNums = new int[R - M + 1];        for (int i = L; i < M; i++) {            leftNums[i - L] = nums[i];        }        for (int i = M; i <= R; i++) {            rightNums[i - M] = nums[i];        }        int i = 0;        int j = 0;        int k = L;                //左边还没有全部比较完，右边还没有全部比较完        while (i < leftNums.length && j < rightNums.length) {            if (leftNums[i] >= rightNums[j]) {                nums[k] = rightNums[j];                j++;                k++;            } else {                nums[k] = leftNums[i];                i++;                k++;            }        }                //二边的比完之后，如果左边还有剩下，就把左边的全部移入数组尾部        while (i < leftNums.length) {            nums[k] = leftNums[i];            i++;            k++;        }        //二边的比完之后，如果右边还有剩下，就把右边的全部移入数组尾部        while (j < rightNums.length) {            nums[k] = rightNums[j];            j++;            k++;        }    }

基数排序：

先说明一个简单的桶排序吧：

比如我们要给{5,3,5,2,8}排序，我们初始化一组内容为0的数组（做为桶），只要把他们当做数组的index值，比如第一个是5，我们就nums[5] ++ ; 这样我们只要对这个数组遍历，取出里面的值，只要不为0就打印出来。

但是这样这里就会有一个问题了，就是如果我的数组里面最大的数是100000，那岂不是我初始化的数组长度是100000了，明显不能这样。我们知道一个数字肯定是由{0-9}这些数组成，只是处于不同的位数而已，所以我们可以还是按照{0-9}来放入某个桶，但是是先按照个位数排序，然后按照十位数，百位数，千位数.....等来一样样来放。

比如我们现在是{25,8,1000,158}四个数
第一次，我们比较的是个位数：

所以我们从左到右，从上到下的新数组的顺序是{1000,25,8,158}

第二次，我们比较的是十位数：

所以新数组是{1000,8,25,158}

3.第三次，我们比较百位数：

所以新数组还是{1000,8,25,158}

第四次，我们比较千位数：

这时候我们就可以看到最终排序是{8,25,158,1000}

ps:如果还有万位数等，持续进行以上的动作直至最高位数为止

我们既然知道了，要一直最外层循环要进行最高数的次数，所以我们第一步是找出最大的数有几位：

//可以通过递归找最大值： public static int findMax(int[] arrays, int L, int R) {        //如果该数组只有一个数，那么最大的就是该数组第一个值了        if (L == R) {            return arrays[L];        } else {            int a = arrays[L];            int b = findMax(arrays, L + 1, R);//找出整体的最大值            if (a > b) {                return a;            } else {                return b;            }        }    }    //也可以通过for循环找最大值：    public static int findMax(int[] arrays, int L, int R) {        int length = arrays.length;        int max = arrays[0];        for (int i = 1; i < length; i++) {            if (arrays[i] > max) {                max = arrays[i];            }        }        return max;    }

然后主要的排序代码：

    public static void radixSort(int[] arrays) {        int max = findMax(arrays, 0, arrays.length - 1);        //需要遍历的次数由数组最大值的位数来决定        for (int i = 1; max / i > 0; i = i * 10) {            int[][] buckets = new int[arrays.length][10];            //获取每一位数字(个、十、百、千位...分配到桶子里)            for (int j = 0; j < arrays.length; j++) {                int num = (arrays[j] / i) % 10;                //将其放入桶子里                buckets[j][num] = arrays[j];            }            //回收桶子里的元素            int k = 0;            //有10个桶子            for (int j = 0; j < 10; j++) {                //对每个桶子里的元素进行回收                for (int l = 0; l < arrays.length; l++) {                    //如果桶子里面有元素就回收(数据初始化会为0)                    if (buckets[l][j] != 0) {                        arrays[k++] = buckets[l][j];                    }                }            }        }    }

外部排序：

一般来说外排序分为两个步骤：预处理和合并排序。首先，根据可用内存的大小，将外存上含有n个纪录的文件分成若干长度为t的子文件（或段）；其次，利用内部排序的方法，对每个子文件的t个纪录进行内部排序。这些经过排序的子文件（段）通常称为顺串(run)，顺串生成后即将其写入外存。这样在外存上就得到了m个顺串（m=[n/t]）。最后，对这些顺串进行归并，使顺串的长度逐渐增大，直到所有的待排序的记录成为一个顺串为止。

结语：

最后附上百度上的图：

文章哪里不对，帮忙指出，谢谢。。o(￣︶￣)o

参考：

《大话数据结构》

《算法图解》

《啊哈，算法》

基数排序就这么简单