选择排序&插入排序

选择排序和插入排序虽然都是初级排序算法,但是熟练的掌握它们能够帮助我们改进复杂算法的效率。

选择排序

原理

首先,找到数组中的最小的那个元素,将它和数组的第一个元素交换位置(如果第一个元素就是最小元素那么就和它自己交换)。其次,在剩下的元素中好到最小的元素,将它与数组的第二个元素交换位置。如此往复,直到将整个数组排序。

algorithm_5_0.gif

选择排序的时间效率主要取决于比较的次数。对于一个长度为N的数组,选择排序需要大约(N*N)/2次比较和N次交换。排序过程中改变相同元素的相对位置,所以该排序算法不稳定。

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// 对元素进行比较
public static boolean less(int a, int b){
return a.compareTo(b) < 0;
}

// 将元素交换位置
public static void exch(int[] a, int i, int j){
int t = a[i];
a[i] = a[j];
a[j] = t;
}

public static void SelectSort(int[] a){
// 将a[]按升序排列
int N = a.length;
for (int i = 0; i < N; i ++) {
int min = i; // 最小元素的索引
for (int j = i+1; j < N; j ++) {
if (less(a[i],a[min])) min = j;
}
exch(a,i,min);
}
}

插入排序

原理

通常我们整理桥牌的方法是一张一张的来,将一张牌插入到其它已经有序的牌中的适当位置。

同理,在计算机的实现中,为了给要插入的元素腾出空间,我们需要将其余所有的元素在插入之前都向右移动一位。

algorithm_2_1.gif

当数据正序时,执行效率最好,每次插入都不用移动前面的元素,时间复杂度为O(N)。
当数据反序时,执行效率最差,每次插入都要前面的元素后移,时间复杂度为O(N^2)。
所以,插入排序对于一个基本有序的数组排序是十分高效的,也很适合小规模数组(希尔排序就是利用这一特点优化了时间效率)

在排序过程中需要一个变量来存储插入的值,所以空间复杂度为O(1)。排序过程没有改变相等元素的位置,所以它是稳定的算法。

实现

1
2
3
4
5
6
7
8
public static void InsertSort(int[] a){
int N = a.length;
for (int i = 0; i < N; i ++) {
for (int j = i; j > 0 && less(a[j], a[j-1]); j --){
exch(a, j, j-1);
}
}
}

两种排序算法的时间效率均是平方级别的。即O(N^2)