说明：
用Python实现十大排序算法，仅有简单解释，无算法的详细介绍。
相关术语：
稳定排序：如果a原本在b的前面，且a==b，排序之后a仍然在b的前面，则为稳定排序。
非稳定排序：如果a原本在b的前面，且a==b，排序之后a可能不在b的前面，则为非稳定排序。
原地排序：指在排序过程中不申请多余的存储空间，只利用原来存储待排数据的存储空间进行比较和交换。
非原地排序：需要利用额外的数组来辅助排序。
排序算法（默认从小到大进行排序）：
选择排序、插入排序、冒泡排序、希尔排序、归并排序、快速排序、堆排序、基数排序、桶排序、基数排序
1.选择排序
步骤：
1.找到数组中最小的元素
2.将它和数组中的第一个元素交换位置
3.在剩下的元素中找到最小的元素，将它与数组中的第二个元素交换位置
4.重复以上操作，直到将整个数组排序
def selectSort(arr): length = len(arr) for i in range(length-1): min_index = i for j in range(i+1,length): if arr[j] < arr[min_index]: min_index = j arr[i], arr[min_index] = arr[min_index], arr[i] return arr
性质：时间复杂度：O(n2)、空间复杂度：O(1)、非稳定排序、原地排序
2.插入排序
步骤：
1.从数组的第2个元素开始抽取
2.将它与左边的第一个元素比较，如果左边第一个元素比它大，则继续与左边第二个元素比较，直到遇到不比它大的元素，插入到该元素的右边
3.继续抽取第3、4、5……n个元素，重复步骤2，选择适当的位置插入
def insertSort(arr): length = len(arr) for i in range(1,length): j = i - 1 while j >= 0 and arr[j] > arr[i]: j -= 1 t = arr.pop(i) arr.insert(j+1,t) return arr
性质：时间复杂度：O(n2)、空间复杂度：O(1)、稳定排序、原地排序
3.冒泡排序
步骤：
1.把第一个元素和第二个元素进行比较，如果第一个比第二个大，则交换他们的位置
2.比较第二个元素和第三个元素，如果第二个比第三个大，则交换位置
3.一直比较到数组的最后一个元素，这样一趟交换下来，最后一个元素就会是最大的数
4.除去最后一个元素，对剩余的元素重复以上操作，直到排序完成
def bubbleSort(arr): length = len(arr) for i in range(length): for j in range(length-i-1): if arr[j] > arr[j+1]: arr[j], arr[j+1] = arr[j+1], arr[j] return arr
性质：时间复杂度：O(n2)、空间复杂度：O(1)、稳定排序、原地排序
4.希尔排序
步骤：
1.将较大的数据集分为若干小组，比如第一组：[0,h,2h,3h……]、第二组：[1,h+1,2h+1……]……(这里h为增量)
2.轮流对每一小组进行插入排序，使得整个数组部分有序
3.令h=h/2，重新进行分组，轮流对每一小组进行插入排序
4.重复3操作，直到h=1,即整个数组被分为一组
5.对这一组数据进行排序
def ShellSort(arr): length = len(arr) gap = length // 2 while gap > 0: for i in range(gap,length): insertI(arr,gap,i) gap = gap // 2 return arr def insertI(arr,gap,i): temp = arr[i] j = i - gap while j >= 0 and temp < arr[j]: arr[j+gap] = arr[j] j = j - gap arr[j+gap] = temp
性质：时间复杂度：O(nlogn)、空间复杂度：O(1)、非稳定排序、原地排序
5.归并排序
步骤：
1.将待排序的数组分为两个后分别排好序，再将排好序的两个数组合并成一个有序数组
2.可以将数组一直分割，直到数组的大小为1，此时只有一个元素，那么该数组即为有序的
3.再将两个大小为1的数组合并成一个大小为2的，再把大小为2的数组合并成一个大小为4的……直到全部合并
def mergerSort(arr): n = len(arr) if n == 1: return arr mid = n // 2 left = mergerSort(arr[:mid]) right = mergerSort(arr[mid:]) return mergeArray(left,right) #合并两个有序数组 def mergeArray(arr1,arr2): n1 = len(arr1) n2 = len(arr2) temp = [] i = 0 j = 0 while i <= n1-1 and j <= n2-1: if arr1[i] < arr2[j]: temp.append(arr1[i]) i += 1 else: temp.append(arr2[j]) j += 1 if i <= n1-1: temp.extend(arr1[i:]) if j <= n2-1: temp.extend(arr2[j:]) return temp
性质：时间复杂度：O(nlogn)、空间复杂度：O(n)、稳定排序、非原地排序
6.快速排序
步骤：
1.选取数组的某个元素，称之为主元
2.将大于等于主元的元素放到主元的右边，将小于主元的元素放到主元的左边
3.主元把数组分成了两部分，采用递归，对左右两部分分别采取1、2步骤，直到子数组只有1个或0个元素
def quickSort(arr): return q_sort(arr, 0, len(arr)-1) #选取第一个元素作为主元 def q_sort(arr, left, right): if left < right: mid = Partition(arr, left, right) arr = q_sort(arr, left, mid - 1) arr = q_sort(arr, mid + 1, right) return arr def Partition(arr, left, right): pivot = arr[left] i = left + 1 j = right while i <= j: while i <= j and arr[i] < pivot: i += 1 while i <= j and arr[j] > pivot: j -= 1 if i >= j: break arr[i],arr[j] = arr[j], arr[i] arr[left] = arr[j] arr[j] = pivot return j
性质：时间复杂度：O(nlogn)、空间复杂度：O(logn)、非稳定排序、原地排序
7.堆排序
堆顶的元素是堆的最大值或最小值，这里考虑大顶堆。
步骤：
1.将堆顶元素与最后一个元素互换
2.破坏了堆的特性后，将剩余元素再次构成一个大顶堆
3.将堆顶元素与最后第二个元素互换
4.重复以上操作，直到剩余一个元素，则完成排序
def headSort(arr): #构建堆 length = len(arr) t = (length - 2) // 2 for i in range(t,-1,-1): #下标不包含-1 downHead(arr,i,length-1) #互换后下沉进行堆排序 for i in range(length-1,0,-1): arr[0], arr[i] = arr[i], arr[0] downHead(arr,0,i-1) return arr def downHead(arr,parent,length): temp = arr[parent] #左孩子 child = 2 * parent + 1 while child <= length: #定位到较大的孩子 if child + 1 <= length and arr[child+1] > arr[child]: child += 1 if temp > arr[child]: break arr[parent] = arr[child] parent = child child = 2 * parent + 1 arr[parent] = temp
性质：时间复杂度：O(nlogn)、空间复杂度：O(1)、非稳定排序、原地排序
8.计数排序
计数排序适合最大值和最小值的差值不是很大的排序
步骤：
1.找出数组中的最大值和最小值
2.构建一个长度为(max-min+1)的连续数组A
3.统计数组中每个元素出现的次数，存入A中
4.再把临时数组A中的数据从小到大汇总起来，出现几次就输出几次
def countSort(arr): min_arr = min(arr) max_arr = max(arr) len = max_arr - min_arr + 1 temp = [0] * len result = [] for t in arr: temp[t-min_arr] = temp[t-min_arr] + 1 for i in range(min_arr,max_arr+1): p = [i]*temp[i-min_arr] result.extend(p) return result
性质：时间复杂度：O(n+k)、空间复杂度：O(k)、稳定排序、非原地排序（k为临时数组的大小）
9.桶排序
当数列取值范围过大，或者不是整数时，不能适用计数排序
步骤：
1.创建若干个桶，确定每一个桶的区间范围，里面可以承载一个或多个元素
2.遍历原数列，把元素对号入座放入各个桶中
3.每个桶内部的元素分别排序
4.遍历所有桶，输出所有元素
def bucketSort(arr): n = len(arr) min_arr = min(arr) max_arr = max(arr) result = [] #创建n个桶 new_list = [[] for _ in range(n)] #区间跨度大小 length = (max_arr - min_arr) // (n - 1) for data in arr: index = int((data - min_arr) // (length + 1)) new_list[index].append(data) for i in range(n): new_list[i].sort() for i in range(n): for j in range(len(new_list[i])): result.append(new_list[i][j]) return result
性质：时间复杂度：O(n+k)、空间复杂度：O(n+k)、稳定排序、非原地排序（k为桶的个数）
10.基数排序
步骤：
1.先以个位数的大小来对数据进行排序，接着以十位数的大小来对数据进行排序，接着是百位数……
2.在以某位数进行排序时，需要准备0-9的10个桶，把相同数值的数放在同一个桶里
def radioSort(arr): #计算最大值是几位数 num = 1 max_arr = max(arr) while max_arr // 10 > 0: max_arr = max_arr // 10 num += 1 for i in range(1,num+1): bucket = [[] for _ in range(10)] for j in range(len(arr)): radio = (arr[j] // int(pow(10,i-1))) % 10 bucket[radio].append(arr[j]) k = 0 for i in range(10): for j in range(len(bucket[i])): arr[k] = bucket[i][j] k += 1 return arr
性质：时间复杂度：O(kn)、空间复杂度：O(n+k)、稳定排序、非原地排序（k为桶的个数）
文章来源: 博客园
- 还没有人评论，欢迎说说您的想法！
客服
