一、常用排序算法简介下面主要从排序算法的基本概念和原理出发，分析算法的时间复杂度、空间复杂度、稳定性和速度，等比较。根据待排序问题的大小（记录数n），排序过程中需要的内存空间也不同，因此排序算法分为两大类：[内排序]、[外排序]。内部排序：是指排序时将所有数据元素存储在计算机的随机存取存储器RAM中。外部排序：需要排序的记录数太多，内存无法一次容纳所有记录，排序过程中还需要访问外存的排序过程。首先了解常用排序算法的分类关系（见图1-1）图1-1常用排序算法2.内部排序相关算法2.1插入排序核心思想：将一个待排序的数据元素插入到先前已排序的适当位置中序列保持数据元素的顺序，直到插入所有要排序的数据元素。2.1.1直接插入排序的核心思想：比较第i个待插入数据元素的关键码与i-1,i-2,i-3,...数据元素的值之前已经排好序的，通过这种线性查找的方法找到第i个数据元素的插入位置，将原位置的数据元素的顺序向后移动，直到全部排好。在直接插入排序中，关键字相同的数据元素会保持原来的位置，所以算法是稳定的，时间复杂度的最差值为平方阶O(n2)，空间复杂度为常数阶O(l)。Python源码：#------------------------直接插入排序-------------------------------definsert_sort(data_list):#遍历数组中的所有元素，其中索引0默认排序，所以从1开始forxinrange(1,len(data_list))：#将元素依次与排序后的前序数组进行比较，如果元素小，则交换#range(x-1,-1,-1):从x-1逆序循环到0foriinrange(x-1),-1,-1):#judgment:如果满足条件，交换ifdata_list[i]>data_list[i+1]:temp=data_list[i+1]data_list[i+1]=data_list[i]data_list[i]=temp2.??1.2希尔排序的核心思想：就是将记录按照一定的下标增量进行分组，使用直接插入排序算法对每一组进行排序；随着增量逐渐减小，每组包含的关键词越来越多，当增量减为1时，整个文件刚刚被分成一组，算法终止。希尔排序的时间复杂度会优于O(n2)。但是在多次插入排序中，第一次插入排序是稳定的，但是在不同的插入排序过程中，每次Sort移动中都可能插入相同的元素，所以希尔排序是不稳定的。Python源码：#------------------------希尔排序-------------------------------definsert_shell(data_list):#初始化步长值，这里用一半的序列长度赋给它group=int(len(data_list)/2)#***layer循环：依次改变group值对list进行分组whilegroup>0:#below：利用直接插入排序的思想对分组后的数据进行排序#range(group,len(data_list)):从group开始foriinrange(group,len(data_list)):#range(x-group,-1,-group):从x-group开始与选中的元素开始反向比较，每个比较元素之间的间隔为groupforjinrange(i-group,-1,-group):#如果group中的两个元素满足交换条件，则交换ifdata_list[j]>data_list[j+group]:temp=data_list[j+group]data_list[j+group]=data_list[j]data_list[j]=temp#whileloopconditionhalfgroup=int(group/2)2.2选择性排序的核心思想：在每次扫描中，从dataelem中选择一个keycode或者***最小的元素entstosorted,并把它按照有序序列的***排序，直到所有要排序的数据元素都排完为止。2.2.1直接选择排序的核心思想：为每个位置选择键码最小的数据元素，即：选择最小的元素与第一个位置的元素交换，然后选择最小的和第一个的剩余元素中first两个位置的元素交换，直到比较倒数第二个元素和最后一个元素。根据它的基本思想，每进行一次扫描，如果当前元素比一个元素小，而这个小元素又出现在一个等于当前元素的元素后面，他们交换位置，所以直接选择排序是不稳定的，它的时间复杂度是平方阶O(n2)，空间复杂度是O(l)。Python源码：#------------------------直接选择排序------------------------------defselect_sort(data_list):#依次遍历序列中的每个元素foriinrange(0,len(data_list)):#定义本次循环中当前位置的元素的最小值valueminimum=data_list[i]#将此元素与其余元素进行比较，求最小元素forjinrange(i+1,len(data_list)):ifdata_list[j]data_list[i]):largest=left#print('左叶节点')else:largest=i#whenright当叶节点的下标小于序列长度且右叶节点的值大于父节点时，将下标赋值右叶节点的值到最大if(rightdata_list[largest]):largest=right#print('rightleafnode')#如果largest不等于i，说明当前父节点不是最大值，需要交换值if(largest!=i):temp=data_list[i]data_list[i]=data_list[largest]data_list[largest]=tempi=largest#print（最大）公司ntinueelse:break#**********建立一个大的顶层堆************defbuild_max_heap(data_list):length=len(data_list)forxinrange(int((length-1)/2),-1,-1):adjust_max_heap(data_list,length,x)#************堆排序************defheap_sort(data_list):#先建一个大顶堆，保证***值在根节点；且父节点的值大于叶节点build_max_heap(data_list)#i:当前堆中序列的长度。初始化为序列的长度i=len(data_list)#执行循环：1.每次取出堆顶元素放入序列***(len-1,len-2,len-3...)#2。调整堆，使其继续满足大顶堆的性质，注意实时修改堆中序列的长度，同时i>0:temp=data_list[i-1]data_list[i-1]=data_list[0]data_list[0]=temp#堆中序列的长度减去1i=i-1#调整大顶堆adjust_max_heap(data_list,i,0)2.3核心思想交换排序：顾名思义，就是在一组待排序的数据元素中，按照位置的先后顺序比较各自的键码。如果顺序颠倒，交换两个数据元素，直到数据元素的顺序是有序的。2.3.1冒泡排序的核心思想：对于一组待排序的数据元素，将每个数据元素看成一个带有权重的冒泡。根据轻泡不能在重泡下的原则，把顺序不对的元素全部从上到下排列。每个元素依次进行比较和调整，让较重的元素下沉，让较轻的元素上升。根据基本思想，只有当两个元素的顺序与排序要求相反时，它们的位置才会交换，否则保持不变，所以冒泡排序是稳定的。时间复杂度为平方阶O(n2)，空间复杂度为O(l)。Python源码：#------------------------冒泡排序--------------------------------defbubble_sort(data_list):length=len(data_list)#序列长度为length，需要进行length-1轮交换forxinrange(1,length):#对于每个在每一轮交换中，比较序列中的左右元素。#在每一轮交换中，由于序列中值最大的元素一定是最高的，所以每一轮循环到序列未排序的位置即可。foriinrange(0,length-x):ifdata_list[i]>data_list[i+1]:temp=data_list[i]data_list[i]=data_list[i+1]data_list[i+1]=temp2.??3.2快速排序快速排序是针对冒泡排序大幅提升的。核心思想：是一种就地排序、分而治之、大规模递归的算法。即：扫描一遍后，保证参考点的数据元素左边元素比它小，右边元素比它大，然后递归处理左右两边的元素，直到有只是参考点左右各一个元素。快速排序是一种不稳定的算法，最差值的时间复杂度为平方阶O(n2)，空间复杂度为O(log2n)。Python源码：#------------------------快速排序------------------------------#data_list：待排序的序列；start排序的起始索引，end序列末尾的索引#对于长度为length的序列：start=0;end=length-1defquick_sort(data_list,start,end):ifstart=pivot):j=j-1#移动thevaluesmallerthanpivottotheleftif(i0):maxNum=(int)(maxNum/10)times=times+1returntimes#从低位到高位数据查找numdefget_num_pos(num,pos):return((int)(num/(10**(pos-1))))%10#基数排序defradix_sort(data_list):count=10*[None]#存储每个桶的数据统计个数bucket=len(data_list)*[None]#暂存排序结果#从低到高依次执行循环forposinrange(1,radix_sort_nums(data_list)+1):#设置每个桶的空数据统计forxinrange(0,10):count[x]=0#统计当前位置的元素个数(个位、十位、百位...)forxinrange(0,len（数据列表）):#统计每个桶要加载的元素个数j=get_num_pos(int(data_list[x]),pos)count[j]=count[j]+1#count[i]表示右边界第i个bucketIndexforxinrange(1,10):count[x]=count[x]+count[x-1]#将数据依次放入bucketforxinrange(len(data_list)-1,-1,-1):#seekThenumberj=get_num_pos(data_list[x],pos)#将元素第K位的数放入对应的桶中，count[j]-1为第j个桶的右边界索引bucket[count[j]-1]=data_list[x]#对应bucket的加载数据索引-1count[j]=count[j]-1#将已分配的bucket中的数据倒出，并现在是对应当前位数的有序表forxinrange(0,len(data_list)):data_list[x]=bucket[x]三、排序算法测量图3-1常用排序算法测试统计四、排序算法对比分析表4-1排序算法对比【直插排序】是对冒泡排序的改进，速度比冒泡排序快，但只适合小数据量（1000）的排序【希尔排序】比较简单，适合小数据量的排序（下图）5000)，比直接插入排序和冒泡排序快。因此，希尔排序适用于数据量小、排序速度要求不高的排序[直接选择排序]与冒泡排序算法相同，适用于n值较小的场合，是发展的初级阶段排序算法，在实际应用中使用的概率较小。【堆排序】比较适合百万级以上数据量的排序。在这种情况下，使用递归设计的快速排序和归并排序时，可能会出现栈溢出。【冒泡排序】是最慢的排序算法，是排序算法发展的初级阶段。在实际应用中使用该算法的概率比较小。【快速排序】是一种递归最快的排序算法，但在内存有限的情况下不是一个好的选择；而且，对于排序基本有序的数据序列，快速排序反而变慢了。[归并排序]比堆排序快，但需要双倍的存储空间。【基数排序】适用于n值较大的情况，但只适用于整数排序。如果对浮点数进行基数排序，必须指定浮点数的存储格式，然后通过一定的方式映射到整数，***再映射回去，过程比较复杂。
