記錄今天的“演算法第四版”進度
今天學習的內容有：插入排序(insertion sort)和希爾排序(shell sort)講解了排序的一個應用，洗牌(shuffling)，那么下面我將簡單的總結下今天的學習內容，當作一種記錄和復習，
插入排序(Insertion sort)
與選擇排序不一樣，插入排序不需要做非常多次比較操作，而是需要做更多次換位操作，選擇排序對于已經排列好的一組資料進行排序和完全打亂的資料進行排序，其花費的時間是沒有差別的，但是插入排序考慮到了陣列本身并不完全是無序的，其中有原本就是順序的資料，也有逆序的資料，其中逆序的資料越多，插入排序所需要花費的時間越久，
因此，在插入排序中，我們需要做的事情有：
- 將索引定在陣列的n=1的位置上，遍歷整個陣列
- 在第一個回圈內，將第n個索引所對應的資料與前一個進行比較，如果逆序就進行交換，直到第一個資料，此時n之前的資料已經是有序的，
public class Insertion
{
public static void sort(Comparable[] a)
{ // 將a[]按升序排列
int N = a.length;
for (int i = 1; i < N; i++)
{ // 將 a[i] 插入到 a[i-1]、a[i-2]、a[i-3]...之中
for (int j = i; j > 0 && less(a[j], a[j-1]); j--)
exch(a, j, j-1);
}
}
}可視化如下：
希爾排序(Shell sort)
那么還有什么方法可以縮減運算量呢？我們注意到插入排序其實做了很多沒有必要或者說是多余的換位操作，有些元素的位置本來就是正確的，
希爾排序的思想是使陣列中任意間隔為
h
的元素都是有序的，這樣的陣列被稱為
h
有序陣列
，換句話說，一個 h
有序陣列
就是
h 個互相獨立的有序陣列編織在一起組成的一個陣列，在進行排序時，如果
h
很大，我們就能將元素移動到很遠的地方，為實作更小的
h
有序
創造方便，
我們注意到一個非常有意思的性質，比如說我們先對一組資料進行h=7的有序排列 ，再進行h=3的有序排列，那么此時的排列對于h=7的情況來說依舊是有效的，按照h=3x+1的辦法來進行h有序陣列排序，就可以節省很大一部分的交換操作，減少實際的操作時間，
代碼如下(摘自演算法第四版)
public class Shell
{
public static void sort(Comparable[] a)
{ // 將a[]按升序排列
int N = a.length;
int h = 1;
while (h < N/3) h = 3*h + 1; // 1, 4, 13, 40, 121, 364, 1093, ...
while (h >= 1)
{ // 將陣列變為h有序
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);
}
h = h/3;
}
}
// less()、exch()、isSorted()和main()方法見“排序演算法類模板”
}希爾排序的可視化
洗牌今天懶得寫了，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/258105.html
標籤：其他
上一篇：Webots Google圖形化編程（2021.01.14推出）
下一篇：C語言 | 求字串的長度