《算法》2.1-初级排序算法
2017-07-05 本文已影响13人
不会code的程序猿
1. 基本规则
- 排序类算法模板
public class Example
{
public static void sort(Comparable[] a)
{
/* See Algorithms 2.1, 2.2, 2.3, 2.4, 2.5, or 2.7. */ }
private static boolean less(Comparable v, Comparable w)
{
return v.compareTo(w) < 0;
}
private static void exch(Comparable[] a, int i, int j)
{
Comparable t = a[i];
a[i] = a[j];
a[j] = t;
}
private static void show(Comparable[] a)
{ // Print the array, on a single
// line.
for (int i = 0; i < a.length; i++)
StdOut.print(a[i] + " ");
StdOut.println();
}
public static boolean isSorted(Comparable[] a)
{ // Test whether the array
// entries are in order.
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)
{ // Read strings from standard
// input, sort them, and print.
String[] a = In.readStrings();
sort(a);
assert isSorted(a);
show(a);
}
}
-
Comparable接口
实现了Comparable接口的数据类型：Integer、String、Double都实现了Comparable接口。创建自己的数据类型时，我们也要实现Comparable接口就能使用该模板进行排序。必须要实现Comparable接口中的compareTo方法。
public class Date implements Comparable<Date>
{
private final int day;
private final int month;
private final int year;
public Date(int d, int m, int y)
{
day = d;
month = m;
year = y;
}
public int day() {return day;}
public int month(){return month;}
public int year(){return year;}
public int compareTo(Date that)
{
if (this.year > that.year)
return +1;
if (this.year < that.year)
return -1;
if (this.month > that.month)
return +1;
if (this.month < that.month)
return -1;
if (this.day > that.day)
return +1;
if (this.day < that.day)
return -1;
return 0;
}
public String toString()
{
return month + "/" + day + "/" + year;
}
}
compareTo必须实现一个全序关系：
①自反性：对所有的v=v
②反对称性：对所有v<w都有v>w，且v=w时w=v
③传递性
- 排序成本模型：比较次数和访问数组的次数
- 额外的内存使用
2. 选择排序
-
思想：
首先，找到数组中最小的元素，其次将它和数组的第一个元素交换位置。再次，在剩下的元素中找到最小的元素和数组的第二个元素交换位置。如此往复，直到将整个数组排序。不断选择剩余元素中的最小者。
public class Selection
{
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(less(a[j],a[min])) min=j;
exch(a,i,min);
}
}
}
-
Example
选择排序
-
分析：
①运行时间和输入无关
②数据移动是最少的
③长度为N的数组需要交换N次，比较次数：(N-1)+(N-2)+...1=N(N-1)/2~
3. 插入排序
-
思想：
想象打扑克牌，一张一张地把牌插入到适当地位置。在计算机的视线中，为了要给插入的元素腾出空间，我们需要将其余所有元素在插入之前都向后移动一位。插入排序所需要的时间取决于输入元素中的初始顺序。
public class Insertion
{
public static void sort(Comparable[] a)
{
int N=a.length;
for(int i=1;i<N;i++)
{ //a[i]插入到a[i-1] a[i-2]...1中
for(int j=i;j>=0&&less(a[j],a[j-1]);j--)
{
exch(a,j,j-1);
}
}
}
}
-
Example
插入排序
-
分析：
①best：输入顺序增大，无需移动元素，只需要N-1次比较。
②worst：输入是逆序的：N2/2次比较和交换
③平均：N2/4次比较和交换
4. 希尔排序
- 思想：
基于插入排序的快速排序算法。对于大规模乱序的数组插入排序很慢，是因为它只会交换相邻的元素，因此元素只能一点一点移动。希尔排序改进了插入排序算法，交换不相邻的元素以对数组的局部进行排序，并最终用插入排序将局部有序的数组排序。 关键：使数组中任意间隔为h的元素都是有序的
public static void sort(Comparable[] a) {
int n = a.length;
// 3x+1 increment sequence: 1, 4, 13, 40, 121, 364, 1093, ...
int h = 1;
while (h < n/3) h = 3*h + 1;
while (h >= 1) {
// h-sort the array
for (int i = h; i < n; i++) {
//将a[i]插入到a[i-h],a[i-2*h],a[i-3*h].....
for (int j = i; j >= h && less(a[j], a[j-h]); j -= h) {
exch(a, j, j-h);
}
}
assert isHsorted(a, h);
h /= 3;
}
assert isSorted(a);
}
希尔排序
