每日一题之常见的排序算法

常见的排序算法

排序是最常用的算法，常见的排序算法有冒泡排序、选择排序、插入排序、快速排序、希尔排序和归并排序。除此之外，还有桶排序、堆排序、基数排序和计数排序。

1、冒泡排序

冒泡排序就是把小的元素往前放或大的元素往后放，比较的是相邻的两个元素。
时间复杂度：$O(n^2)$，空间复杂度：$O(1)$，稳定排序。
思想：
（1）比较相邻的两个元素，如果第一个比第二个大，就交换它俩的位置；
（2）对每一对相邻元素作同样的工作，从开始第一对到最后一对，一趟下来，最后的元素会是最大的数；
（3）针对所有的元素重复以上的步骤，除了最后一个；
（4）持续每次对越来越少的元素重复上面的步骤，直到没有任何一对元素需要比较。此时，该数组排好序。

def bubbleSort(list_1):len_1 = len(list_1)# 需要遍历的趟数for i in range(len_1):# 相邻元素的比较次数for j in range(len_1-i-1):# 如果第一个比第二个大，则交换两个元素的顺序if list_1[j]>list_1[j+1]:list_1[j], list_1[j+1] = list_1[j+1], list_1[j]return list_1				

改进后的排序算法，如果在一轮遍历中没有发生元素交换，就可以确定列表已经有序。可以修改冒泡排序函数，使其在遇到这种情况时提前终止。

def shortBubble(list_2):# 判断是否需要交换exchange = Falselen_2 = len(list_2)# 如果在一轮遍历中没有发生元素交换，则提前终止for i in range(len_2):exchange = Falsefor j in range(len_2-i-1):if list_2[j] > list_2[j+1]:list_2[j], list_2[j+1] = list_2[j+1], list_2[j]if not exchange:	breakreturn list_2

2、选择排序

选择排序给每个位置选择当前最小的元素。
算法思想：
（1）在所有数组中找到最小（大）元素，将其存放到数组的起始位置；
（2）在剩余元素中继续找最小（大）元素，然后依次放到已排序数组的末尾；
（3）重复操作，直到所有元素均排列好。
时间复杂度：$O(n^2)$，空间复杂度：$O(1)$，非稳定排序

def selectionSort(list_3):len_3 = len(list_3)for i in range(len_3):minIndex = ifor j in range(i+1, len_3):if list_3[j] < list_3[minIndex]:minIndex = jlist_3[i], list_3[minIndex] = list_3[minIndex], list_3[i]return list_3

3、插入排序

插入排序：在一个已经有序的小数组上，依次插入一个元素
算法思想：
（1）从第一个元素开始，该元素被认为是已经排好序的小数组；
（2）取出下一个元素，在已经排好序的小数组中从后向前遍历；
（3）如果排好序小数组的末尾元素大于待插入元素，将该末尾元素移动到下一个位置，并找小数组末尾元素的前面一个元素；
（4）重复步骤3，直到找到已排序的元素小于或等于待插入元素的位置；
（5）将待插入元素插入到该位置后，重复步骤2-5，直到该数组是有序的。
时间复杂度：$O(n^2)$，空间复杂度： $O(1)$，稳定排序

def insertionSort(list_4):len_4 = len(list_4)#遍历除第一个元素外的所有元素for i in range(1, len_4):# 若第i个元素大于i-1元素，直接插入if list_4[i] < list_4[i-1]:j = i - 1# 待插入元素value = list_4[i]while j >= 0 and value < list_4[j]:# 向后移动元素list_4[j+1] = list_4[j]j -= 1list_4[j+1] = valuereturn list_4

4、快速排序

快速排序：选取一个基准值，分成两段，左边放小于基准值的所有数，右边放大于基准值的数。
思想：
（1）选取基准值；
（2）将比基准值小的元素交换到前面，比基准值大的元素交换到后面；
（3）对左右区间重复步骤2，直到各区间只有一个数。

# 分区操作
def partition(alist, first, last):# 基准pivotVal = alist[first]# 左右两个leftMark = first + 1rightMark = lastflag = Falsewhile not flag:# 加大leftMark，直到遇到一个大于基准的元素while alist[leftMark] <= pivotVal and leftMark <= rightMark:leftMark += 1# 减少rightMark,直到遇到一个小于基准的元素while alist[rightMark] >= pivotVal and leftMark <= rightMark:rightMark -= 1# 当rightMark <leftMark时，过程终止if rightMark < leftMark:flag = Trueelse:#将rightMark对应的元素与当前位于分割点的元素互换alist[leftMark], alist[rightMark] = alist[rightMark], alist[leftMark]alist[leftMark], alist[rightMark] = alist[rightMark], alist[leftMark]return rightMarkdef quickSortHelper(alist, first, last):if first < last:mid = partition(alist, first, last)quickSortHelper(alist, first, mid)quickSortHelper(alist, mid+1, last)def quickSort(alist):quickSortHelper(alist, 0, len(alist)-1)

5、希尔排序

希尔排序是插入排序的一种变种，为了加快速度改进的插入排序，交换不相邻的元素以对数组的局部进行排序。
思想：
（1）让数组中任意间隔为 $h$ 的元素有序；
（2）刚开始 $h=length/2$；
（3）接着让 $h=length/4$，让 $h$ 一直缩小，直到 $h=1$，此时数组中任意间隔为1的元素有序。

# 对每个子序列进行插入排序，需要得到子序列的起始点和长度
def gapInsertSort(list_6, start, gap):for i in range(start+gap, len(list_6), gap):# 当前待插入元素curValue = list_6[i]j = i - gapif list_6[i] < list_6[i-gap]:while j >= 0 and curValue < list_6[j]:list_6[j+gap] = list_6[j]j -= gaplist_6[j+gap] = curValuereturn list_6def shellSort(list_6):# 获取每个子序列的长度subListLen = len(list_6) // 2# 子序列的长度要始终大于0while subListLen > 0:# 起始位置的取值for startPos in range(subListLen):# 分段进行插入排序gapInsertSort(list_6, startPos, subListLen)# 每次都将子序列的长度减少一半subListLen = subListLen // 2return list_6

6、归并排序

思想：将一个无序数组有序，首先将这个数组分成两个，然后对这两个数组分别进行排序，之后再把这两个数组合并成一个有序的数组。此时该数组就有序了。

# 合并两个有序数组
def merge(list_7, list_8):# 分别获取两个子序列的下标index1 = 0index2 = 0# 分别获取两个子序列的长度len_7 = len(list_7)len_8 = len(list_8)list_sum = []while index1 < len_7 or index2 < len_8:if list_7[index1] > list8[index2]:list_sum.append(list_8[index2])index2 += 1else:list_sum.append(list_7[index1])index1 += 1list_sum += list_7[index1:]list_sum += list_8[index2:]return list_sumdef mergeSort(list_9):# 原数组的长度不能少于2if len(list_9) < 2:return list_9# 进行二路归并mid = len(list_9) // 2# 左边进行归并排序left = merge(list_9[:mid])# 右边进行归并排序right = merge(list_9[mid:])return merge(left, right)