1、冒泡排序-减而治之

冒泡排序属于最基础的排序,其思路为减而治之

  1. 采用两层for循环,记录k=array.length。使i=0,每一次比对当前位置i与位置i+1的大小,若array[i]>array[i+1],则交换位置,i++,直到i不小于k。
  2. 这样每经过一轮顶层迭代都能使数组中最大元素到达数组末尾,并令k–,达到减少遍历长度的条件。

如图,蓝色的是未排序部分,而灰色的则是已排序部分。

2、选择排序-减而治之

选择排序与冒泡排序非常非常像,但是他相较于冒泡排序有一个提升,就是当发现逆序对时并不进行交换,而只保存一个max值,在到达末尾时才进行交换。其余思路与冒泡排序相同。即只比冒泡排序少了交换这一动作的损耗。

3、插入排序-减而治之

相较于前两种排序,通常使用数组实现比较高效,插入排序则用链表实现比较容易理解。

  1. 首先将待排序链表假定为两部分g,h,g为未排序部分,而h为排序部分。假定n为链表长度,h初始为秩为n-1的节点,即只有一个节点。而g则为前n-1个节点。
  2. 遍历g,取除g部分的节点与h部分进行遍历依次必对,当遇到大于当前比较节点的h内部节点d时,则将其插入d之前。从而g减少,h增大
  3. 循环步骤2直至g部分为0,排序完成。

当然希尔排序在最差情况下就等于插入排序,因此也有可能是o(n^2)

KAI 排序, 数据结构与算法