search

YuezhenQin / javase

Implement Data Structures and Algorithms (Sorting, Searching, Greedy, DP) from Sketch
2 stars 1 forks source link

Sorting Algorithm (排序专项讨论) #23

Closed YuezhenQin closed 10 months ago

YuezhenQin commented 10 months ago

Fundamentals of Sorting

The fundamental problem of sorting is all about ordering a collection of items. The way to order these items is entirely based on the method of comparison. Different methods of comparison may lead to different results.

At the most basic level, sorting algorithms are all about rearranging elements in a collection based on a common characteristic of those elements.

YuezhenQin commented 10 months ago
YuezhenQin commented 6 months ago

排序总结：基于比较排序、非比较排序

基于比较的排序 (实现Comparable接口，利用compareTo方法): 选择，插入，归并，交换

  1. 选择排序 (SelectionSort): 它每一次从序列中选择一个最大值，并放在序列的末尾；这样重复多次扫描序列之后，整个序列就排序完毕。
  2. 堆排序 (HeapSort):
  3. 插入排序 (InsertionSort)

Image Image

  1. 希尔排序 (ShellSort) 优化的插入排序
  2. 归并排序 (MergeSort)

Image Image

  1. 冒泡排序 (BubbleSort) 属于交换排序
  2. 快速排序 (QuickSort) 属于交换排序 Name Time Complexity
    (best, avg, worst)    		 Space Complexity Version Application Stability 备注
    选择排序 (SelectionSort) O(n2) O(1) ⛔
    堆排序 (HeapSort) O(nlogn) O(1) 堆；优先队列 ⛔
    插入排序 (InsertionSort) O(n), O(n2), O(n2) O(1) ✅ Fast on a sorted array
    希尔排序 (ShellSort) O(n), O(nlogn), O(n2) O(1) 不同的步长序列 h ⛔
    归并排序 (MergeSort) O(nlogn) O(n) 自顶向下 自底向上 O(nlogn) 求解逆序对个数 ✅
    冒泡排序 (BubbleSort) O(n), O(n2), O(n2) O(1) ✅
    快速排序 (QuickSort) O(nlogn), O(nlogn), O(n2) O(1) v1 单路快速排序 v2 双路快速排序 v3三路快速排序 O(n) 求解 selectK, topK ⛔-✅
Name Time Complexity (best, avg, worst) Space Complexity Version Application Stability 备注
选择排序 (Selection Sort) O(n^2) O(1) ⛔
堆排序 (Heap Sort) O(n log n) O(1) 堆；优先队列 ⛔
插入排序 (Insertion Sort) O(n), O(n^2), O(n^2) O(1) ✅ Fast on a sorted array
希尔排序 (Shell Sort) O(n), O(n log n), O(n^2) O(1) 不同的步长序列 h ⛔
归并排序 (Merge Sort) O(n log n) O(n) 自顶向下 自底向上 O(n log n) 求解逆序对个数 ✅
冒泡排序 (Bubble Sort) O(n), O(n^2), O(n^2) O(1) ✅
快速排序 (Quick Sort) O(n log n), O(n log n), O(n^2) O(1) v1 单路快速排序 v2 双路快速排序 v3 三路快速排序 O(n) 求解 selectK, topK ⛔-✅

非比较排序

  1. 计数排序 (CountingSort)
  2. 基数 (RadixSort)
  3. 桶排序 (BucketSort)

two to the power of n: O(2n)

YuezhenQin commented 6 months ago
Format Tag example
Headings =heading1=
==heading2==
===heading3===
New paragraph A blank line starts a new paragraph
Source code block // all on one line
{{{ if (foo) bar else baz }}}
YuezhenQin commented 6 months ago

https://betterexplained.com/articles/sorting-algorithms/#:~:text=Heapsort%20is%20just%20like%20selection,%2Dplace%2C%20without%20additional%20memory.