数据结构中排序的方法中稳定的有那些,不稳定的有那些(如快速排序等)

如题所述

稳定的
  冒泡排序(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)
温馨提示:内容为网友见解,仅供参考
无其他回答
相似回答