内排序算法小结

内排序算法

William Yi 完成于2016/10/18

Email: [e-mail]

排序算法可以大致分为两种类型：

• 内排序
• 外排序

两者之间的区别是内排序是在内存中进行的排序，而外排序则可以借助磁盘空间。

我们通过之前的学习了解到：内存中的排序时间代价与空间代价是成反比的，也就是说时间的缩短是以空间增长为代价的，空间的减少是以时间延长为代价的；而磁盘中的时间代价与空间代价是成正比的。

如果不考虑特别情况，我们所有的排序算法都是进行的非降序排列。

内部排序的分类

排序算法：

• 插入排序
  
  • 直接插入排序
  • 折半插入排序
  • 希尔排序
• 交换排序
  
  • 冒泡排序
  • 快速排序
• 选择排序
  
  • 简单选择排序
  • 堆排序
• 归并排序
• 基数排序

算法的稳定性：

算法的稳定性是指如果待排序列中存在两个或者多个相同的元素，某一特定的算法在排序之后不改变相同元素的相对关系，那么就称该算法是稳定的，否则则说该算法是不稳定的。

三种时间代价为 Θ(n2) 的排序算法

• 简单插入排序
• 冒泡排序
• 选择排序

简单插入排序

简单插入排序的算法思想

简单插入排序就是将待插入元素插入进排好序的序列之中，其中至少第一个元素是已经排好序了的。其采取的是两重遍历，第一重遍历 n−1 个元素作为插入元素，然后每个插入元素在之前已经排好序的序列中遍历，选择合适的位置进行插入。

代码实现

public static void InsertSort(Element[] array) {
for(int i = 1; i < array.length; i++)
for(int j = i; (j > 0) && array[j].compareTo(array[j-1]) < 0; j--)
      arraySwap(array, j, j-1); 
}

注： 此处i循环是从1开始计数是因为第一个元素一定是有序的，因此我们第一个循环只用遍历n-1次。

简单插入排序算法优化

暂时不考虑简单插入排序算法的优化问题。

利用最好情形的时间特性来对其他较为复杂的算法进行优化

最好、平均、最差情况的时间复杂度分析

• 最好情形

  • 比较次数 Θ(n)
  • 交换次数 0

  注：由于在最好情形下简单插入排序算法具有任何一个算法都无法比拟的时间特性，因此这种时间特性常常用来对其他算法进行优化（例如Shell排序）。另外，由于最好情形出现的可能性较低，但是类最好情形出现的概率则是很高的，因此上述优化是可行的。

• 最差情形

  • 比较次数 Θ(n2)
  • 交换次数 Θ(n2)

• 平均情形

  理论上平均情形的计算就是最好情形与最差情形时间复杂度的平均值。

  • 比较次数 Θ(n2)
  • 交换次数 Θ(n2)

冒泡排序

冒泡排序算法思想

冒泡排序也是经过两重循环，第一重从序列最大处（array[n-1]）开始逐步遍历，然后第二重循环在待排序列选定后进行循环定位。

代码实现

public static void BubbleSort(Element[] array) {
for(int i = 0; i < array.length - 1; i++) {
for(int j = array.length; j > i; j--)
if(array[j].compareTo(array[j-1]) < 0) arraySwap(array, j, j-1);
}

注： 冒泡排序算法的思路就是哪个元素最小，那么就直接将其排到数组头，其有一个突出特点是，在排序时各个元素会向各自的最终位置移动。

冒泡排序算法优化

如果原来的数据本身已经是排好序了的，那么可以通过设置一个bool类型的变量，去判断当前的一组比较是否是有意义的，当该组比较无意义时，那么证明数据本省已经排好序了。因此其最好情况的运行时间是 Θ(n) .

public static void BubbleSort_Better(Element[] array) {
boolean isSwap = false;
for(int i = 0; i < array.length-1; i++) {
    isSwap = false;
for(int j = array.length-1; j > i; j--) {
if(array[j].compareTo(array[j-1]) < 0) {
        isSwap = true;
        swap(array, j, j-1);
      }
    }
if(!isSwap) break;
  }
}

最好、平均、最差情况的时间复杂度分析

• 最好情形

  • 比较次数 Θ(n2) 优化之后运行时间为Θ(n)
  • 交换次数 0

  注： 由于冒泡排序中有一个将所有数据元素向其最终位置移动的动作，因此会在比较次数上明显劣于简单选择排序。

• 最差情形

  • 比较次数 Θ(n2)
  • 交换次数 Θ(n2)

• 平均情形

  • 比较次数 Θ(n2)
  • 交换次数 Θ(n2)

选择排序

选择排序算法思想

选择排序的本质还是进行的冒泡排序–每进行一次排序循环则筛选出当前的最先元素置于已排序序列之中。但是其交换是间接交换的，相对于冒泡排序而言，交换次数较少，但是由于其交换是跳元素交换，因此选择排序算法不具有稳定性。

代码实现

public static void SelectSort(Element[] array) {
for(int i = 0; i < array.length; i++) {
int lowIndex = i;
for(int j = array.length - 1; j > i; j--) {
if(array[j].compareTo(array[lowIndex] < 0) lowIndex = j;
      arraySwap(array, i, lowIndex);
    }
  }
}

选择排序算法优化

简单选择排序算法的优化原理与冒泡排序的原理是相同的。都是可以通过设置布尔类型的flag值对于最好情况下的比较次数进行降级至 Θ(n) .

public static void SelectSort_Better(Element[] array) {
boolean isSwap = false;
for(int i = 0; i < array.length; i++) {
int lowIndex = i;
    isSwap = false;
for(int j = array.length - 1; j > i; j--) {
if(array[j].compareTo(array[lowIndex]) < 0) {
        lowIndex = j;
        isSwap = true;
      }
      arraySwap(array, i ,lowIndex);
    }
  }
}

最好、平均、最差情况的时间复杂度分析

• 最好情形
  
  • 比较次数 Θ(n2) 优化之后可以降级为线性时间复杂度。
  • 交换次数 0
• 最差情形
  
  • 比较次数 Θ(n2)
  • 交换次数 Θ(n2)
• 平均情形
  
  • 比较次数 Θ(n2)
  • 交换次数 Θ(n2)

三种排序算法的优劣比较

以下从四个方面对算法的优劣进行比较：

• 部分性

  • 概念：该算法进行的过程之中已排序序列中的最小值是否是整体的最小值，如果一致，那么该算法不具有部分性，否则则说该算法具有部分性。
  • 由上可知，仅有简单插入算法满足部分性，冒泡排序算法和选择排序算法不满足

• 在线性

  • 概念：该算法是否在排序过程中可以在数组末端增加其他元素
  • 有算法本身的特性可知，仅有简单插入排序算法具有在线性，由于其他两者算法是执行第i次找出算法中的第i小的元素，因此不具有

• 稳定性

  • 概念：稳定性是指该排序算法在排序之后是否改变相同元素的相对位置
  • 由于稳定性的一个考量标准是数据的交换是否为相邻元素。由于选择排序数据的交换非相邻元素，而其他两种算法数据的交换是相邻元素，因此只有简单插入排序算法和冒泡排序算法具有稳定性

• 原地性

  • 概念：在完成一次排序之后，不需要额外申请新的空间。
  • 算法比较中的原地性是指其算法运行本身不需要其他的空间来存储数据。

两种折半排序算法

• 折半插入排序算法

• 折半搜索算法

  折半搜索算法在学习搜素时再进行系统化的理解与学习。

希尔排序

算法思想

希尔排序的核心思想是利用简单插入排序在接近于最佳情况时的良好性能来进行的跳元素交换排序。（其间距的选择极为重要）

代码实现

以下排序算法仅仅是特殊化的取中间值shell排序算法的实现

public static void ShellSort(Element[] array, int start, int incr) {
for(int i = start + incr; i < array.length; i += incr) {
for(int j = i; (j >= incr) && array[j] < array[j-incr]; j -= incr) 
      swap(array, array[j], array[j-incr]);
  }
}

算法优化

由于shell排序的算法关键在于间距的选择，因此我们需要选择合适的间距来将shell排序的良好算法特性发挥出来，目前普遍采用的主要有两种间距选择方式：

• 唐纳德间距选择法

  {h1=1hi+1=3hi+1  i>=1

• 海伯德间距选择法

  hi=2i−1 i>=1

在间距取得很好的情况下，希尔排序算法的时间复杂度可以降低到 Θ(nlgn) .最差情况是什么都没有做但是时间复杂度还是 Θ(n2) .

快速排序

算法思想

快速排序使用的算法思想是分治法。通过二分，取一个轴值，将比轴值大的元素分为一组，比轴值小的元素分为一组，再重复上面的思路。最后进行合并(此处合并为自动合并)。

代码实现

//Main Structure：

public static void QuickSort(Element[] array, int left, int right) {
int pivotIndex = findPivot(array, left, right);
  swap(array, pivotIndex, right);
int k = partition(array, left - 1, right, array[right]);
  swap(array, k, right);
if((k - left) > 1) QuickSort(array, left, k - 1);
if((right - k) > 1) QuickSort(array, k + 1; right);
}

findPivot(array, left, right):

//Main Idea:
public static int findPivot(array, left, right) {
return (left + right) /2;
}
//Make center to be the second one in the chosen three elements
public static int findPivot(array, left, right) {
int center = (left + right) / 2;
if(array[right].compareTo(array[left]) < 0) swap(array, left, right);
if(array[center].compareTo(array[left]) < 0) swap(array, center, left);
if(array[right].compareTo(array[center]) < 0) swap(array, center, right);
return center;
}

partition(Element[] array, int left, int right, Element pivot)

分割的总体思路是：

• 将轴值
• 与最右边界的值进行交换
• 为记录序列两端建立两个游标(左游标=left， 右游标=right-1)
• 将两个游标朝相反的方向移动
  
  • 左游标移过小于轴值的所有元素
  • 右游标移过大于轴值的所有元素
  • 当左游标小于右游标则交换两个游标所指的元素
  • 重复这个步骤直到当左游标大于右游标则分割完成
• 将左游标和right所指的元素进行交换

public static int partition(Element[] array, int left, int right, Element pivot) {
  do {
while(array[++left].compareTo(pivot) < 0);
while(right != 0 && array[--right].compareTo(pivot) < 0);
    swap(array, left, right);
  } while(left < right);
  swap(array, left, right);
return left;
}

算法优化

快速排序的关键在于轴值的选取，我们一般是将头，尾，中坐标下的值取一个中间值进行选择。

快速排序的算法不存在最好情况，最差情况和平均情况的差异，在任何时候的时间复杂度都是 Θ(nlgn) .

归并排序

算法思想

归并排序使用的算法思想也是分治法，其可以新开一段内存空间，先将一个线性表一分为二(从中间分开即可)，然后使用递归对其进行分别排序，排完序之后依次将两个数组的元素在新内存空间中进行排列。如果是链表，那么直接新建新的链表即可。

代码实现

//Main Structure:

List MergeSort(List list) {
if(inList.length() <= 1) return inList;
  List l1 = half of the items from inlist;
  List l2 = other half of the items from inList;
return merge(MergeSort(L1), mergeSort(L2));
}

链表线性表的分割

LList list1 = new LList();
LList list2 = new LList();
while(!list.isEmpty()) {
  list1.append(list.remove());
if(list.isEmpty()) break;
  list2.append(list.remove());
} 

数组形式线性表的分割

int left = 0;
int right = array.length - 1;
int mid = (left + right) / 2;

链表式线性表的合并

while(!list1.isEmpty() && !list2.isEmpty()) {
if(list1.currValue().compareTo(list2.currValue) < 0)
    list.append(list1.remove());
else list.append(list2.remove());
}
while(!list1.isEmpty()) list.append(list1.remove());
while(!list2.isEmpty()) list.append(lsit2.remove());

效率分析

归并排序算法的效率是 Θ(nlgn) .

写在最后

内排序算法是之后算法与数据结构学习的基础，自己要在熟练掌握的基础上进行运用，就如老师所说的，认真走过这一段路，将数据结构学好，那么一切都不会构成障碍，代码能力会得到飞跃式的提升。