算法笔记（一）排序之桶排序和插入排序

小咪咪 2022-06-15 05:37 151阅读 0赞

# 什么是算法 #

百度百科中的定义是这样的，算法（Algorithm）是指解题方案的准确而完整的描述，是一系列解决问题的清晰指令，算法代表着用系统的方法描述解决问题的策略机制。  
      个人理解算法是用来解决某一个或者某一列问题的方案方法，在我们的生活中算法无处无处不在，处处体现着算法的运用，比如你要去某一个目的地，到达目的地有好几条路，我们都会自己选择最近的路走，在这个选择的过程中其实也用了算法。

有大有小并不是越复杂的算法实用价值就高，一个算法的实用性是由使用该算法人的多少，解决的问题来决定的，如01背包问题解决了当某个条件最大时，价值最大的问题；最长公共子序列解决了DNA相似性程度，为预防疾病做出了贡献。

# 算法由来 #

关于算法的由来存在着集中不同的说法，一种认为比较多的说法是来自于《波斯教科书》作者的名字，在里面最早的含义仅仅表示数字的四则运算，并没有今天代表的这么多含义，在文化不断发展过程中1950年出来了欧几里德运算，而且两者慢慢练习在一起，随后的研究过程中，逐渐把一些规律性的问题称之为算法Algorithm，从算法产生来看也就是80年左右的历史，所以我们现在学习的是80年的结晶，学习算法是一件很有意义的事情。

# 为什么要学习算法 #

难道我们学习算法只是为了应付考试、用来面试、用来炫耀么，这样的目的显示很世俗，但谁不想去谷歌、百度、BAT这样的大公司呢，算法似乎是这些公司必问的一项内容，如果你懂得多就有可能得到更多的机会。

算法就像内功修炼一样，是一种外在表现不出来的修养，同各种类型工具、UI外在的招式相比不好修炼、有一定难度所以它经久不衰，想想从计算机诞生到现在各种技术层出不穷，如前端框架jquery、ext、bootstrap等，还有各种后端开发框架，这里就不一一列举了，唯一不变的就是算法，从古代武装电视剧我们就可以得出来结论，只学习一些外在招式而不注重内在修炼很难成为武功大成者，他们有相似的道理。  
      我们从排序算法入手，看一下桶排序和插入排序。

# 桶排序 #

## 原理 ##

它的原理很好理解，数组元素值表示数字出现的次数，下标表示该数字大小，把数组打印出来就可以得到排好序的列表，它的排序速度也是很快，桶排序是最快、最简单的排序，但它可能浪费的空间也是最多的，假如排序中最大数是10000，那么需要分配10001长度的存放数据，里面大部分空间是浪费的，如下图所示：

![这里写图片描述][SouthEast]

## 实现思路 ##

1.  已知有一个五个数组成的整型数组a\[5,7,2,1,7\]，现从小到大排序
2.  初始化元素都为0的数据b\[\]，最大index为已知数组最大值+1
3.  根据下标给b\[\]数组元素赋值，如果b下标每出现次b\[index\]+1
4.  打印b\[\]数组下标（b\[index\]十几就打印几次）

### java版 ###

public static List<Integer> bucketSortedList(int[] arrayParamList){
            List<Integer> sortedInt = new ArrayList<Integer>(arrayParamList.length);
    
            int[] arrayBucket = new int[11];
            for (int element : arrayParamList){
                arrayBucket[element] = arrayBucket[element]+1;
            }
    
            for (int i = 0;i < arrayBucket.length; i++){
                if (arrayBucket[i] != 0){
                    for (int j = 1;j <= arrayBucket[i];j++){
                        sortedInt.add(i);
                    }
                }
            }
    
            return sortedInt;
        }

### python 版 ###

1 def bucket_sort():
      2         deflist = [2,5,7,8,3,9]
      3 
      4         bucketList = []
      5         for i in range(10):
      6                 bucketList.append(0)
      7                 print("i="+str(i))
      8         for element in deflist:
      9                 bucketList[element] = bucketList[element] + 1
     10                 print("element="+str(element))
     11 
     12         result = []
     13         for j in range(len(bucketList)):
     14                 print("j="+str(j))
     15                 if (bucketList[j] != 0):
     16                         for t in range(bucketList[j]):
     17                                 result.append(j)
     18         return result
     19

# 插入排序 #

## 原理 ##

插入排序的原理是通过不断比较不断寻找元素的最适合插入位置，为每一个元素和前面的元素比较，如果不符合排序规则，则交换位置，有一个网站上面有一栋的动态图，帮助我们理解一栋过程，下面是一个静态图，它是按从小到大排序第一次12和15比较，12<15故不进行移动；第二次9移动到了首位置，其它这里比较了两次分为和12、15，由于9小于12、15，两次交换位置，插入排序优点是快，但是比较次数不能确定，最坏是将递增序列按递减排，每个元素都需要移动和比较，如下图：

![这里写图片描述][SouthEast 1]

## 实现思路 ##

1.  访问每次元素，确定它的位置是否正确
2.  当前元素与前面元素逐个比较，找到自己的合适位置
3.  每个元素都找好位置之后，排序也就排好了

### java代码 ###

public static int[] insertSortedList(int[] arrayParamList){
    
            for (int i = 1; i < arrayParamList.length;i++){
                System.out.println("i="+i);
                //循环计数变量
                int j = i - 1;
                //欲插入数据变量
                int target = arrayParamList[i];
    
                //错误代码
    // for (j=i-1;j >= 0 ;j--){ 
    // if (arrayParamList[j] > target){ 
    // arrayParamList[j+1] = arrayParamList[j];
    // }
    // }
                //找适当的插入位置
                while (j>=0 && arrayParamList[j] > target){
                    arrayParamList[j+1] = arrayParamList[j];
                    j--;
                }
                //将变量插入
                arrayParamList[j+1]=target;
            }
    
            return arrayParamList;
        }

开始在写代码时，位置比较和交换利用for () \{\}循环比较的，发现总是不对，问题在于每次循环之后j都会自动减1，也就是说不小于时也往前移动了，这就会有问题，这里使用while循环还是比较合适的，满足比较天剑才移动位置，算法代码要多写、多思考才能更完善。

### python代码 ###

1 def insert_sort():
      2         defList = [7,4,8,2,4,5]
      3         print("length="+str(len(defList)))
      4         for i in range(1,len(defList)):
      5                 print("i="+str(i))
      6                 j = i - 1
      7                 target = defList[i]
      8                 while j >= 0 and defList[j] > target :
      9                         defList[j+1] = defList[j]
     10                         j -= 1
     11                 defList[j+1] = target
     12 
     13         for m in defList:
     14                 print("m="+str(m))
     15

# 总结 #

经常学习有益于大脑活跃，开发智力提神益脑；算法有助我们提高编码质量、效率；它是一种几百年智慧的结晶，从小里面说懂算法的人也是懂生活的人，算法里面蕴含着很多优秀思想，需要慢慢体会理解，然后运用到工作、生活中去。

[SouthEast]: /images/20220615/bbe119bdbede43899b8e5f9859dc7b65.png
[SouthEast 1]: /images/20220615/d19588feb8a747148512b32a3dc1046e.png