作业帮数据结构中排序的方法中稳定的有那些,不稳定的有那些（如快速排序等）
来源：学生作业帮助网 编辑：作业帮 时间：2024/11/19 09:19:14
数据结构中排序的方法中稳定的有那些,不稳定的有那些（如快速排序等）
数据结构中排序的方法中稳定的有那些,不稳定的有那些（如快速排序等）
数据结构中排序的方法中稳定的有那些,不稳定的有那些（如快速排序等）
稳定的
冒泡排序（bubble sort） — O(n2) 鸡尾酒排序 (Cocktail sort, 双向的冒泡排序) — O(n2) 插入排序 （insertion sort）— O(n2) 桶排序 （bucket sort）— O(n); 需要 O(k) 额外 记忆体 计数排序 (counting sort) — O(n+k); 需要 O(n+k) 额外 记忆体 归并排序 （merge sort）— O(n log n); 需要 O(n) 额外记忆体 原地归并排序 — O(n2) 二叉树排序 （Binary tree sort） — O(n log n); 需要 O(n) 额外记忆体 鸽巢排序 (Pigeonhole sort) — O(n+k); 需要 O(k) 额外记忆体 基数排序 （radix sort）— O(n·k); 需要 O(n) 额外记忆体 Gnome sort — O(n2) Library sort — O(n log n) with high probability, 需要 (1+ε)n 额外记忆体
不稳定
选择排序 （selection sort）— O(n2) 希尔排序 （shell sort）— O(n log n) 如果使用最佳的现在版本 Comb sort — O(n log n) 堆排序 （heapsort）— O(n log n) Smoothsort — O(n log n) 快速排序 （quicksort）— O(n log n) 期望时间, O(n2) 最坏情况; 对於大的、乱数串列一般相信是最快的已知排序 Introsort — O(n log n) Patience sorting — O(n log n + k) 最外情况时间, 需要 额外的 O(n + k) 空间, 也需要找到最长的递增子序列（longest increasing subsequence）