1.排序算法的描述
假设含有n个记录的序列为{r1,r2,……,rn}，其相应的关键字分别为{k1,k2,……, kn}，需确定 1，2，……，n的一种排列p1,p2,……,pn，使其相应的关键字满足kp1≤ kp2≤……≤kpn（非递减或非递增）关系，即使得序列成为一个按关键字有序的序列 {rp1,rp2,……,rpn}，这样的操作就称为排序。
对一序列对象根据某个关键字进行排序。
2.排序算法中的常用术语
（1）怎样判断排序算法的稳定与不稳定
稳定：如果a原本在b前面，而a=b，排序之后a仍然在b的前面；
不稳定：如果a原本在b的前面，而a=b，排序之后a可能会出现在b的后面；
（2）内排序与外排序
内排序：所有排序操作都在内存中完成；
外排序：由于数据太大，因此把数据放在磁盘中，而排序通过磁盘和内存的数据传输才能进行；
（3）排序算法的性能三大影响因素
1. 时间性能(时间复杂度): 一个算法执行所耗费的时间。
2. 辅助空间 (空间复杂度)：运行完一个程序所需内存的大小。
3. 算法的复杂性 : 算法本身的复杂度，而不是指算法的时间复杂度
交换排序：冒泡排序
冒泡排序（Bubble Sort）一种交换排序，它的基本思想是：两两比较相邻记录的 关键字，如果反序则交换，直到没有反序的记录为止。这个算法的名字由来是因为越大的元素会经由交换慢慢“浮”到数列的顶端。
冒泡排序的步骤：
1. 比较相邻的元素。如果第一个比第二个大(升序),就交换他们两个。
2. 对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对。这步做完后,最后的元素会是最大的数。
3. 针对所有的元素重复以上的步骤,除了最后一个。
4. 持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。
冒泡排序代码如下：
ef BubbleSort(nums): """ 冒泡排序 需要排n趟， i趟需要比较(n-i-1) :param nums: 需要排序的数值 :return: """ nums_len = len(nums) for count in range(nums_len): for index in range(nums_len-count-1): if nums[index] < nums[index+1]: nums[index], nums[index+1] = nums[index+1], nums[index] return nums if __name__ == '__main__': nums = [12, 34, 23, 45, 66, 1, 2, 0] sorted_nums = BubbleSort(nums) print(sorted_nums)
代码运行结果如下：
冒泡排序的稳定性为：稳定
交换排序:快速排序
快速排序（Quick Sort）的基本思想是：通过一趟排序将待排记录分割成独立的 两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部 分记录继续进行排序，以达到整个序列有序的目的。
层数为O(logn)(即调用栈的高度为O(logn)),而每层需要的时间为O(n)。因此整个算法需要的时间为O(n) * O(logn) = O(nlogn)
快速排序代码如下：
def quicksort(array): if len(array)<2: return array else: #递归条件 pivot = array[0] #由所有小于基准值的元素组成的子数组 less = [i for i in array[1:] if i <pivot ] #由所有大于基准值的元素组成的子数组 greater = [i for i in array[1:] if i >=pivot] return quicksort(less) + [pivot] +quicksort(greater) print(quicksort([10,5,2,3,3]))代码运行结果如下：
直接插入排序
直接插入排序（Straight Insertion Sort）的基本操作是将一个记录插入到已经排 好序的有序表中，从而得到一个新的、记录数增 1 的有序表。
直接插入排序图例如下所示：
直接插入排序代码如下：
import random def insert_sort(nums): """ 插入排序 :param nums: :return: """ # count = len(nums) # for i in range(1,count): # key = nums[i] # j= i-1 # while j>=0: # if nums[j]>key: # nums[j+1]=nums[j] # nums[j]=key # j-=1 # return nums count = len(nums) for i in range(1,count): key = nums[i] j= i-1 while j>=0: if nums[j]>key: # nums[j]=key nums[j+1]=nums[j] nums[j]=key j-=1 return nums if __name__ == '__main__': nums = [random.randint(1,100) for i in range(20)] sort_nums = insert_sort(nums) print(sort_nums)代码运行结果如下：
最好的情况,也就是要排序的表本身就是有序的, 因此没有移动的记录,时间复杂 度为 O(n)。 最坏的情况,即待排序表是逆序的情况,时间复杂度为 O(n**2)。
插入排序: 希尔排序
基本思想： 算法先将要排序的一组数按某个增量d（n/2,n为要排序数的个数）分成若干组，每组中记录的然后 再用一个较小的增量（d/2）对它进行分组，在每组中再进行直接插入排序。当增量减到1时，进行 直接插入排序后，排序完成。
希尔排序图例：
一般在记录的数量多的情况下，希尔排序的排序效率较直接插入排序高。
希尔排序代码如下：
ef shellSort(arr): n = len(arr)#n=5 gap = int(n/2)#gap=3 while gap>0: for i in range(gap,n):#range(3,5) temp = arr[i] j= i while j>=gap and arr[j-gap]>temp: arr[j]=arr[j-gap] j-=gap arr[j]=temp gap=int(gap/2) arr = [12,34,54,2,3] n= len(arr) print("排序前:") for i in range(n): print(arr[i]) shellSort(arr) print("排序后：") for i in range(n): print(arr[i])代码运行结果如下：
选择排序
选择排序(Selection sort)是一种简单直观的排序算法。它的工作原理如下。首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置,然后,再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾。以此类推,直到所有元素均排序完毕。
选择排序代码如下:
def findSmalllest(arr): smallest = arr[0] smallest_index = 0 for i in range(1,len(arr)): if arr[i] < smallest: smallest= arr[i] smallest_index = i return smallest_index def selectionSort(arr): newArr = [] for i in range(len(arr)): smallest = findSmalllest(arr) newArr.append(arr.pop(smallest)) return newArr print(selectionSort([5,3,6,2,10]))代码运行结果如下:
最优时间复杂度:O(n2 )
最坏时间复杂度:O(n2 )
稳定性:不稳定(考虑升序每次选择最大的情况)
选择排序:堆排序
堆排序是指利用堆积树（堆）这种数据结构所设计的一种排序算法，利用数组的特点快速 定位指定索引的元素。堆分为大根堆和小根堆，是完全二叉树。大根堆的要求是每个节点的 值都不大于其父节点的值。最大的值一定在堆顶。
归并排序
归并排序(Merge sort)，是创建在归并操作上的一种有效的排序算法。该算法是采用分治法 （Divide and Conquer）的一个非常典型的应用。
分治法: 分割：递归地把当前序列平均分割成两半。 集成：在保持元素顺序的同时将上一步得到的子序列集成到一起（归并）。
归并排序图例如下所示：
基数排序
基数排序（radix sort）它是透过键值的部份资讯，将要排序的元素分配至某些“桶”中，达到排序的作用，基数排序法是属于稳定性的排序，其时间复杂度为O (nlog(r)m)，其中r为所采取的基数，而m为堆数，在某些时候，基数排序法的效率高于其它的稳定性排序法。
例如：
{50，123，543，187，49，30，0，2，11，100}进行基数排序
基数排序运行代码：
def RadixSort(list): d = len(str(max(list))) for i in range(d): Bucketlist = [[] for k in range(10)] print(Bucketlist) for j in range(len(list)): Bucketlist[list[j] // (10**i) % 10].append(list[j]) list = [number for B in Bucketlist for number in B] return list if __name__ == '__main__': list1 = [810,700,821,892,846,199] print(RadixSort(list1))运行结果如下所示：
