排序算法的应用
选择排序，冒泡排序
之前在学习时，对选择排序和冒泡排序做过专门的记录（https://www.cnblogs.com/honor260/p/14040208.html） ，因为这两种排序比较经典，而且我在做题过程中遇到不少变种的情况。排序的核心其实就是一句话，让合适的位置放置合适的值，但是实现起来却有不同的方式，我理解的选择排序其实就是每次在选择一个最值，把它放到该在的位置，然后再在剩下的序列中为下一个位置寻找合适的值。比如我遇到的两道题目（题目有更好的解法，这里用选择排序解是为了体现选择排序的应用，从而可以探究其算法思想的实质）其中一个要求输出前k个最小的数，另一个则是组合字符串的问题，其实都可以用选择排序解决。
题目一：输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4。
这道题我最初是用选择排序解的，因为在读完题目后，我看到k，第一反应就是：这不就是要把最小的k个数挑出来吗？而选择排序就是每次都把最值挑出来，然后放到应该在的位置（一般是从位置0到位置n，从前往后往上面选择放置最值）。所以我有了下面的解法：
class Solution:
def GetLeastNumbers_Solution1(self, tinput, k):
#方法1，使用排序然后输出前k个数
# write code here
if len(tinput)<k:
return []
listt=sorted(tinput)
return listt[:k]
def GetLeastNumbers_Solution(self,tinput,k):
#方法2：选择排序改进版，选择最小的数，选择k次
if len(tinput)<k:
return []
if k==len(tinput):
tinput.sort()
return tinput
for i in range(k):
for j in range(i,len(tinput)):
if tinput[i]>tinput[j]:
tinput[i],tinput[j]=tinput[j],tinput[i]
return tinput[:k]代码内容
题目二：输入一个正整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。例如输入数组{3，32，321}，则打印出这三个数字能排成的最小数字为321323。
该题的解法大体分为两种，一种是用选择排序的方法。我们观察组合的数字发现，个位数越大的数，在组合得到的数中其位就越低，比如321-1，32-1，3-3，排列成为新数字时，321就应该在最高位，而3则在最低位。这种解法正是典型的选择排序，即把个位大的数排在后面（如果把地位视为后面，把高位视为前面的话）。实现方法如下（两个函数都是选择排序的思想，第二种更加简洁）：
class Solution:
def PrintMinNumber1(self, numbers):
# write code here
if len(numbers)==0:
return ""
if len(numbers)==1:
return numbers[0]
minum=self.min(numbers)
while numbers:
minum=str(self.min(numbers))+str(minum)
return int(minum)
def min(self,numbers):
#获取列表中个位最大的数作为个位
max=numbers[0]
for i in numbers:
if (max%10)<(i%10):
max=i
return numbers.pop(numbers.index(max))
def PrintMinNumber(self,ns):
#利用选择排序的思想
if len(ns)==0:
return ""
for i in range(len(ns)):
for j in range(i,len(ns)):
if ns[i]%10<ns[j]%10:
ns[i],ns[j]=ns[j],ns[i]
minu=""
for i in ns:
minu=str(i)+minu
return int(minu)
其实想到选择排序，就可以想到冒泡排序，我参考其他牛友的解答，发现还有一种排序方法，对于两个数 n1和n2，根据排序n1n2和n2n1的方式比较，如果n1n2>n2n1，则证明n2应该排在n1前面；根据这种思想把相邻的两个数按照如上规则进行比较，然后用冒泡排序的算法排序。这里就不用具体的代码实现了。其实不论那种思路，都是将这个问题转换为排序问题，而一旦拖入排序领域，那么解决起来就比较熟悉了。
这里提供一种大神的浓缩解法，利用sort方法精简python代码，算法核心还是排序。
class Solution:
def PrintMinNumber(self, numbers):
# write code here
if not numbers: return ""
numbers = list(map(str, numbers))
numbers.sort(cmp=lambda x, y: cmp(x + y, y + x))
return "".join(numbers).lstrip('0') or'0'