songzi 2008-5-1 22:42
四种排序算法学习【超级经典】（常用算法）
[url=http://hideto.javaeye.com/blog/66718][color=#0000ff]四种排序算法学习[/color][/url]
[b]关键字:[/b] Sorting 排序
[table=98%][tr][td]无聊中eMule了一份中文版的<<算法导论>>来看，发现是1993年出版的古物，寒。
在网上google一通，发现一个网站[url=http://www.algosort.com/][color=#0000ff]Computer Programming Algorithms Directory[/color][/url]，进去先看看Sorting Algorithms部分。
所以今天学习了一下四种排序算法，见Andrew Kitchen的[url=http://www.cs.rit.edu/~atk/Java/Sorting/sorting.html][color=#0000ff]Sorting Algorithms[/color][/url]的applet动画显示。
[b]Bubble Sort[/b]
代码
[list=1]/* * @(#)BubbleSortAlgorithm.java 1.6f 95/01/31 James Gosling * * Copyright (c) 1994-1995 Sun Microsystems, Inc. All Rights Reserved. * * Permission to use, copy, modify, and distribute this software * and its documentation for NON-COMMERCIAL or COMMERCIAL purposes and * without fee is hereby granted. * Please refer to the file [url]http://java.sun.com/copy_trademarks.html[/url] * for further important copyright and trademark information and to * [url]http://java.sun.com/licensing.html[/url] for further important licensing * information for the Java (tm) Technology. * * SUN MAKES NO REPRESENTATIONS OR WARRANTIES ABOUT THE SUITABILITY OF * THE SOFTWARE, EITHER EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED * TO THE IMPLIED WARRANTIES OF MERCHANTABILITY, FITNESS FOR A * PARTICULAR PURPOSE, OR NON-INFRINGEMENT. SUN SHALL NOT BE LIABLE FOR * ANY DAMAGES SUFFERED BY LICENSEE AS A RESULT OF USING, MODIFYING OR * DISTRIBUTING THIS SOFTWARE OR ITS DERIVATIVES. * * THIS SOFTWARE IS NOT DESIGNED OR INTENDED FOR USE OR RESALE AS ON-LINE * CONTROL EQUIPMENT IN HAZARDOUS ENVIRONMENTS REQUIRING FAIL-SAFE * PERFORMANCE, SUCH AS IN THE OPERATION OF NUCLEAR FACILITIES, AIRCRAFT * NAVIGATION OR COMMUNICATION SYSTEMS, AIR TRAFFIC CONTROL, DIRECT LIFE * SUPPORT MACHINES, OR WEAPONS SYSTEMS, IN WHICH THE FAILURE OF THE * SOFTWARE COULD LEAD DIRECTLY TO DEATH, PERSONAL INJURY, OR SEVERE * PHYSICAL OR ENVIRONMENTAL DAMAGE ("HIGH RISK ACTIVITIES"). SUN * SPECIFICALLY DISCLAIMS ANY EXPRESS OR IMPLIED WARRANTY OF FITNESS FOR * HIGH RISK ACTIVITIES. */
/** * A bubble sort demonstration algorithm * SortAlgorithm.java, Thu Oct 27 10:32:35 1994 * * @author James Gosling * @version 1.6f, 31 Jan 1995 */
class BubbleSortAlgorithm extends SortAlgorithm {
void sort(int a[]) throws Exception {
for (int i = a.length; --i>=0; )
for (int j = 0; j<i; j++) {
if (stopRequested) {
return; }
if (a[j] > a[j+1]) {
int T = a[j]; a[j] = a[j+1]; a[j+1] = T; } pause(i,j); } pause(-1,-1); } [*]} [/list]
Bubble Sort is a sequential algorithm, with an average case time of O(n2).
经典的冒泡排序。这种方法的基本思想是，将待排序的元素看作是竖着排列的“气泡”，较小的元素比较轻，从而要往上浮。在冒泡排序算法中我们要对这个“气泡”序列处理
若干遍。所谓一遍处理，就是自底向上检查一遍这个序列，并时刻注意两个相邻的元素的顺序是否正确。如果发现两个相邻元素的顺序不对，即“轻”的元素在下面，就交换它
们的位置。显然，处理一遍之后，“最轻”的元素就浮到了最高位置；处理二遍之后，“次轻”的元素就浮到了次高位置。在作第二遍处理时，由于最高位置上的元素已是“最
轻”元素，所以不必检查。一般地，第i遍处理时，不必检查第i高位置以上的元素，因为经过前面i-1遍的处理，它们已正确地排好序。
以上解释来自[url=http://algorithm.diy.myrice.com/algorithm/commonalg/sort/internal_sorting/bubble_sort/bubble_sort.htm][color=#0000ff]http://algorithm.diy.myrice.com/algorithm/commonalg/sort/internal_sorting/bubble_sort/bubble_sort.htm[/color][/url]
[b]Quick Sort[/b]
代码
[list=1]/* * @(#)QSortAlgorithm.java 1.6f 95/01/31 James Gosling * * Copyright (c) 1994-1995 Sun Microsystems, Inc. All Rights Reserved. * * Permission to use, copy, modify, and distribute this software * and its documentation for NON-COMMERCIAL or COMMERCIAL purposes and * without fee is hereby granted. * Please refer to the file [url]http://java.sun.com/copy_trademarks.html[/url] * for further important copyright and trademark information and to * [url]http://java.sun.com/licensing.html[/url] for further important licensing * information for the Java (tm) Technology. * * SUN MAKES NO REPRESENTATIONS OR WARRANTIES ABOUT THE SUITABILITY OF * THE SOFTWARE, EITHER EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED * TO THE IMPLIED WARRANTIES OF MERCHANTABILITY, FITNESS FOR A * PARTICULAR PURPOSE, OR NON-INFRINGEMENT. SUN SHALL NOT BE LIABLE FOR * ANY DAMAGES SUFFERED BY LICENSEE AS A RESULT OF USING, MODIFYING OR * DISTRIBUTING THIS SOFTWARE OR ITS DERIVATIVES. * * THIS SOFTWARE IS NOT DESIGNED OR INTENDED FOR USE OR RESALE AS ON-LINE * CONTROL EQUIPMENT IN HAZARDOUS ENVIRONMENTS REQUIRING FAIL-SAFE * PERFORMANCE, SUCH AS IN THE OPERATION OF NUCLEAR FACILITIES, AIRCRAFT * NAVIGATION OR COMMUNICATION SYSTEMS, AIR TRAFFIC CONTROL, DIRECT LIFE * SUPPORT MACHINES, OR WEAPONS SYSTEMS, IN WHICH THE FAILURE OF THE * SOFTWARE COULD LEAD DIRECTLY TO DEATH, PERSONAL INJURY, OR SEVERE * PHYSICAL OR ENVIRONMENTAL DAMAGE ("HIGH RISK ACTIVITIES"). SUN * SPECIFICALLY DISCLAIMS ANY EXPRESS OR IMPLIED WARRANTY OF FITNESS FOR * HIGH RISK ACTIVITIES. */
/** * A quick sort demonstration algorithm * SortAlgorithm.java, Thu Oct 27 10:32:35 1994 * * @author James Gosling * @version 1.6f, 31 Jan 1995 */
class QSortAlgorithm extends SortAlgorithm {
void sort(int a[], int lo0, int hi0) throws Exception {
int lo = lo0;
int hi = hi0; pause(lo, hi);
if (lo >= hi) {
return; }
int mid = a[(lo + hi) / 2];
while (lo < hi) {
while (lo<hi && a[lo] < mid) { lo++; }
while (lo<hi && a[hi] > mid) { hi--; }
if (lo < hi) {
int T = a[lo]; a[lo] = a[hi]; a[hi] = T; pause(); } }
if (hi < lo) {
int T = hi; hi = lo; lo = T; } sort(a, lo0, lo); sort(a, lo == lo0 ? lo+1 : lo, hi0); }
void sort(int a[]) throws Exception { sort(a, 0, a.length-1); pause(-1,-1); } [*]} [/list]
Quick Sort is a sequential algorithm, with an average case time of O(n log n).
快速排序的基本思想是基于分治策略的。对于输入的子序列L[p..r]，如果规模足够小则直接进行排序，否则分三步处理：
1，分解(Divide)：将输入的序列L[p..r]划分成两个非空子序列L[p..q]和L[q+1..r]，使L[p..q]中任一元素的值不大于L[q+1..r]中任一元素的值。
2，递归求解(Conquer)：通过递归调用快速排序算法分别对L[p..q]和L[q+1..r]进行排序。
3，合并(Merge)：由于对分解出的两个子序列的排序是就地进行的，所以在L[p..q]和L[q+1..r]都排好序后不需要执行任何计算L[p..r]就已排好序。
这个解决流程是符合分治法的基本步骤的。因此，快速排序法是分治法的经典应用实例之一。
以上解释来自[url=http://algorithm.diy.myrice.com/algorithm/commonalg/sort/internal_sorting/quick_sort/quick_sort.htm][color=#0000ff]http://algorithm.diy.myrice.com/algorithm/commonalg/sort/internal_sorting/quick_sort/quick_sort.htm[/color][/url]
[b]Odd-Even Transposition Sort[/b]
代码
[list=1]/* * @(#)OETransSortAlgorithm.java 95/11/22 Andrew Kitchen * */
/** * An Odd-Even Transposition sort demonstration algorithm * * @author Andrew Kitchen * @version 22 Nov 1995 */
class OETransSortAlgorithm extends SortAlgorithm {
void sort(int a[]) throws Exception { pause(0,a.length-1);
for (int i = 0; i < a.length/2; i++ ) {
if (stopRequested) {
return; }
for (int j = 0; j+1 < a.length; j += 2)
if (a[j] > a[j+1]) {
int T = a[j]; a[j] = a[j+1]; a[j+1] = T; } pause(); pause();
for (int j = 1; j+1 < a.length; j += 2)
if (a[j] > a[j+1]) {
int T = a[j]; a[j] = a[j+1]; a[j+1] = T; } pause(); pause(); } pause(-1,-1); } [*]} [/list]
Odd-Even Transposition Sort is a parallel algorithm, with an worst case time of O(n), running on n processors. Its absolute speed up
is O(log n), so its efficiency is O((log n)/n).
主要思想为奇偶位两个循环并行排序。
[b]Shear Sort[/b]
代码
[list=1]/** * A shear sort demonstration algorithm * SortAlgorithm.java, Thu Nov 27 1995 * * author Andrew Kitchen */
class ShearSortAlgorithm extends SortAlgorithm {
private
int Log, Rows, Cols;
void sort(int a[]) throws Exception {
int pow=1, div=1;
int h[];
for(int i=1; i*i<=a.length; i++)
if (a.length % i == 0) div = i; Rows = div; Cols = a.length / div;
for(Log=0; pow<=Rows; Log++) pow = pow * 2;
h = new
int[Rows];
for (int i=0; i<Rows; i++) h[i]=i*Cols;
for (int k=0; k<Log; k++) {
for (int j=0; j<Cols/2; j++) {
for (int i=0; i<Rows; i++) sortPart1(a,i*Cols,(i+1)*Cols,1,(i%2==0?true:false)); apause(h);
for (int i=0; i<Rows; i++) sortPart2(a,i*Cols,(i+1)*Cols,1,(i%2==0?true:false)); apause(h); }
for (int j=0; j<Rows/2; j++) {
for (int i=0; i<Cols; i++) sortPart1(a,i,Rows*Cols+i,Cols,true); apause(h);
for (int i=0; i<Cols; i++) sortPart2(a,i,Rows*Cols+i,Cols,true); apause(h); } }
for (int j=0; j<Cols/2; j++) {
for (int i=0; i<Rows; i++) sortPart1(a,i*Cols,(i+1)*Cols,1,true); apause(h);
for (int i=0; i<Rows; i++) sortPart2(a,i*Cols,(i+1)*Cols,1,true); apause(h); }
for (int i=0; i<Rows; i++) h[i]=-1; apause(h); }
private
void sortPart1(int a[], int Lo, int Hi, int Nx, boolean Up) throws Exception {
for (int j = Lo; j+Nx<Hi; j+=2*Nx)
if ((Up && a[j] > a[j+Nx]) || !Up && a[j] < a[j+Nx]) {
int T = a[j]; a[j] = a[j+Nx]; a[j+Nx] = T; } }
private
void sortPart2(int a[], int Lo, int Hi, int Nx, boolean Up) throws Exception {
for (int j = Lo+Nx; j+Nx<Hi; j+=2*Nx)
if ((Up && a[j] > a[j+Nx]) || !Up && a[j] < a[j+Nx]) {
int T = a[j]; a[j] = a[j+Nx]; a[j+Nx] = T; } } [*]} [/list]
Shear Sort is a parallel algorithm, with an worst case time of O(n1/2 log n), running on n processors. Its absolute speed up is
O(n1/2), so its efficiency is O(1/n1/2).
主要思想为将N个数的数组分配到长度为sqrt(N)的grid，然后分别对行和列并行排序。[/td][/tr][/table]