1 TODO 排序算法 @home ALGORITHM
1.1 性能指标
- 效率从高到低
- 常数级
- 对数级
- 次线性级
- 线性级
- n log(n)
- 平方级
- 指数级
1.2 排序算法
- 使用环境
- 小规模数据(因为复杂度为O(n平法))
- 原本几乎有序(原本几乎有序,在理想状况下,算法复杂度为O(n))
1.3 代码实现
def insert_sort(ary): """ 插入法排序 """ """ 算法复杂度O(n平方)""" """ 始终保证A[0,i]是有序的 """ """ 依次插入值,如果插入的值比左边的小,依次往左移动直至合适位置 """ sort_ary = [0 for i in range(len(ary))] for i in range(len(ary)): sort_ary[i] = ary[i] for j in range(i, 0, -1): if sort_ary[j] < sort_ary[j - 1]: tmp = sort_ary[j - 1] sort_ary[j - 1] = sort_ary[j] sort_ary[j] = tmp for i in range(len(sort_ary)): ary[i] = sort_ary[i] def median_sort(ary): """ 中值法排序 """ """ 算法复杂度O(nlog(n)) """ """ 递归,分治思想 """ """ 找到中值元素,比中值小的放左边,大于或者等于中值的放右边 """ """ 递归中值左右子数组 """ median_sort_internal(ary, 0, len(ary) - 1) def median_sort_internal(ary, left, right): """ 递归函数 """ if right <= left: return else: mid = (right - left + 1) / 2 select_kth(ary, left, right, mid) median_sort_internal(ary, left, left + mid - 1) median_sort_internal(ary, left + mid + 1, right) def select_kth(ary, left, right, k): """ 选择第k大的元素,并分区 """ idx = left index = partition(ary, left, right, idx) if (left + k) - 1 == index: return index else: if (left + k - 1) < index: return select_kth(ary, left, index - 1, k) else: return select_kth(ary, index + 1, right, k - (index - left + 1)) def partition(ary, left, right, index): """ 分块函数,并返回index对应值在分块完成的下标 """ store = left value = ary[index] tmp = ary[right] ary[right] = value ary[index] = tmp for i in range(left, right, +1): if ary[i] < value: tmp = ary[i] ary[i] = ary[store] ary[store] = tmp store = store + 1 ary[right] = ary[store] ary[store] = value return store def quick_sort(ary, left, right): """ 快速排序 """ """ 快速排序和中值排序的方法几乎一样,区别在于快速排序可以随机选择枢纽值,而不是选择中值 """ if (left >= right): return """ 选择最右边的为枢纽值 """ key = ary[right] i = left j = left for i in xrange(left, right): if (ary[i] < key): tmp = ary[i] ary[i] = ary[j] ary[j] = tmp j = j + 1 tmp = ary[j] ary[j] = key ary[right] = tmp quick_sort(ary, left, j - 1) quick_sort(ary, j + 1, right) def bubble_sort(ary): """ 冒泡排序 """ """ 时间复杂度O(n平方) """ """ 如其名,像气泡一样网上冒 """ """ 如果a[i]大于a[i+1],则交换.需要进行n-1次扫描. """ """ 第一次扫描把最大值放到最后,第二次把第二大的值放到最大值前门,依次类推 """ length = len(ary) for i in range(length - 1, -1, -1): for j in range(i): if ary[j] > ary[j + 1]: tmp = ary[j] ary[j] = ary[j + 1] ary[j + 1] = tmp def select_sort(ary): """ 选择排序 """ """ 时间复杂度O(n平方) """ """ 不停选择最大值往最后放,先选完再交换 """ for i in range(len(ary)): index = select_max(ary, len(ary) - i) tmp = ary[len(ary) - i - 1] ary[len(ary) - i - 1] = ary[index] ary[index] = tmp def select_max(ary, length): """ 选择最大值,返回下标 """ max = ary[length - 1] index = length - 1 for i in range(length): if max < ary[i]: max = ary[i] index = i return index def heap_sort(ary): """ 堆排序 """ """ 时间复杂度O(nlogn),最坏情况也是n(nlogn) """ """ 可以把堆当做完全二叉树 """ """ 利用堆的性质,不停添加有序区域,直至全部有序. """ """ 1. 构造大顶堆 """ """ 2. 取出根元素和最后一个元素互换. """ """ 3. 重复执行以上过程 """ build_heap(ary) length = len(ary) for i in range(length - 1, -1, -1): tmp = ary[0] ary[0] = ary[i] ary[i] = tmp """ 大根堆根顶元素互换,然后重新构造大根堆 """ heapify(ary, 0, i) def build_heap(ary): """ 初始化堆,从无序堆到大根堆 """ """ 假设完全二叉树的层级为n,从n-1层开始构造子大根堆,逐渐递减n.直到n为0. """ length = len(ary) / 2 - 1 for i in range(length, -1, -1): heapify(ary, i, len(ary)) def heapify(ary, idx, max_len): """ 调整堆 """ left = 2 * idx + 1 right = 2 * idx + 2 largest = idx if left < max_len and ary[left] > ary[idx]: largest = left if right < max_len and ary[right] > ary[largest]: largest = right if not largest == idx: tmp = ary[idx] ary[idx] = ary[largest] ary[largest] = tmp heapify(ary, largest, max_len) def counting_sort(ary): """ 计数排序 """ """ 非比较排序,时间复杂度为线性. """ """ 适合于排序n个元素,元素的取值为[0, k],n远大于k """ k = ary[0] for i in range(len(ary)): if ary[i] > k: k = ary[i] k_ary = [0 for i in range(k + 1)] tmp = 0 for i in range(len(ary)): k_ary[ary[i]] += 1 for i in range(len(k_ary)): if k_ary[i] > 0: for j in range(k_ary[i]): ary[tmp] = i tmp += 1 def bucket_sort(ary): """ 桶排序 """ """ 跟计数排序类似 """ """ 使用hash函数均匀的将n个元素分散到k个桶中,桶必须是有序的,i-1桶中的元素一定都要比i桶中的元素小 """ """ 每个桶使用插入排序 """ k = ary[0] for i in range(len(ary)): if ary[i] > k: k = ary[i] """ hash(x) = x / 3 """ bucket_ary = [[] for i in range(k / 3 + 1)] for i in range(len(ary)): index = ary[i] / 3 bucket_ary[index].append(ary[i]) tmp = 0 for i in range(len(bucket_ary)): insert_sort(bucket_ary[i]) for j in range(len(bucket_ary[i])): ary[tmp] = bucket_ary[i][j] tmp += 1 ARRAY = [2, 5, 6, 8, 1, 3, 4, 2, 9, 7] insert_sort(ARRAY) print ARRAY ARRAY = [2, 5, 6, 8, 1, 3, 4, 2, 9, 7] quick_sort(ARRAY, 0, len(ARRAY) - 1) print ARRAY ARRAY = [2, 5, 6, 8, 1, 3, 4, 2, 9, 7] median_sort(ARRAY) print ARRAY ARRAY = [2, 5, 6, 8, 1, 3, 4, 2, 9, 7] select_sort(ARRAY) print ARRAY ARRAY = [2, 5, 6, 8, 1, 3, 4, 2, 9, 7] bubble_sort(ARRAY) print ARRAY ARRAY = [2, 5, 6, 8, 1, 3, 4, 2, 9, 7] heap_sort(ARRAY) print ARRAY ARRAY = [2, 5, 6, 8, 1, 3, 4, 2, 9, 7] counting_sort(ARRAY) print ARRAY ARRAY = [2, 5, 6, 8, 1, 3, 4, 2, 9, 7] bucket_sort(ARRAY) print ARRAY