插入排序实现&&选择排序实现

萌新刚刚开始学习算法，第一步是学习排序，毕竟算法的四大块“排序，查找，图，字符串”里面，排序是第一位的（PS：今天才知道算法提供的只是一个程序编写思路，一直以为是一个函数，难怪传入参数怎么也实现不出来，好气啊）

话不多说，先上源码！

选择排序：

 #coding:utf8

 __author__ = "zhoumi"

 class Seltsort(object):

     def __init__(self,list):

         self.list = list

     def sort(self):

         #错误示例

         # for num in self.list:

         #     for des in self.list:

         #         if des > num:

         #             continue

         #         elif des == num:

         #             continue

         #         else:

         #             tmp = num

         #             num = des

         #             des = tmp

         for i in range(len(self.list) - 1):

             for j in range(i,len(self.list)):

                 #该循环体的len(self.list)不需要-1，否则最后一个数字无法参与排序

                 if self.list[j] >= self.list[i]:

                     continue

                 else:

                     tmp = self.list[i]

                     self.list[i] = self.list[j]

                     self.list[j] = tmp

         return self.list

 if __name__ == "__main__":

     list = [123, 5493, 599, 921,264, 570, 435,444]

     st = Seltsort(list)

     print(st.sort())

萌新第一次写的时候，发现总是有最后一个数字不参与排序，把我给气的！后来经过各种折腾（写了老长老长的一段代码），还是没有解决掉，无奈只好找度娘，他告诉我算法的实现一定要注意循环体的执行次数，然后我把21行的len(self.list)-1改成了len(self.list)，大功告成！

插入排序：

 #coding:utf8

 #插入排序（默认要返回顺序递增列表），即从左往右选定基数,将该基数以所在位置为起点，从右往左比较大小

 #如果碰到a<基数<a+1，此时将基数插入

 class Insertsort(object):

     def __init__(self,list):

         self.list = list

     #错误示例

     # def sort(self):

         # #外层循环负责取base

         # for i in range(len(self.list) - 1):

         #    #内层循环负责取base左边的值

         #     for j in range(i):

         #         if  i == 0:

         #             #此时list[i]为第一个值，不需要作比较

         #             break

         #         #else负责定位比list[i]大的

         #         else:

         #             if self.list[i] < self.list[j]:

         #                 self.tmp = self.list[i]

         #                 self.count = j

         #     for k in range(self.count,i+1):

         #         if i == k:

         #             break

         #         else:

         #             self.list[i] = self.list[i-1]

         #             self.list[self.count] = self.tmp

         #             i -= 1

 #----------------------------------------------------------------------------------------------------

     def sort(self):

         for i in range(len(self.list)):

             for j in range(i+1):

                 if self.list[i] < self.list[j]:

                     tmplist = self.list[j:i+1]

                     count = i - j

                     while True:

                         if count != 0:

                             tmplist.append(tmplist.pop(0))

                             count -= 1

                         else:

                             break

                     self.list[j:i+1] = tmplist

                 else:

                     continue

         return self.list

 if __name__ == "__main__":

     list = [1,3,4,5,8,9,2,6,7,0]

     inst = Insertsort(list)

     print(inst.sort())

这段插入排序的实现相对来讲比较容易，tmplist.append(tmplist.pop[0])实现的是将末位移动至首位，例如[2,3,4,1]或者[10,11,12,9]，但是这个实现对内存的开销比较大，因为增加了一个tmplist作为缓存列表

巴特西

插入排序实现&&选择排序实现

最新文章

热门文章