侧边栏壁纸
博主头像
996worker

祇園精舎の鐘の聲, 諸行無常の響き有り。

  • 累计撰写 193 篇文章
  • 累计创建 46 个标签
  • 累计收到 8 条评论

目 录CONTENT

文章目录

Sorting

996worker
2021-07-04 / 0 评论 / 0 点赞 / 213 阅读 / 1,088 字
温馨提示:
本文最后更新于 2021-07-24,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

Let's talk about sorting, which can be helpful when I deal with god damn interviews...

1. What?

  • Bubble sort
    It traverses the whole array. At each traverse, it will compares two adjacent numbers from the array head to the array tail. If the former is larger then the latter, they will be swapped.

  • Quick sort
    One pivot with two pointers...

  • insertion sort
    Start from the second element (pointer A), compare with the previous one. If the previous one is greater than the latter, swapping. Repeat these steps until previous one is less than or equal to the latter, Move the pointer A to the next element, then repeat all steps.

  • shell sort

  • selection sort
    Start From the first element (pointer A), then the other pointer (pointer B = A + 1) will traverse the rest of elements to find the minimum value, then put the minimum one to the start pointer A, then the start pointer A +1. Repeat these steps until A = len - 1.

  • heap sort
    Construct a heap (Max heap 大顶堆 or Min head 小顶堆), pop root element, then fix the heap, then pop, then fix..... until no one left.

  • merge sort
    Divide an conquer


  • bucket sort

  • radix sort


2. When to use?

| 排序场景 | 排序效率 |
| ---- | ---- | ---- |
| Random | 希尔>快排>归并 |
| Few unique | 快排>希尔>归并 |
| Reversed | 快排>希尔>归并 |
| Almost sorted | 插入排序>基数排序>快排>希尔>归并 |

3. How?

Animation of these sortings

0

评论区