python数据结构与算法--排序
1、常用排序算法
| 排序算法 | 平均时间 | 最差情形 | 稳定度 | 备注 |
|---|---|---|---|---|
| 快速排序 | O(nlogn) | O(n^2) | 不稳定 | n大时较好 |
| 冒泡排序 | O(n^2) | O(n^2) | 稳定 | n小时较好 |
| 选择排序 | O(n^2) | O(n^2) | 不稳定 | n小时较好 |
| 插入排序 | O(n^2) | O(n^2) | 稳定 | 大部分已排好序时较好 |
| 归并排序 | O(nlogn) | O(nlogn) | 稳定 | n大时较好 |
| 希尔排序 | O(nlogn) | O(n^s) 1<s<2 | 不稳定 | s是所选分组 |
2、快速排序法
-
基本思想：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。注：快速排序不是一种稳定的排序算法，也就是说，多个相同的值的相对位置也许会在算法结束时产生变动。
-
一趟快速排序算法（首先任意选取一个数据（通常选用数组的第一个数）作为关键数据，然后将所有比它小的数都放到它前面，所有比它大的数都放到它后面）步骤：
1）设置两个变量i、j，排序开始的时候：i=0，j=N-1（列表长度最后一个元素下标）；
2）以第一个列表元素作为关键数据，赋值给key，即key=A[0]；
3）从j开始向前搜索，即由后开始向前搜索(j-=1)，找到第一个小于key的值A[j]，将A[j]和A[i]互换；
4）从i开始向后搜索，即由前开始向后搜索(i+=1)，找到第一个大于key的A[i]，将A[i]和A[j]互换；
5）重复第3、4步，直到i=j； (3,4步中，没找到符合条件的值，即3中A[j]不小于key,4中A[i]不大于key的时候改变j、i的值，使得j=j-1，i=i+1，直至找到为止。找到符合条件的值，进行交换的时候i， j位置不变。另外，i=j这一过程一定正好是i+或j-完成的时候，此时令循环结束）。
-
示例：
假设用户输入了如下数组：
下标 0 1 2 3 4 5 数据 6 2 7 3 8 9 创建变量i=0（指向第一个数据）, j=5(指向最后一个数据), key=6(赋值为第一个数据的值)。
（1）要把所有比key小的数移动到key的左面，故先开始寻找比6小的数，从j开始，从右往左找，不断递减变量j的值(j-=1)，找到第一个下标3的数据比6小，于是把数据3移到下标0的位置(A[i]=A[j])，把下标0的数据6移到下标3，完成第一次比较：
下标 0 1 2 3 4 5 数据 3 2 7 6 8 9 （2）i=0，j=3，key=6，第二次比较（通俗来说：移动指针从j开始的，而因为第一个比较时，找到了值比key小，故该值由key的右边移到了左边，称做发生了“交叉变换”行为，故移动指针变为i了，要去找比key大的值了；说明：之后每发生一次所谓的“交叉变换”，移动指针都要变化的），移动指针为i，从前往后找，递加变量i，发现下标2的数据是第一个比key大的，于是用下标2的数据7和j指向的下标3的数据的6做交换，数据状态变成下表：
下标 0 1 2 3 4 5 数据 3 2 6 7 8 9 （3）i=2，j=3，key=6，移动指针变为j，故递减变量j，不断重复进行上面的循环比较。
（4）直到i=j：都指向了下标2。于是，第一遍比较结束。得到结果如下，凡是key(=6)左边的数都比它小，凡是key右边的数都比它大：
下标 0 1 2 3 4 5 数据 3 2 6 7 8 9 如果i和j没有碰头的话，就递加i找大的，还没有，就再递减j找小的，如此反复，不断循环。注意判断和寻找是同时进行的。然后，对key两边的数据，再分组分别进行上述的过程，直到不能再分组为止。
注意：第一遍快速排序不会直接得到最终结果，只会把比key大和比key小的数分到key的两边。为了得到最后结果，需要再次对下标2两边的数组分别执行此步骤，然后再分解数组，直到数组不能再分解为止（只有一个数据），才能得到正确结果。
-
Python代码
def quickSort_main(data_list,i,j):#快速排序法主调用程序,调用开始时i=1,j=len(data_kist)-1 if i < j: split_point = quickSort_spec(data_list,i,j) quickSort_main(data_list,i,split_point) #递归 quickSort_main(data_list,split_point+1,j) def quickSort_spec(data_list,i,j):#快速排序具体过程 key = data_list[i] while i < j: while i < j and data_list[j]>=key: j-=1 data_list[i] = data_list[j]#不在循环里了，即data_list[j]<key，要将j下标对应的值放到i位置 while i < j and data_list[i]<=key: i +=1 data_list[j] = data_list[i]#不在循环里了，即data_list[i]>key，要将i下标对应的值放到j位置 data_list[i] = key #此时i=j，即找到了key要放的位置 return i #返回key所在下标位置 >>>data_list = [54, 26, 93, 17, 77, 31, 44, 55, 20] >>>quickSort_main(data_list,0,len(data_list)-1) >>>print(data_list) [17, 20, 26, 31, 44, 54, 55, 77, 93]
3、冒泡排序法
-
基本思想
每个回合都从第一个元素开始和它后面的元素比较，如果比它后面的元素更大的话就交换，一直重复，直到这个元素到达了所进行排序元素的最后位置。继续重复操作，每次遍历都会将剩下的元素中最大的那个放到了序列的“最后”(除去了前面已经排好的那些元素)，即排序一次后大的元素会经由交换慢慢“浮”到数列的顶端（冒泡命名的来源）。算法时间复杂度为O(n^2)
-
步骤
（1）比较相邻的元素。如果第一个比第二个大，就交换他们两个。
（2）对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
（3）针对所有的元素重复以上的步骤，除了最后一个。
（4）持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
-
示例
冒泡排序
上图为一轮排序，可见一轮排序后，最大的元素93会"浮"到顶端，下一轮排序则对（26,54,17,77,31,44,55,20）进行，以此重复，直到没有元素
-
Python代码
def bubble_sort(data_list):#冒泡排序法 length = len(data_list) exchanges = True while length > 0 and exchanges: exchanges = False for i in range(length-1): if data_list[i]>data_list[i+1]: exchanges = True #python中可直接交换两个变量,而不需引入临时变量temp来交换 data_list[i],data_list[i+1] = data_list[i+1],data_list[i] length-=1 #一轮排序后，已放置好的那个元素不需要再参与下一轮的排序 >>>data_list = [5, 3, 7, 9, 6, 1, 10] >>>bubble_sort(data_list) >>>print(data_list) [1, 3, 5, 6, 7, 9, 10] #增加exchanges作为标识，即如果有一趟排序中没有产生交换的话，那么说明此刻数列以及变成了有序的数列，如：5，1，2，3，4，冒泡一次之后就变成了：1，2，3，4，5，已经有序了，我们没有必要再去比较了。
4、选择排序法
-
基本思想
每个回合都选择出剩下的元素中最小（大）的那个，选择的方法是首先默认第一元素是最小（大）的，如果后面的元素比它小（大）的话，那就更新当前的最小（大）的元素值，直到找到最后，把当前参与排序中的第一个元素和找到的那个最小（值）所在的位置交换。以此重复排序，直到排序完成。时间复杂度O(n^2)，选择排序法是不稳定排序算法。
-
步骤
（1）在待排序记录A[1]~A[n]中选出最小的记录，将它与A[1]交换
（2）在待排序记录A[2]~A[n]中选出最小的记录，将它与A[2]交换
（3）以此类推，第i趟在待排序记录A[i]~A[n]中选出最小的记录，将它与A[i]交换，使有序序列不断增长直到全部排序完毕。
-
示例
初始序列：{49 27 65 97 76 12 38} ，其中大括号内为无序区，大括号外为有序序列
第1趟：先假设第一个元素49是最小的，然后不停往后比较，找到12是当前最小的元素，则将12与49交换：12{27 65 97 76 49 38}
第2趟：在剩余元素中假设27最小的，不停查找到最后，27还是最小的，故保持27不动 ：12 27{65 97 76 49 38}
第3趟：方法同上，此处是65与38交换：12 27 38{97 76 49 65}
第4趟：方法同上，此处是97与49交换：12 27 38 49{76 97 65}
第5趟：方法同上，此处是76与65交换：12 27 38 49 65{97 76}
第6趟：方法同上，此处是97与76交换：12 27 38 49 65 76 97 完成
-
Python代码
def select_sort(data_list):#选择排序法 length = len(data_list) for i in range(length): min_index = i #记录最小元素的下标（每次都是把参与排序的第一个元素先作为最小值） for j in range(i+1,length): #在i+1开始一直往后查找最小值 if data_list[j] < data_list[min_index]: min_index = j #找到了更小的值，故当前最小元素下标变为了j if min_index != i: #min_index=i时,是不用交换的 data_list[i],data_list[min_index] = data_list[min_index],data_list[i] #每次交换，都是把找到的最小值放在参与排序元素里的第一位 >>>data_list = [5, 3, 7, 9, 6, 1, 10] >>>select_sort(data_list) >>>print(data_list) [1, 3, 5, 6, 7, 9, 10]
5、插入排序法
-
基本思想
输入一个元素，检查数组列表中的每个元素，将其插入到一个已经排好序的数列中的适当位置，使数列依然有序，当最后一个元素放入合适位置时，该数组排序完毕。
-
示例
假设用户输入序列为[7，3，1，4，8] （目标：判断数字有没有在正确的位置上，做法：与左边的数字对比）
（1）首先从第二个数字3开始，看看3有没在正确的位置上，与7对比，比7小，故交换位置，此时序列变为
[3，7，1，4，8]
（2）看看第三个数字1是否在正确的位置上，与7比较，比7小，故与7交换，再与左边的3比较，比3小，再次与3交换，此时序列变为[1，3，7，4，8]
（3）看看第四个数字4是否在正确的位置上，与7比较，比7小，故与7交换，再与左边的3比较，比3大，不用交换了，此时序列变为[1，3，4，7，8]
（3）看看第五个数字8是否在正确的位置上，与7比较，比7大，不用交换了，元素遍历完毕，排序完成
-
Python代码
def insert_sort(data_list):#插入排序法 length = len(data_list) for i in range(1,length): #从第二个元素开始寻找其“正确”位置 key = data_list[i] #设置当前元素值为key j = i - 1 #与当前值key的前一个元素对比 while j >= 0 and data_list[j] > key: data_list[j+1] = data_list[j] #前一个元素大于当前值key,则将前一个元素后移一位 j-=1 data_list[j+1] = key #j+1即为当前值key的合适位置 return data_list >>>data_list = [5, 3, 7, 9, 6, 1, 10] >>>print(insert_sort(data_list)) [1, 3, 5, 6, 7, 9, 10]
6、归并排序法(合并排序法)
-
基本思想
典型的是二路合并排序，将原始数据集分成两部分(不一定能够均分)，分别对它们进行排序，然后将排序后的子数据集进行合并，这是典型的分治法策略（分治思想是将每个问题分解成个个小问题，将每个小问题解决，然后合并）。时间复杂度O(nlogn)
-
步骤
（1）：将n个元素分成两个含n/2元素的子序列
（2）：用归并排序法将两个子序列递归排序（最后可以将整个原序列分解成n个子序列）
（3）：合并两个已排序好的子序列（合并的过程是将两个子序列排序，合成一个有序的序列）
-
示例
假设输入序列为[54, 26, 93, 17, 77, 31, 44, 55, 20]
（1）首先将序列拆分成二等分：[54,26,93,17]和[77, 31, 44, 55, 20]
（2）对左边的序列[54,26,93,17]继续执行拆分，分为[54,26]和[93,17]，再递归拆分，分为[54]和[26]，此时序列中均只剩一个元素了，则进行合并比较操作，54>26，result=[26,54]
（3）再对右边序列[93,17]拆分，分为[93]和[17]，序列中均只剩一个元素了，故进行合并比较操作，93>17，result=[26,54]
（4）对（2）（3）步得到的序列[26,54]和[17,93]递归合并排序（在此讲述一次合并步骤，其他不再赘述），首先i=0，j=0，26>17，故在result=[ ]中加入17，此时移动指针变为j，故j+=1；再继续比较，26<93，在result中加入26，则result=[17,26]，这时移动指针变为i了，故i+=1；再继续比较54和93，54<93，在result中加入54，则result=[17,26,54]；此时左边序列已遍历完，故可直接将右边序列元素加到result后面了，即result += right[j:]，得到result=[17,26,54,93]
（5）{77, 31, 44, 55, 20}操作也同理，得到[20,31,44,55,77]
（6）最后对[17,26,54,93]与[20,31,44,55,77]进行合并排序即可
归并排序
归并排序2
-
Python代码
def merge_sort(data_lists): # 归并排序 if len(data_lists) <= 1:#只有一个元素时,不进行切分,而是返回列表，紧接着开始第一次merge return data_lists num = int(len(data_lists) / 2)#每次都是二等分 left = merge_sort(data_lists[:num])#递归执行:拆分成二等份步骤 right = merge_sort(data_lists[num:]) return merge(left, right) def merge(left, right): i, j = 0, 0 result = [] while i < len(left) and j < len(right): if left[i] < right[j]: result.append(left[i]) i += 1 else: result.append(right[j]) j += 1 #退出循环时，表left或者right有一个已经遍历完毕。假设right遍历完毕，则是将剩余的left里的值全部添加到result中，此时right[j:]为[]的 result += left[i:] result += right[j:] return result >>>a_list = [54, 26, 93, 17, 77, 31, 44, 55, 20] >>>print(merge_sort(a_list)) [17, 20, 26, 31, 44, 54, 55, 77, 93]
7、希尔排序法
-
基本思想
是插入排序的一种。也称缩小增量排序，是直接插入排序算法的一种更高效的改进版本。其先取一个小于n的整数d1作为第一个增量，把文件的全部记录分组。所有距离为d1的倍数的记录放在同一个组中。先在各组内进行直接插入排序；然后，取第二个增量d2<d1重复上述的分组和排序，直至所取的增量dt=1（dt<dt-1<...<d2<d1）即所有记录放在同一组中进行直接插入排序为止。（实质是分组插入）
-
示例
假设用户输入[49,38,65,97,76,13,27,49,55,04]，
（1）第一趟初始增量d1=10/2=5，即将10个待排记录增量分为5个子序列，分别为[49,13]，[38,27]，[65,49]，[97,55]，[76,04]
（2）对上述5个分组分别进行插入排序（具体插入排序步骤看上面讲述），每次排序时插回原序列对应的位置中，如[49,13]，开始时49下标为0，13下标为5，而13<39，故排序后，下标0的位置是13，而49移动到原来13所在的下标位置5，其他同理，第一趟排序后序列变为[13,27,49,55,04,49,38,65,97,76]
（3）缩小增量d2=5/2=2，即将第一趟排序后的序列分为2组，分别为[13,49,04,38,97]，[27,55,49,65,76]
（4）对上述2个分组分别进行插入排序（具体插入排序步骤看上面讲述），第2趟排序后序列变为[04,27,13,49,38,55,49,65,97,76]
（5）缩小增量d3=2/2=1，即将第二趟排序后的序列分为1组，[04,27,13,49,38,55,49,65,97,76]
（6）对上述分组[04,27,13,49,38,55,49,65,97,76]进行插入排序，第3趟排序后序列变为[04,13,27,38,49,49,55,65,76,97]
希尔排序
-
Python代码
def shell_sort(a_list):#希尔排序 sublist_count = len(a_list) // 2 #增量因子d while sublist_count > 0: for start_position in range(sublist_count): gap_insertion_sort(a_list, start_position, sublist_count) #按照d分组后得到的值进行插入排序 print("增量因子为：", sublist_count, " 排序后列表为:", a_list) sublist_count = sublist_count // 2 #增量因子d=1时,完成所有排序 def gap_insertion_sort(a_list, start, gap):#插入排序法的步骤 for i in range(start + gap, len(a_list), gap): #从第二个增量后的值start+gap开始进行插入排序 current_value = a_list[i] position = i while position >= gap and a_list[position - gap] > current_value: a_list[position] = a_list[position - gap] position = position - gap a_list[position] = current_value >>>a_list = [54, 26, 93, 17, 77, 31, 44, 55, 20] >>>shell_sort(a_list) print(a_list) 增量因子为： 4 排序后列表为: [20, 26, 44, 17, 54, 31, 93, 55, 77] 增量因子为： 2 排序后列表为: [20, 17, 44, 26, 54, 31, 77, 55, 93] 增量因子为： 1 排序后列表为: [17, 20, 26, 31, 44, 54, 55, 77, 93] [17, 20, 26, 31, 44, 54, 55, 77, 93]
