排序算法

排序就是将一组无序的元素通过某种规则将他们按照某种主键来进行升序或者降序排列,比如,我们考试成绩,按照总分进行降序排列,按照语文成绩进行降序排列,按照数学成绩进行降序排列,此时的总分, 语文, 数学 就是我们排序的主键,又或者我们打开电脑文件夹,按照名字排序,按照时间排序等,由此可见,排序操作在我们的日常生活中的作用之大,下面我们将讲解一些常见的排序算法,参考书籍为<<算法 第四版>>.

声明: 本节所有内容均默认以升序排列,同时所有代码遵从以下模板.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
public class Template {
public static void sort(Comparable[] a) {
}

protected static boolean less(Comparable v, Comparable w){
return v.compareTo(w) < 0;
}

protected static void exch(Comparable[] a, int i, int j) {
Comparable t = a[i];
a[i] = a[j];
a[j] = t;
}

protected static void show(Comparable[] a) {
for (int i = 0; i < a.length; ++i) {
System.out.print(a[i] + ", ");
}
System.out.println();
}
public static boolean isSorted(Comparable[] a) {
for (int i = 1; i < a.length; ++i) {
if (less(a[i], a[i-1]))
return false;
}
return true;
}

public static void main(String[] args) {
// String[] a = new String[n];
sort(a);
assert Template.isSorted(a);
Template.show(a);
}
}

选择排序

选择排序 顾名思义就是从乱序的数组中选择最值,其思路如下: 首先,从 N 个数中选择最小的数,放在数组第一个位置,然后从剩下的 N-1 个数中选择最小的数放在数组的第二个位置,迭代此过程直至完成排序.该算法大约进行 $N^2/2$ 次比较和 N 次交换,详细计算如下:

寻找第一个最小值时,我们需要在余下的 N-1(为什么是 N-1 不是 N?因为数组坐标为0的数是我们目前最小的值,此时我们从剩下的 N-1 个数比较依次找最小值) 个数中进行比较,且交换 1 次,此时进行了 N-1 次比较,寻找第二个最小值时,需要在余下的 N-2 个数中进行比较,此时进行了 N-2 次比较,所以我们总共需要 $(N-1)+(N-2)+\dots +1=N(N-1)/2$ 比较和 N-1 次交换.

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
package sort;
/**
* @Author song
* @Date 18-8-14 下午9:38
*/
public class Selection extends Template {
public static void sort(Comparable[] a) {
// 升序排列
int N = a.length;
for (int i = 0; i < N; ++i) {
int min = i;
for (int j = i+1; j < N; ++j) {
if (Template.less(a[j], a[min]))
min = j;
}

Template.exch(a, i, min);
}
}

public static void main(String[] args) {
String[] a = new String[]{"s", "o", "r", "t", "e", "x", "a", "m", "p", "l", "e"};
sort(a);
assert Template.isSorted(a);
Template.show(a);
}
}