本文介绍三种简单的排序算法，包括选择排序、冒泡排序和插入排序。同样每个python的排序函数都是在一个整数列表上进行操作的。

一、交换函数

   在每个排序函数中都会使用一个swap函数来交换列表中两个元素的位置。

#交换函数
def swap(lyst,i,j):
temp=lyst[i]
lyst[i]=lyst[j]
lyst[j]=temp

二、选择排序

   最简单的策略是搜索整个列表找到最小项的位置，如果该位置不是列表的第一个位置的话，则交换这两个位置的项，然后回到第2个位置并且重复这个过程。当算法到达整个过程的最后一个位置，列表就是排好序的。这个算法就是简单的选择排序。

#选择排序
def selectionSort(lyst):
i=0
while i<len(lyst)-1:
minIdex=i
        j=i+1
while j < len(lyst):            #找到最小项的位置
if lyst[j]<lyst[minIdex]:
minIdex=j
            j += 1
if minIdex != i:                #交换最小项的位置
swap(lyst,minIdex,i)
        i += 1                          #移动位置

   该函数外围循环执行n-1次，内循环次数依次递减n-1,n-2,……,1，所以总的比较次数为n（n-1）/2.

三、冒泡排序

   从列表的开头开始，并且比较一对数据项，直到移动到列表的末尾。每当成对的两项之间的顺序不正确时，算法交换其位置。这个过程的效果就是将最大的项以冒泡的方式排到列表的末尾。然后，算法从列表开头到倒数第二的位置重复这一过程，一次类推，指导该算法从列表的最后一项开始执行，此时列表已排序好。

#冒泡排序
def bubbleSort(lyst):
n = len(lyst)
while n > 1:
j=1
while j<len(lyst):
            if lyst[j-1]>lyst[j]:
swap(lyst,j-1,j)
            j += 1
n -= 1

冒泡排序和选择排序的性能相似，复杂度相同。

四、插入排序

   插入排序的思路为：在第i轮通过列表时，第i个项应该插入到列表的前i个项之中的正确位置；在第i轮之后，前i个项应该是排好序的；这个过程类似玩扑克时我们排列手中牌的顺序，即如果你按照顺序放好了前i-1张牌，抓取了第i张牌，并且将其与手中的这些牌进行比较，直到找到合适的位置。

#插入排序
def insertionSort(lyst):
i = 1
while i <len(lyst):
itemToInsert = lyst[i]
        j = i-1
while j >= 0:
            if itemToInsert < lyst[i]:
lyst[j+1]=lyst[j]
                j -= 1
else:
                break
lyst[j+1]=itemToInsert
        i += 1

   两个循环，外围循环遍历从1到n-1的位置，对于这个循环中的每一个位置i，我们都保持该项并且从位置i-1开始内部循环，对于内循环的每个位置j，我们都将项移动到位置j+1，直到找到了给保存的项（第i项）的插入位置。

   当列表中排好序的项越多，插入排序的效果越好，在最好的情况下，列表本就是有序的，插入排序的复杂度为线性的，在平均情况下仍是二次方。