专业制作网站的公司哪家好,seo技术 如何优化网站内部结构,erp开发和网站开发,交换友情链接的意义是什么排序算法 一、选择排序二、合并/归并排序三、快速排序四、计数排序 排序类型时间复杂度选择排序(Selection Sort) O ( n 2 ) O(n^{2} ) O(n2)合并/归并排序#xff08;Merge Sort#xff09; O ( n log n ) O(n\log n ) O(nlogn)快速排序(Quick Sort)平均情况 O ( n log … 排序算法 一、选择排序二、合并/归并排序三、快速排序四、计数排序 排序类型时间复杂度选择排序(Selection Sort) O ( n 2 ) O(n^{2} ) O(n2)合并/归并排序Merge Sort O ( n log n ) O(n\log n ) O(nlogn)快速排序(Quick Sort)平均情况 O ( n log n ) O(n\log n ) O(nlogn)最糟情况 O ( n 2 ) O(n^{2} ) O(n2)计数排序(Counting Sort) O ( n k ) O(nk ) O(nk)
一、选择排序
来自《算法图解》一书
def findSmallest(arr):smallest arr[0] # 存储最小值smallest_index 0 # 存储最小值索引for i in range(1,len(arr)):if arr[i] smallest:smallest arr[i]smallest_index ireturn smallest_indexdef selectionSort(arr):newArr []for i in range(len(arr)):smallest_ind findSmallest(arr)newArr.append(arr.pop(smallest_ind))return newArrprint(selectionSort([5,3,6,2,10,58,23,31,9,14,4,46,25,35,1,56,29,20,18,43,40,36,49]))结果
二、合并/归并排序
参考 Python实现合并排序归并排序一文看懂
将一个序列从中间位置分成两个序列在将这两个子序列按照第一步继续二分下去直到所有子序列的长度都为1也就是不可以再二分截止。这时候再两两合并成一个有序序列即可。
def merge(arr_a, arr_b):arr_c []i j 0while i len(arr_a) and j len(arr_b):if arr_a[i] arr_b[j]:arr_c.append(arr_a[i])i 1else:arr_c.append(arr_b[j])j 1if i len(arr_a):return arr_c arr_b[j:]else:return arr_c arr_a[i:]def mergeSort(arr):if len(arr) 2:return arrmiddle len(arr) // 2left mergeSort(arr[:middle])right mergeSort(arr[middle:])return merge(left, right)print(mergeSort([23,12,3,7,5,32,37,29,15,24,19]))结果
三、快速排序
来自《算法图解》一书
选择基准值将数组分成两个子数组小于基准值的元素和大于基准值的元素对这两个子数组进行快速排序
def quickSort(arr):if len(arr) 2:return arr # 基线条件为空或只包含一个元素的数组是“有序”的else:pivot arr[0] # 递归条件基准值less [i for i in arr[1:] if i pivot] # 由所有小于基准值的元素组成的子数组greater [i for i in arr[1:] if i pivot] # 由所有大于基准值的元素组成的子数组return quickSort(less) [pivot] quickSort(greater)print(quickSort([10,28,2,36,45,23,14,39,32,24]))结果
四、计数排序
参考 python实现【计数排序】(Count Sort)
找出待排序的数组中最大和最小的元素统计数组中每个值为i的元素出现的次数存入count_nums数组的第i项将count_nums数组中从左向右每一个计数不为0的值依次填充进最终的res排序数组中。
def countingSort(arr):max_value max(arr)res []count_nums [0 for i in range(max_value 1)]for num in arr:count_nums[num] 1for i in range(len(count_nums)):if count_nums[i] ! 0:# res.extend(count_nums[i] * [i]) # 元素i有 count_nums[i]个添加入最终的排序数组res count_nums[i] * [i]return resprint(countingSort([12,30,2,29,23,18,5,7,25,15,8]))结果
