算法系列之二 基础排序

基础排序中,我们介绍两种排序方法:选择排序插入排序

这两种排序方法实现和理解都非常简单。学习它们非常有助于明白基础排序的弱点,以及了解为什么会有高级排序算法。而且插入排序还经常用于优化快速排序的小数组排序,这一点可以参见上一篇博客《算法系列之一 快速排序》。

选择排序

选择排序是人脑思维中最容易想到,也最容易实践的方法:

  1. 遍历整个数组,找出一个最小的值,放入到数组第一个位置中。
  2. 从 第二个数 开始,遍历整个数组,找出一个最小的值,放到 第二个位置中。
  3. 以此类推,直到整个数组有序

选择排序是一个非常有特点的算法。它有两个鲜明的特点:

  1. 它不依赖输入的情况。输入一个倒序数组和输入一个已排好序的数组,算法需要的时间是一样的。
  2. 数据的移动是最少的,每次交换都会改变数组中的两个值。因此用了N次交换,即交换次数和数组长度成线性增长。

算法实现如下:

1
2
3
4
5
6
7
8
void selection_sort(int *a, int lo, int hi){

for( int i = lo; i <= hi; i++){
int min = i;
for(int j = i+1; j <= hi; j++) if(a[j] < a[min]) min = j;
swap(a, i, min);
}
}

插入排序

插入排序同选择排序一样,维护一个索引,索引左边所有的元素是有序的,区别在于,插入排序的索引左边的元素有序但位置并不固定,如果有更小的元素,就会插入到元素之间。当索引移动到最右边的时候,整个数组就有序了。

插入排序与选择排序最大的不同是:它依赖输入的数据。如果输入是有序(或接近有序)就要比乱序(接近逆序)要快得多。

1
2
3
4
5
6
7
void insertion_sort(int *a, int lo, int hi){

for(int i = lo; i <= hi; i++){
// 每次处理 第 i个 元素,向左遍历,将其放到合适的位置
for(int j = i; j >= lo && a[j] < a[j-1]; j--) swap(a, j, j-1);
}
}

上面的实现是标准实现,但其实,加一些简单的改动,就可以提升性能。比如:我们每一次的处理的元素(假设为 v ),都会将其和左边比它大的元素交换位置,这需要访问两次数组。如果我们只是将比它大的元素向后移动,等到 v 的位置确定了,再将其放入数组,那么就会减少一半的数组访问次数。

1
2
3
4
5
6
7
8
9
10
void insertion_sort_better(int *a, int lo, int hi){

for(int i = lo+1; i <= hi; i++){
int v = a[i];
int j = i;
for(; j >= lo && v < a[j-1]; j--)
a[j] = a[j-1]; // 每次只移动元素,而不是交换
a[j] = v; // 最后位置确定时,将元素放入最终位置
}
}

插入排序适用的更一般的情况是:部分有序的数组。这样的数组中:

  • 每一个元素离其最终的位置都不远
  • 元素倒置(前一个元素大于后一个元素)很少
  • 只有几个位置不对

这样的情况下,插入排序会比其他任何排序都要更快。所以这就是为什么用插入排序来处理快排的小数组。

reposkeeper wechat
关注微信公众号