java演算法（一）—初級排序演算法
- 黄舟原創
- 2017-03-01 11:15:051348瀏覽
程式=資料結構+演算法。對於那些建構專案的框架不是由我們來編寫的，真正能判斷一個專案的水平高低的是我們在其中自訂的資料結構是否方便、簡潔、耦合度低；我們實現這些方法的演算法是否快速、有效、不易出錯。如果你想做的不是那種每天從早幹到晚的搬磚工作，學會演算法、品析資料結構絕對是你成長水準的必經之路。
（一）排序演算法
演算法和程式語言關係是緊密的，但又不只依賴某種語言。在不考慮實作語言的情況下，我們通常會有以下這些種排序方法：
#選擇排序
- ##插入排序
- 希爾排序
- #歸併排序
- 快速排序
比較和交換
##我們不隻隻是空泛的講述這幾種排序方法，在介紹完5種排序演算法之後，我們會將這些方法總結並與javaAPI連結。除此之外，為了方便我們對這幾種排序方法的實現，我們現在這裡使用了一點輔助的方法，這些輔助方法非常簡單，他們存在的作用就是為了讓我們的程式碼變得簡潔。
/** * 比较两个大小不同的数字，如果第一个参数比较小则返回true。 * * @param v 第一个数字 * @param w 第二个数字 * @return 返回比较结果 */ public static boolean less(int v , int w){ if(v<w) return true; return false; } /** * 交换数组中两个索引的内容 * * @param arr 数组 * @param v 第一个索引 * @param w 第二个索引 */ public static void exch(int[] arr,int v ,int w){ int temp=arr[v]; arr[v]= arr[w]; arr[w] = temp; } /** * 打印数组 * * @param arr 要显示的数组 */ public static void show(int[] arr){ for(int i=0;i<arr.length;i++) System.out.println(arr[i]); }- （二）排序成本模型
在java中，絕大多數的元素都是對象，對這些對象的主鍵的描述是透過Comparable的機制來實現的，有了Comparable才有了順序和排序的概念。那麼如何去研究一個排序方法到底是快還是慢，到底有多快，到底效率如何呢？我們將從下面的幾個方面來研究各個排序演算法的成本。
（我們需要計算比較和交換的數量，來評判排序的成本）
#時間（一個排序演算法所花費的時間，或在某種情況下所花費的時間）
額外的記憶體使用（有的排序方法需要使用額外的記憶體空間，有的則不需要）
#針對某些特殊的排序演算法我們會給出特殊的成本估計的方法，對於大多數的排序方法，我們都會在最後討論這個方法在什麼情況下適用——畢竟那些沒用的排序早已被淘汰。
（三）選擇排序選擇排序是所有排序中最簡單的一種排序演算法。選擇排序的核心思想是：
在數組前端維護一個有序的子數組，每次找到後半部分無序數組中最小的元素，將其與前端結尾後的第一個無序元素交換，使這個元素變成有序。當有序部分數組元素等於總元素個數時，排序完成。
通俗的說，我們先找到陣列中最小的那個元素，把它和第一個元素交換，如果第一個元素就是最小的元素，那麼它和它自己交換
。然後我們從第二個元素開始到結尾再找到最小的那個元素，將它與數組第二個元素交換，以此類推，不斷地選擇剩餘元素中最小的那個。1.比較與交換
選擇排序有固定的比較次數N2/2，與固定的交換次數N
。 ######對於比較次數來講，選擇排序在第一次需要從第一個元素比較到最後一個元素才能知道最小的元素是什麼。在第二次，需要N-1次比較才能知道最小元素。總計需要N+(N-1)+(N-2)+ ··· + 1 = N###2###/2 次。 ######因為由於演算法的程式設計原因，即使最小的這個元素已經在正確的位置上了，我們還是需要將它自己和自己交換位置，所以交換的次數也是固定的為N次。 #########2.時間#########選擇排序的運行時間是固定的約為N###2###/2次比較所需時間（N## #2###/2的情況下，我們基本上可以將交換的N次時間忽略）。如果我們在無法預估一個排序方法的運行時間時，我們現在已經至少知道了一種保底的排序方法，只要你的排序方法使用得當，它的運行時間絕對不會超過N###2## #/2次比較的時間。 ###3.java实现
package Sort;/**
*
* @author QuinnNorris 选择排序
*/public class Sort1 {
/**
* @param args
*/
public static void main(String[] args) { // TODO Auto-generated method stub
int[] arr = { 9, 8, 7, 6, 5, 4, 3, 2, 1, 0 }; // 测试数组
sort(arr); // 调用排序算法
Tool.show(arr); // 打印
} /**
* 用选择排序将arr升序排列
*
* @param arr
* 所要排列的数组
*/
public static void sort(int[] arr) {
for (int i = 0; i < arr.length; i++) {
int min = i;
for (int j = i + 1; j < arr.length; j++)
if (Tool.less(arr[j], arr[min]))
min = j;
Tool.exch(arr, min, i);
}
}
}4.特点
选择排序非常简单，他有两个很鲜明的特点：
1.运行时间和输入无关
运行时间和输入无关，好听的讲就是无论多么乱的数据都会在固定的时间之内完成排序，但是更多的情况下，这种前一遍比较不能为后一遍比较提供任何价值的算法是非常费时的。夸张的讲，如果我们要完成某个几乎接近有序的数组的排序，你会发现，使用选择排序所需的时间和去排序那些无序的数组竟然是完全一样的。这在很多情况下是大家不能接受的。
2.数据移动最少
为了保证最少的交换数据，我们不断的进行比较，每次的交换都会百分之百的把一个数字放在正确的位置上。其他的任何排序方法都不具备这个特性。
（四）插入排序
在选择排序中，一个几乎有序的数组和一个完全无序的数组所需时间是一样的。插入排序则完美的解决了这个问题：
从数组的头部开始，通过不断的一次一位的比较和交换，让每个数据都能插入前端有序部分中自己合理的位置，当所有的元素都完成一遍操作后，排序完成。
我们将要排序的那个元素和前面一位元素比较，如果比前面的元素小，则交换位置，这个元素继续和再前面的元素比较，如果仍然小则继续交换，知道前面的元素小于该元素位置。这个时候，这个不断交换的元素就在这个数组中达到了自己合适的位置，刚才其他被交换的元素，都像是“向后移动一个位置”，为这个元素挪出了空间，这就是插入排序。这种排序很类似我们在打桥牌时整理牌的方法，不断地将牌按照大小从后向前插入。
1.比较和交换
在一个随机排序而且主键不重复的数组中，平均情况下插入排序需要N2/4次比较以及N2/4次交换。在最坏的情况下需要N2/2次比较和N2/2次交换，最好情况下需要N-1次比较和0次交换。
这个平均情况是怎么计算得出的呢？通常情况下，我们认为数组中的一个数字在整个数组中会被移动半个数组的长度（在平均情况下，每个数字都会移动到有序部分的中间位置，在这种情况下，数字自己的移动和被向后“推”的移动加起来长度为半个数组），在半个数组的移动算作平均情况下，我们得到N2/4的比较和交换次数。
2.时间
我们可以看出，用插入排序算法排序的时间和这个数组情况有很大关系，如果数组是非常无序的，它的速度要慢于选择排序，但是如果我们现在要排序的数组是几乎完全有序的，那么它的时间将会非常的小。就像我们手中握着一副全都排好顺序的扑克牌，这时你抽到一张梅花9，你可以非常快的将它插到你的手牌中。
数组中每个元素距离他的最终位置不远
一个有序数组的大数组接一个小数组
数组中只有几个元素的位置不正确
上述的三种情况下，使用插入算法会非常非常有效。事实上，当顺序错误的数量很少的时候，插入排序会比其他任何排序算法都快。
3.java实现
package Sort;/**
*
* @author QuinnNorris 插入排序
*/public class Sort2 {
/**
* @param args
*/
public static void main(String[] args) { // TODO Auto-generated method stub
int[] arr = { 9, 8, 7, 6, 5, 4, 3, 2, 1, 0 }; // 测试数组
sort(arr); // 调用排序算法
Tool.show(arr); // 打印
} /**
* 用插入排序将arr升序排列
*
* @param arr
* 所要排列的数组
*/
public static void sort(int[] arr) {
for (int i = 0; i < arr.length; i++)
for (int j = i; j > 0; j--)
if (Tool.less(arr[j], arr[j - 1]))
Tool.exch(arr, j, j - 1);
}
}4.特点
在插入排序中，因为他的速度和原有的序列有很大关系。在这里，我们将在原序列中位置顺序颠倒的一对数字叫做倒置，这只是我们起的一个名字，它表示两个数字的位置是错误的（a应该在b的前面，但是在数组中a在b的后面，无论a与b相隔多远，都可以称a、b是一个倒置）。插入排序具有以下几点特性：
交换和比较的次数相同
比较的次数大于等于倒置的数量
比较的次数小于等于倒置数量加上数组的大小再减一
除此之外，插入排序作为一种初级排序算法，会在之后的高级排序算法中作为一个中间算法频频出现，我们会在以后再见到他。
（五）选择算法和插入算法比较
这两种算法是如此的相似，以至于我们非常好奇想将他们比较一番。对于随机排序无重复的数组，插入排序和选择排序的运行时间都是平方级别的，所以两者只比应该是一个较小的常数。
（六）希爾排序
我們接下來要介紹的一種排序演算法並不屬於初級排序演算法，但是它實際上是運用了插入演算法的技術來實現的，我們不妨在這裡一起討論一下。希爾排序是指：
透過由大到小的製定一個常數h的值，透過插入排序使數組中任意間隔為h的元素都是有序的。不斷減少h的大小，直到h=1，使得整個陣列都是有序的。
我們還是用橋牌來做比喻，一開始的時候你手上有一副毫無順序的牌，你可以一個一個的去找位置，但是這時你突然覺得這種方法太慢了，於是你打算先粗略的篩一遍。你把一些牌放的有順序，但是其他有的牌並沒有順序，就這樣，你篩了幾遍你的牌最後讓所有的手牌都變得有序。這就是希爾排序。
在我們需要排序的陣列成千上萬時，我們通常可以去採用希爾排序。
在希爾排序中，我們先定義一個h，我們以h為間隔，劃分出一個子數組，我們用插入演算法將這個子數組排序。然後不斷地讓h變小，我們再去將新的陣列排序，最後當h為1時，這一遍排序讓所有的資料都有序。
1.優勢
那麼希爾排序有什麼優勢呢？我們知道，插入排序的優勢是對於已經部分有序的序列排序極快，而且對於小型數組排序速度很快。我們的希爾排序就是結合了這兩個優點。在h較大的時候，整個陣列比較小，插入排序較快，在h較小的時候整個陣列已經漸漸趨於有序，這時使用插入排序也是非常好的選擇。可以說希爾排序集合了這兩個優點，整體的時間是比較快的。
2.時間
對於希爾排序，我們並不打算按照我們上面的分析方式來分析，原因如下。首先希爾排序非常難以研究交換和比較，因為關鍵因素在於h，h是一個常量，我們可以透過設定不同的h來改變這種跳躍的間隔。而且沒有一個明確的解釋：h到底遵循什麼規律效果最優（通常我們可以採用3*h+1 即：1，4，13，40，121，364…這組數字來作為h）。 h既然不能被確定那麼也就沒有什麼最優時間的說法。
3.實際應用
有經驗的程式設計師有的時候會採用希爾排序，因為對於中等大小的數組，希爾排序的運行時間是可以接受的。他的程式碼量很小，而且不用使用額外的記憶體空間。或許我們確實有更快的演算法但是對於很大的N，他們很有可能只比希爾排序快了不到兩倍的時間。而且非常的複雜。如果你需要排序但是沒有一個系統的排序函數，或者可以考慮使用希爾排序，然後再去考慮是否將它替換成更高級的排序方法。
程式=資料結構+演算法。對於那些建構專案的框架不是由我們來編寫的，真正能判斷一個專案的水平高低的是我們在其中自訂的資料結構是否方便、簡潔、耦合度低；我們實現這些方法的演算法是否快速、有效、不易出錯。如果你想做的不是那種每天從早幹到晚的搬磚工作，學會演算法、品析資料結構絕對是你成長水準的必經之路。
以上就是java演算法（一）—初級排序演算法的內容，更多相關內容請關注PHP中文網（www.php.cn）！