1. 基本規(guī)則
- 排序類算法模板
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接口
實現(xiàn)了Comparable接口的數(shù)據(jù)類型：Integer、String涝影、Double都實現(xiàn)了Comparable接口燃逻。創(chuàng)建自己的數(shù)據(jù)類型時臂痕，我們也要實現(xiàn)Comparable接口就能使用該模板進行排序。必須要實現(xiàn)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必須實現(xiàn)一個全序關(guān)系：
①自反性：對所有的v=v
②反對稱性：對所有v<w都有v>w片效，且v=w時w=v
③傳遞性
- 排序成本模型：比較次數(shù)和訪問數(shù)組的次數(shù)
- 額外的內(nèi)存使用
2. 選擇排序
-
思想：
首先英古，找到數(shù)組中最小的元素召调，其次將它和數(shù)組的第一個元素交換位置。再次只嚣，在剩下的元素中找到最小的元素和數(shù)組的第二個元素交換位置艺沼。如此往復(fù)，直到將整個數(shù)組排序调鲸。不斷選擇剩余元素中的最小者藐石。
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
選擇排序 分析：
①運行時間和輸入無關(guān)
②數(shù)據(jù)移動是最少的
③長度為N的數(shù)組需要交換N次于微，比較次數(shù)：(N-1)+(N-2)+...1=N(N-1)/2~
3. 插入排序
-
思想：
想象打撲克牌，一張一張地把牌插入到適當(dāng)?shù)匚恢们ぁＴ谟嬎銠C的視線中恋腕，為了要給插入的元素騰出空間，我們需要將其余所有元素在插入之前都向后移動一位祈远。插入排序所需要的時間取決于輸入元素中的初始順序商源。
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. 希爾排序
- 思想：
基于插入排序的快速排序算法器罐。對于大規(guī)模亂序的數(shù)組插入排序很慢渐行，是因為它只會交換相鄰的元素，因此元素只能一點一點移動肴沫。希爾排序改進了插入排序算法蕴忆，交換不相鄰的元素以對數(shù)組的局部進行排序颤芬，并最終用插入排序?qū)⒕植坑行虻臄?shù)組排序。 關(guān)鍵：使數(shù)組中任意間隔為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);
}
-
Example
希爾排序 -
分析：
希爾排序是基于插入排序的一種算法， 在此算法基礎(chǔ)之上增加了一個新的特性站蝠，提高了效率汰具。希爾排序的時間復(fù)雜度與增量序列的選取有關(guān)，希爾排序時間復(fù)雜度的下界是n*log2n沉衣。希爾排序沒有快速排序算法快 O(n(logn))，因此中等大小規(guī)模表現(xiàn)良好减牺，對規(guī)模非常大的數(shù)據(jù)排序不是最優(yōu)選擇豌习。但是比O( n^2 )復(fù)雜度的算法快得多。并且希爾排序非常容易實現(xiàn)拔疚，算法代碼短而簡單。 此外稚失，希爾算法在最壞的情況下和平均情況下執(zhí)行效率相差不是很多栋艳，與此同時快速排序在最壞的情況下執(zhí)行的效率會非常差。
