2.5排序算法和优先队列的应用
排序有重要原因是,在有序的数组中查找比在无序数组中查找更方便.例如删除重复项,在统计学中剔除异常值,查找中位数,或者计算比例.
2.5.1将各种数据排序,实现Comparable接口.
交易事物.
排序算法的一种典型的应用就是商业数据处理.
指针排序
不可变的键
如果排序后的键值还可以修改,那么数组很可能不是有序数组了,在java中可以使用不可变的数据类型作为键来避免这个问题.例如Integer,String,Double,File…
多种排序方法
继承Comparator比Comparable包含更多的比较方式.可以采用不同的比较方式.
多键数组
一般应用中一种元素的多个属性都可能作为排序的键.例如在交易中,有时需要按客户排序(按照每个客户的所有交易记录),有时可能需要按金额排序,有时可能需要按照另一种属性排序.要实现这种灵活性,Comparator正合适.可以定义多种比较器.
private void sort(Object[] a,Comparator c){
}
2.5.12使用比较器实现优先队列,其中Comparator代码如下:
Transaction.java
/******************************************************************************
* Compilation: javac Transaction.java
* Execution: java Transaction
* Dependencies: StdOut.java
*
* Data type for commercial transactions.
*
******************************************************************************/
import java.util.Arrays;
import java.util.Comparator;
/**
* The {@code Transaction} class is an immutable data type to encapsulate a
* commercial transaction with a customer name, date, and amount.
* <p>
* For additional documentation,
* see <a href="https://algs4.cs.princeton.edu/12oop">Section 1.2</a> of
* <i>Algorithms, 4th Edition</i> by Robert Sedgewick and Kevin Wayne.
*
* @author Robert Sedgewick
* @author Kevin Wayne
*/
public class Transaction implements Comparable<Transaction> {
private final String who; // customer
private final Date when; // date
private final double amount; // amount
/**
* Initializes a new transaction from the given arguments.
*
* @param who the person involved in this transaction
* @param when the date of this transaction
* @param amount the amount of this transaction
* @throws IllegalArgumentException if {@code amount}
* is {@code Double.NaN}, {@code Double.POSITIVE_INFINITY},
* or {@code Double.NEGATIVE_INFINITY}
*/
public Transaction(String who, Date when, double amount) {
if (Double.isNaN(amount) || Double.isInfinite(amount))
throw new IllegalArgumentException("Amount cannot be NaN or infinite");
this.who = who;
this.when = when;
this.amount = amount;
}
/**
* Initializes a new transaction by parsing a string of the form NAME DATE AMOUNT.
*
* @param transaction the string to parse
* @throws IllegalArgumentException if {@code amount}
* is {@code Double.NaN}, {@code Double.POSITIVE_INFINITY},
* or {@code Double.NEGATIVE_INFINITY}
*/
public Transaction(String transaction) {
String[] a = transaction.split("\\s+");
who = a[0];
when = new Date(a[1]);
amount = Double.parseDouble(a[2]);
if (Double.isNaN(amount) || Double.isInfinite(amount))
throw new IllegalArgumentException("Amount cannot be NaN or infinite");
}
/**
* Returns the name of the customer involved in this transaction.
*
* @return the name of the customer involved in this transaction
*/
public String who() {
return who;
}
/**
* Returns the date of this transaction.
*
* @return the date of this transaction
*/
public Date when() {
return when;
}
/**
* Returns the amount of this transaction.
*
* @return the amount of this transaction
*/
public double amount() {
return amount;
}
/**
* Returns a string representation of this transaction.
*
* @return a string representation of this transaction
*/
@Override
public String toString() {
return String.format("%-10s %10s %8.2f", who, when, amount);
}
/**
* Compares two transactions by amount.
*
* @param that the other transaction
* @return { a negative integer, zero, a positive integer}, depending
* on whether the amount of this transaction is { less than,
* equal to, or greater than } the amount of that transaction
*/
public int compareTo(Transaction that) {
return Double.compare(this.amount, that.amount);
}
/**
* Compares this transaction to the specified object.
*
* @param other the other transaction
* @return true if this transaction is equal to {@code other}; false otherwise
*/
@Override
public boolean equals(Object other) {
if (other == this) return true;
if (other == null) return false;
if (other.getClass() != this.getClass()) return false;
Transaction that = (Transaction) other;
return (this.amount == that.amount) && (this.who.equals(that.who))
&& (this.when.equals(that.when));
}
/**
* Returns a hash code for this transaction.
*
* @return a hash code for this transaction
*/
public int hashCode() {
int hash = 1;
hash = 31*hash + who.hashCode();
hash = 31*hash + when.hashCode();
hash = 31*hash + ((Double) amount).hashCode();
return hash;
// return Objects.hash(who, when, amount);
}
/**
* Compares two transactions by customer name.
*/
public static class WhoOrder implements Comparator<Transaction> {
@Override
public int compare(Transaction v, Transaction w) {
return v.who.compareTo(w.who);
}
}
/**
* Compares two transactions by date.
*/
public static class WhenOrder implements Comparator<Transaction> {
@Override
public int compare(Transaction v, Transaction w) {
return v.when.compareTo(w.when);
}
}
/**
* Compares two transactions by amount.
*/
public static class HowMuchOrder implements Comparator<Transaction> {
@Override
public int compare(Transaction v, Transaction w) {
return Double.compare(v.amount, w.amount);
}
}
/**
* Unit tests the {@code Transaction} data type.
*
* @param args the command-line arguments
*/
public static void main(String[] args) {
Transaction[] a = new Transaction[4];
a[0] = new Transaction("Turing 6/17/1990 644.08");
a[1] = new Transaction("Tarjan 3/26/2002 4121.85");
a[2] = new Transaction("Knuth 6/14/1999 288.34");
a[3] = new Transaction("Dijkstra 8/22/2007 2678.40");
StdOut.println("Unsorted");
for (int i = 0; i < a.length; i++)
StdOut.println(a[i]);
StdOut.println();
StdOut.println("Sort by date");
Arrays.sort(a, new Transaction.WhenOrder());
for (int i = 0; i < a.length; i++)
StdOut.println(a[i]);
StdOut.println();
StdOut.println("Sort by customer");
Arrays.sort(a, new Transaction.WhoOrder());
for (int i = 0; i < a.length; i++)
StdOut.println(a[i]);
StdOut.println();
StdOut.println("Sort by amount");
Arrays.sort(a, new Transaction.HowMuchOrder());
for (int i = 0; i < a.length; i++)
StdOut.println(a[i]);
StdOut.println();
}
}
2.5.13 稳定性
如果一个算法能保留数组中重复元素的相对位置则可以称是稳定的.通俗说就是排序前, 有两个相同的数的相对位置是 A 在左边,A在右边,排序后A 还是在左边,A还是在右边.反之如果排序后把相同的数值A,A`的顺序打乱了,则不是稳定的.
image.png
常见排序算法的稳定性:
- 堆排序、快速排序、希尔排序、直接选择排序不是稳定的排序算法
- 基数排序、冒泡排序、直接插入排序、折半插入排序、归并排序是稳定的排序算法
首先，排序算法的稳定性大家应该都知道，通俗地讲就是能保证排序前2个相等的数其在序列的前后位置顺序和排序后它们两个的前后位置顺序相同。在简单形式化一下，如果Ai = Aj, Ai原来在位置前，排序后Ai还是要在Aj位置前。
其次，说一下稳定性的好处。排序算法如果是稳定的，那么从一个键上排序，然后再从另一个键上排序，第一个键排序的结果可以为第二个键排序所用。基数排序就 是这样，先按低位排序，逐次按高位排序，低位相同的元素其顺序再高位也相同时是不会改变的。
回到主题，现在分析一下常见的排序算法的稳定性，每个都给出简单的理由。
(1)冒泡排序
冒泡排序就是把小的元素往前调或者把大的元素往后调。比较是相邻的两个元素比较，交换也发生在这两个元素之间。所以，如果两个元素相等，我想你是不会再无 聊地把他们俩交换一下的；如果两个相等的元素没有相邻，那么即使通过前面的两两交换把两个相邻起来，这时候也不会交换，所以相同元素的前后顺序并没有改 变，所以冒泡排序是一种稳定排序算法。
(2)选择排序
选择排序是给每个位置选择当前元素最小的，比如给第一个位置选择最小的，在剩余元素里面给第二个元素选择第二小的，依次类推，直到第n-1个元素，第n个 元素不用选择了，因为只剩下它一个最大的元素了。那么，在一趟选择，如果当前元素比一个元素小，而该小的元素又出现在一个和当前元素相等的元素后面，那么 交换后稳定性就被破坏了。比较拗口，举个例子，序列5 8 5 2 9， 我们知道第一遍选择第1个元素5会和2交换，那么原序列中2个5的相对前后顺序就被破坏了，所以选择排序不是一个稳定的排序算法。
(3)插入排序
插入排序是在一个已经有序的小序列的基础上，一次插入一个元素。当然，刚开始这个有序的小序列只有1个元素，就是第一个元素。比较是从有序序列的末尾开 始，也就是想要插入的元素和已经有序的最大者开始比起，如果比它大则直接插入在其后面，否则一直往前找直到找到它该插入的位置。如果碰见一个和插入元素相 等的，那么插入元素把想插入的元素放在相等元素的后面。所以，相等元素的前后顺序没有改变，从原无序序列出去的顺序就是排好序后的顺序，所以插入排序是稳 定的。
(4)快速排序
快速排序有两个方向，左边的i下标一直往右走，当a[i] <= a[center_index]，其中center_index是中枢元素的数组下标，一般取为数组第0个元素。而右边的j下标一直往左走，当a[j] > a[center_index]。如果i和j都走不动了，i <= j, 交换a[i]和a[j],重复上面的过程，直到i>j。 交换a[j]和a[center_index]，完成一趟快速排序。在中枢元素和a[j]交换的时候，很有可能把前面的元素的稳定性打乱，比如序列为 5 3 3 4 3 8 9 10 11， 现在中枢元素5和3(第5个元素，下标从1开始计)交换就会把元素3的稳定性打乱，所以快速排序是一个不稳定的排序算法，不稳定发生在中枢元素和a[j] 交换的时刻。
(5)归并排序
归并排序是把序列递归地分成短序列，递归出口是短序列只有1个元素(认为直接有序)或者2个序列(1次比较和交换),然后把各个有序的段序列合并成一个有 序的长序列，不断合并直到原序列全部排好序。可以发现，在1个或2个元素时，1个元素不会交换，2个元素如果大小相等也没有人故意交换，这不会破坏稳定 性。那么，在短的有序序列合并的过程中，稳定是否受到破坏？没有，合并过程中我们可以保证如果两个当前元素相等时，我们把处在前面的序列的元素保存在结 果序列的前面，这样就保证了稳定性。所以，归并排序也是稳定的排序算法。
(6)基数排序
基数排序是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优 先级排序，最后的次序就是高优先级高的在前，高优先级相同的低优先级高的在前。基数排序基于分别排序，分别收集，所以其是稳定的排序算法。
(7)希尔排序(shell)
希尔排序是按照不同步长对元素进行插入排序，当刚开始元素很无序的时候，步长最大，所以插入排序的元素个数很少，速度很快；当元素基本有序了，步长很小， 插入排序对于有序的序列效率很高。所以，希尔排序的时间复杂度会比o(n^2)好一些。由于多次插入排序，我们知道一次插入排序是稳定的，不会改变相同元 素的相对顺序，但在不同的插入排序过程中，相同的元素可能在各自的插入排序中移动，最后其稳定性就会被打乱，所以shell排序是不稳定的。
(8)堆排序
我们知道堆的结构是节点i的孩子为2i和2i+1节点，大顶堆要求父节点大于等于其2个子节点，小顶堆要求父节点小于等于其2个子节点。在一个长为n 的序列，堆排序的过程是从第n/2开始和其子节点共3个值选择最大(大顶堆)或者最小(小顶堆),这3个元素之间的选择当然不会破坏稳定性。但当为n /2-1, n/2-2, ...1这些个父节点选择元素时，就会破坏稳定性。有可能第n/2个父节点交换把后面一个元素交换过去了，而第n/2-1个父节点把后面一个相同的元素没 有交换，那么这2个相同的元素之间的稳定性就被破坏了。所以，堆排序不是稳定的排序算法。
综上，得出结论: 选择排序、快速排序、希尔排序、堆排序不是稳定的排序算法，而冒泡排序、插入排序、归并排序和基数排序是稳定的排序算法。
性质T:
快速排序是最快的通用排序方法.
快速排序子所以块,是因为他的内循环的指令少,而且还利用缓存,他总是顺序的访问数据,运行时间增长量级cNlgN,这里的c比其他先行对数排序算法的相对常数值要小,增加3向切分法后,快速排序时间复杂度出现某些分布输入称为线性级cN,而其他算法还是线性对数级~cNlgN.
如果稳定性非常高,空间又不是问题.可以考虑归并算法.
java系统库的排序算法比较:
对于原始数据,采用3向切分的快速排序,对引用类型数据采用归并排序.说明对原始类型数据考虑速度,对引用类型数据考虑稳定性.
2.5.3问题的规约
使用排序算法来解决其他问题的思想是算法设计领域的基本技巧---规约的一个例子.
例子1:找出重复数: 先对数组排序,然后进行遍历数组,记录连续出现的数据的重复元素即可.还可以打印不同元素的值,所有重复元素的值.
2:优先队列.(TopM,MultiWay归并为有序的流输出).
3.中位数与顺序统计.
2.5.4.1 商业计算:
以下的算法都依赖 排序算法或者优先队列数据类型的高效实现
1.prim算法和dijkstra算法
2.kruskal算法
3.haffman压缩算法
4.字符串处理
