西维蜀黍

【Algorithm】排序(Sorting)算法

排序算法的比较

算法 平均时间复杂度 最好时间复杂度 最坏时间复杂度 空间复杂度 排序方式 稳定性 备注
冒泡排序 $O(N^2)$ $O(N)$ $O(N^2)$ $O(1)$ In-place 稳定
选择排序 $O(N^2)$ $O(N^2)$ $O(N^2)$ $O(1)$ In-place 稳定
插入排序 $O(N^2)$ $O(N)$ $O(N^2)$ $O(1)$ In-place 稳定 时间复杂度和初始顺序有关
希尔排序(Shell Sort) $O(Nlog_2N)$ $O(Nlog_2N)$ $$O(N^2)$ $O(1)$ In-place 不稳定 改进版插入排序
归并排序(Merge Sort) $O(Nlog_2N)$ $O(Nlog_2N)$ $O(Nlog_2N)$ $O(N)$ Out-place 不稳定
快速排序 $O(Nlog_2N)$ $O(Nlog_2N)$ $O(N^2)$ $O(1)$ In-place 不稳定
堆排序(Heap Sort) $O(Nlog_2N)$ $O(Nlog_2N)$ $O(Nlog_2N)$ $O(1)$ In-place 不稳定
桶排序 (bucke sort) O(N) O(N) $O(N^2)$ or $O(Nlog_2N)$ $O(N)$ Out-place 稳定 最坏时间复杂度取决于对于桶内元素进行排序的算法
  ...


【Algorithm】排序算法 - 冒泡排序(Bubble Sort)

冒泡排序(Bubble Sort)

**冒泡排序(Bubble Sort)**是一种简单的排序算法。它重复地走访过要排序的数列,一次比较两个元素,如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行,直到没有再需要交换,也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。

图解冒泡

第一轮冒泡

以 [ 8,2,5,9,7 ] 这组数字来做示例。

从左往右依次冒泡,将小的元素往右冒泡(移动):

首先比较第一个数和第二个数的大小,我们发现 2 比 8 要小,那么保持原位,不做改动。位置还是 8,2,5,9,7 。

指针往右移动一格,接着比较:

比较第二个数和第三个数的大小,发现 2 比 5 要小,所以位置交换,交换后数组更新为:[ 8,5,2,9,7 ]。

指针再往右移动一格,继续比较:

比较第三个数和第四个数的大小,发现 2 比 9 要小,所以位置交换,交换后数组更新为:[ 8,5,9,2,7 ]

同样,指针再往右移动,继续比较:

比较第 4 个数和第 5 个数的大小,发现 2 比 7 要小,所以位置交换,交换后数组更新为:[ 8,5,9,7,2 ]

下一步,指针再往右移动,发现已经到底了,则本轮冒泡结束,处于最右边的 2 就是已经排好序的数字。

通过这一轮不断的对比交换,数组中最小的数字移动到了最右边。

第二轮冒泡

接下来继续第二轮冒泡:

由于右边的 2 已经是排好序的数字,就不再参与比较,所以本轮冒泡结束,本轮冒泡最终冒到顶部的数字 5 也归于有序序列中,现在数组已经变化成了[ 8,9,7,5,2 ]。

第三轮冒泡

让我们开始第三轮冒泡吧!

由于 8 比 7 大,所以位置不变,此时第三轮冒泡也已经结束,第三轮冒泡的最后结果是[ 9,8,7,5,2 ]

第四轮冒泡

紧接着第四轮冒泡:

9 和 8 比,位置不变,即确定了 8 进入有序序列,那么最后只剩下一个数字 9 ,放在末尾,自此排序结束。

  ...


【Algorithm】排序算法 - 快速排序(Quick Sort)

快速排序(Quick Sort)

快速排序的核心思想也是分治法(Divide and Conquer Method),分而治之。

它的实现方式是每次从序列中选出一个基准值(pivot),其他数依次和基准值做比较,比基准值大的放右边,比基准值小的放左边,然后再对左边和右边的两组数分别选出一个基准值,进行同样的比较移动,重复步骤,直到最后都变成单个元素,整个数组就成了有序的序列。

  ...


【Interview】应聘者提问

SOA

  • 如何看待SOA
  • 下一个SOA
  ...


【Network】Shadowsocks 总结

Shadowsocks Server

Shadowsocks Server 的实现

  ...