[TOC]
algorithm 4th笔记(2.1)
两个object可以比较的前提
- object实现Comparable。
- 提供Comparator ，此处还说明了Comparator的第二和用法。
排序用到的方法less 判断两object的大小关系 exch交换两个object,注意对象需要实现Comparable接口，才能使用。
private static boolean less(Comparable v, Comparable w) {
return (v.compareTo(w) < 0);
}
private static void exch(Comparable[] a, int i, int j) {
Comparable swap = a[i];
a[i] = a[j];
a[j] = swap;
}
排序算法类的模板,用到的时候，只需要填写排序算法即可
/**
* Created by admin on 2016/11/20.
*/
public class SortExample {
//排序算法具体实现
public static void sort(Comparable[] a){
}
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){
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= In.readStrings();
// sort(a);
// assert isSorted(a);
// show(a);
// }
private static String[] readDataFromFile(String fileName) throws Exception{
/*
*从data.in中读取数据，然后把数据转换成Integer(包装了有Comparable接口)
*/
URL url = SortExample.class.getClassLoader().getResource(fileName);
File file = new File(url.getPath());
Scanner sc=new Scanner(file);
String str= sc.nextLine();
return str.split(" ");
}
public static void main(String[] args) throws Exception{
//设计成从文件读入数据，然后把数据(maven下，数据放在resources目录)
String[] ss=readDataFromFile("ch02/data.in");
int N=ss.length;
Integer[] arr=new Integer[N];
for(int i=0;i<N;i++){
arr[i]=new Integer(Integer.parseInt(ss[i]));
}
sort(arr);
assert isSorted(arr);
show(arr);
}
}
Select排序
[0 ... idx ... len - 1]
每次从(idx,len-1]之间选择一个最小的与idx处的值交换。
// 只能对实现Comparable接口的数据类型排序
private static void sort(Comparable[] a) {
int len = a.length;
for (int i = 0; i < len; ++i) {
int min = i;
for (int j = i + 1; j < len; ++j) {
if (less(a[j], a[min])) {
min = j;
}
}
assert isSorted(a, 0, i);
exch(a, i, min);
}
assert isSorted(a);
}
Insert排序
[0 ... idx ... len - 1]
从idx开始，把idx处的值插入到已经排序后的[0,idx)中适当的位置。
// 只能对实现Comparable接口的数据类型排序
private static void sort(Comparable[] a) {
int n = a.length;
for (int i = 1; i < n; ++i) {
for(int j = i; j > 0; --j){
if(less(a[j],a[j-1])){
exch(a,j,j-1);
}
}
assert isSorted(a,0,i);
}
assert isSorted(a);
}
Shell排序
可以看作Insert排序的改进版本。把一个数组中的所有元素分成几部分来排序；先把几个小部分的元素排序好，让元素大概有个顺序，最后再全面使用插入排序。一般最后一次排序都是和上面的插入排序一样的；
// 只能对实现Comparable接口的数据类型排序
private static void sort(Comparable[] a) {
int n = a.length;
int h = 1;
while (h < n / 3) {
h = 3 * h + 1;
}
while (h >= 1) {
for (int i = h; i < n; ++i) {
for (int j = i; j >= h && less(a[j], a[j - h]); j -= h) {
exch(a, j, j - h);
}
}
assert isSorted(a);
h /= 3;
}
assert isSorted(a);
}
注意： 最差情况下：shell排序的时间复杂度为O(n^2);
最佳情况下，Shell排序的时间复杂度为O(n^1.3) --> 具体推理上不做说明。
以前一直以为Shell排序的时间复杂度为O(nlog(n))。
