算法Sedgewick第四版-第1章基础-2.1Elementary Sortss-006归并排序(Mergesort)
2024-10-11 16:43:29
一、
1.特点
(1)merge-sort : to sort an array, divide it into two halves, sort the two halves (recursively), and then merge the results. As you will see, one of mergesort’s most attractive properties is that it guarantees to sort any array of N items in time proportional to N log N. Its prime disadvantage is that it uses extra space proportional to N.
(2)
(3)
(4)
(5)
2.缺点
■ Mergesort is not optimal with respect to space usage.
■ The worst case may not be likely in practice.
■ Operations other than compares (such as array accesses) may be important.
■ One can sort certain data without using any compares.
Thus, we shall be considering several other sorting methods in this book.
3.介绍
二、
1.代码
package algorithms.mergesort22; import algorithms.util.StdIn;
import algorithms.util.StdOut; /******************************************************************************
* Compilation: javac Merge.java
* Execution: java Merge < input.txt
* Dependencies: StdOut.java StdIn.java
* Data files: http://algs4.cs.princeton.edu/22mergesort/tiny.txt
* http://algs4.cs.princeton.edu/22mergesort/words3.txt
*
* Sorts a sequence of strings from standard input using mergesort.
*
* % more tiny.txt
* S O R T E X A M P L E
*
* % java Merge < tiny.txt
* A E E L M O P R S T X [ one string per line ]
*
* % more words3.txt
* bed bug dad yes zoo ... all bad yet
*
* % java Merge < words3.txt
* all bad bed bug dad ... yes yet zoo [ one string per line ]
*
******************************************************************************/ /**
* The <tt>Merge</tt> class provides static methods for sorting an
* array using mergesort.
* <p>
* For additional documentation, see <a href="http://algs4.cs.princeton.edu/22mergesort">Section 2.2</a> of
* <i>Algorithms, 4th Edition</i> by Robert Sedgewick and Kevin Wayne.
* For an optimized version, see {@link MergeX}.
*
* @author Robert Sedgewick
* @author Kevin Wayne
*/
public class Merge { // This class should not be instantiated.
private Merge() { } // stably merge a[lo .. mid] with a[mid+1 ..hi] using aux[lo .. hi]
private static void merge(Comparable[] a, Comparable[] aux, int lo, int mid, int hi) {
// precondition: a[lo .. mid] and a[mid+1 .. hi] are sorted subarrays
assert isSorted(a, lo, mid);
assert isSorted(a, mid+1, hi); // copy to aux[]
for (int k = lo; k <= hi; k++) {
aux[k] = a[k];
} // merge back to a[]
int i = lo, j = mid+1;
for (int k = lo; k <= hi; k++) {
if (i > mid) a[k] = aux[j++];
else if (j > hi) a[k] = aux[i++];
else if (less(aux[j], aux[i])) a[k] = aux[j++];
else a[k] = aux[i++];
} // postcondition: a[lo .. hi] is sorted
assert isSorted(a, lo, hi);
} // mergesort a[lo..hi] using auxiliary array aux[lo..hi]
private static void sort(Comparable[] a, Comparable[] aux, int lo, int hi) {
if (hi <= lo) return;
int mid = lo + (hi - lo) / 2;
sort(a, aux, lo, mid);
sort(a, aux, mid + 1, hi);
merge(a, aux, lo, mid, hi);
} /**
* Rearranges the array in ascending order, using the natural order.
* @param a the array to be sorted
*/
public static void sort(Comparable[] a) {
Comparable[] aux = new Comparable[a.length];
sort(a, aux, 0, a.length-1);
assert isSorted(a);
} /***************************************************************************
* Helper sorting functions.
***************************************************************************/ // is v < w ?
private static boolean less(Comparable v, Comparable w) {
return v.compareTo(w) < 0;
} // exchange a[i] and a[j]
private static void exch(Object[] a, int i, int j) {
Object swap = a[i];
a[i] = a[j];
a[j] = swap;
} /***************************************************************************
* Check if array is sorted - useful for debugging.
***************************************************************************/
private static boolean isSorted(Comparable[] a) {
return isSorted(a, 0, a.length - 1);
} private static boolean isSorted(Comparable[] a, int lo, int hi) {
for (int i = lo + 1; i <= hi; i++)
if (less(a[i], a[i-1])) return false;
return true;
} /***************************************************************************
* Index mergesort.
***************************************************************************/
// stably merge a[lo .. mid] with a[mid+1 .. hi] using aux[lo .. hi]
private static void merge(Comparable[] a, int[] index, int[] aux, int lo, int mid, int hi) { // copy to aux[]
for (int k = lo; k <= hi; k++) {
aux[k] = index[k];
} // merge back to a[]
int i = lo, j = mid+1;
for (int k = lo; k <= hi; k++) {
if (i > mid) index[k] = aux[j++];
else if (j > hi) index[k] = aux[i++];
else if (less(a[aux[j]], a[aux[i]])) index[k] = aux[j++];
else index[k] = aux[i++];
}
} /**
* Returns a permutation that gives the elements in the array in ascending order.
* @param a the array
* @return a permutation <tt>p[]</tt> such that <tt>a[p[0]]</tt>, <tt>a[p[1]]</tt>,
* ..., <tt>a[p[N-1]]</tt> are in ascending order
*/
public static int[] indexSort(Comparable[] a) {
int N = a.length;
int[] index = new int[N];
for (int i = 0; i < N; i++)
index[i] = i; int[] aux = new int[N];
sort(a, index, aux, 0, N-1);
return index;
} // mergesort a[lo..hi] using auxiliary array aux[lo..hi]
private static void sort(Comparable[] a, int[] index, int[] aux, int lo, int hi) {
if (hi <= lo) return;
int mid = lo + (hi - lo) / 2;
sort(a, index, aux, lo, mid);
sort(a, index, aux, mid + 1, hi);
merge(a, index, aux, lo, mid, hi);
} // print array to standard output
private static void show(Comparable[] a) {
for (int i = 0; i < a.length; i++) {
StdOut.println(a[i]);
}
} /**
* Reads in a sequence of strings from standard input; mergesorts them;
* and prints them to standard output in ascending order.
*/
public static void main(String[] args) {
//String[] a = StdIn.readAllStrings();
Integer[] a = {3,1,2,5,4};
Merge.sort(a);
show(a);
}
}
2.可视化
package algorithms.mergesort22; import algorithms.util.StdDraw;
import algorithms.util.StdRandom; /******************************************************************************
* Compilation: javac MergeBars.java
* Execution: java MergeBars M N
* Dependencies: StdDraw.java
*
* Sort N random real numbers between 0 and 1 (with M disintct values)
* using mergesort with cutoff to insertion sort.
*
* Visualize the results by ploting bars with heights proportional
* to the values.
*
* % java MergeBars 1000 96
*
* Comments
* --------
* - suggest removing the 10% default StdDraw border
* - if image is too large, it may not display properly but you can
* still save it to a file
*
******************************************************************************/ public class MergeBars {
private static final int VERTICAL = 70;
private static final int CUTOFF = 12; private static int numberOfRows;
private static int row = 0; // stably merge a[lo .. mid] with a[mid+1 .. hi] using aux[lo .. hi]
public static void merge(double[] a, double[] aux, int lo, int mid, int hi) { // copy to aux[]
for (int k = lo; k <= hi; k++) {
aux[k] = a[k];
} // merge back to a[]
int i = lo, j = mid+1;
for (int k = lo; k <= hi; k++) {
if (i > mid) a[k] = aux[j++];
else if (j > hi) a[k] = aux[i++];
else if (less(aux[j], aux[i])) a[k] = aux[j++];
else a[k] = aux[i++];
}
} // mergesort a[lo..hi] using auxiliary array aux[lo..hi]
private static void sort(double[] a, double[] aux, int lo, int hi) {
int N = hi - lo + 1;
if (N <= CUTOFF) {
insertionSort(a, lo, hi);
show(a, lo, hi);
return;
}
if (hi <= lo) return;
int mid = lo + (hi - lo) / 2;
sort(a, aux, lo, mid);
sort(a, aux, mid + 1, hi);
merge(a, aux, lo, mid, hi);
show(a, lo, hi);
} public static void sort(double[] a) {
double[] aux = new double[a.length];
sort(a, aux, 0, a.length-1);
} // sort from a[lo] to a[hi] using insertion sort
private static void insertionSort(double[] a, int lo, int hi) {
for (int i = lo; i <= hi; i++)
for (int j = i; j > lo && less(a[j], a[j-1]); j--)
exch(a, j, j-1);
} private static boolean less(double v, double w) {
return v < w;
} private static void exch(double[] a, int i, int j) {
double t = a[i];
a[i] = a[j];
a[j] = t;
} // draw one row of trace
private static void show(double[] a, int lo, int hi) {
double y = numberOfRows - row - 1;
for (int k = 0; k < a.length; k++) {
if (k < lo) StdDraw.setPenColor(StdDraw.LIGHT_GRAY);
else if (k > hi) StdDraw.setPenColor(StdDraw.LIGHT_GRAY);
else StdDraw.setPenColor(StdDraw.BLACK);
StdDraw.filledRectangle(k, y + a[k]*.25, .25, a[k]*.25);
}
row++;
} public static void main(String[] args) {
int M = Integer.parseInt(args[0]);
int N = Integer.parseInt(args[1]);
if (args.length == 3) {
long seed = Long.parseLong(args[2]);
StdRandom.setSeed(seed);
}
double[] a = new double[N];
double[] b = new double[N];
for (int i = 0; i < N; i++) {
a[i] = (1 + StdRandom.uniform(M)) / (double) M;
b[i] = a[i];
} // precompute the number of rows
StdDraw.show(0);
numberOfRows = 0;
sort(b);
numberOfRows = row;
row = 0;
StdDraw.clear(); StdDraw.setCanvasSize(800, numberOfRows*VERTICAL);
StdDraw.show(0);
StdDraw.square(.5, .5, .5);
StdDraw.setXscale(-1, N);
StdDraw.setYscale(-0.5, numberOfRows);
StdDraw.show(0);
sort(a);
StdDraw.show(0);
}
}
最新文章
- Jmeter响应内容为文件
- 细数iOS上的那些安全防护
- SQL获取汉字首字母
- PP66 EEPPPPMM SSyysstteemm AAddmmiinniissttrraattiioonn GGuuiiddee 16 R1
- POJ 2136
- Spring Auto-Wiring Beans with @Autowired annotation
- Thread学习
- LeetCode FindMinimuminRotatedSorteArray &&FindMinimuminRotatedSorteArray2
- 七，WPF的元素绑定
- CP_THREAD_ACP与CP_ACP
- Dynamic Web Module 3.0 requires Java 1.6 or newer报错
- 工作流activiti-03数据查询（流程定义 流程实例 代办任务） 以及个人小练习
- centos7 opera济览器安装
- Github干货系列：C++资源集合-
- SSM整合XML版(Maven Project)
- mysql关联、子查询索引优化
- 协议并发测试工具 BoHexTest
- .NET MVC+ EF+通用存储过程实现增删改功能以及使用事物处理
- luoguP1080 国王游戏 （贪心+高精度）
- mysql5.6以上（适用5.7）免安装版本 终极配置