JAVA 程式設計與資料結構 第十九章 Sorting.

Presentation on theme: "JAVA 程式設計與資料結構 第十九章 Sorting."— Presentation transcript:

1 JAVA 程式設計與資料結構 第十九章 Sorting

2 Selection Sort Selection Sort的意義就是我們在尚未排序(unsorted)的部分，找出最小的數（或物件），然後將其移出，並且加到sorted的部分後面，直到unsorted的部分中所有的數（或物件）都移到sorted去，這樣便完成了sorting。

3 Insertion Sort Insertion Sort。Insertion Sort的意義就是將Array內的物件(comparable)分成sorted跟unsorted兩個部分。我們將unsorted內的物件逐一加入到sorted的部分，先在sorted的部分找到應該排入的位置，然後將位置空出來，然後將此物件放入該空位，如此步驟一直到unsorted內所有的物件都加入sorted的部分，便完成了sorting。

4 Shell Sort Shell Sort是為了改良Insertion Sort
先根據一個任意決定的數，稱之為Increment，來將陣列分組。例如如果Increment = 5，那便將陣列分為5的倍數，5的倍數加一…等subfiles，並分別用Insertion Sort排序。 subfile1  (x[0],x[5],x[10],…..) subfile2  (x[1],x[6],x[11],…..) subfile3  (x[2],x[7],x[12],…..) subfile4  (x[3],x[8],x[13],…..) subfile5  (x[4],x[9],x[14],…..) 然後Increment改成3 subfile1  (x[0],x[3],x[6],…..) subfile2  (x[1],x[4],x[7],…..) subfile3  (x[2],x[5],x[8],…..) 然後Increment改成1 (x[0],x[1],x[2],x[3],x[4],x[5]…..)

5 Bubble Sort x = [3,6,2,8,1] x = [3,2,6,8,1] x = [3,2,6,1,8] x = [2,3,6,1,8] x = [2,3,1,6,8] x = [2,1,3,6,8] x = [1,2,3,6,8] 演算方式為每次都自陣列之index = 0處開始比較其相鄰之數的大小，如果大小排列方式不適當，則互換(Swap)，如此最大的數便會向水中的泡泡一樣，一步一步的往上升。

6 Merge Sort Merge Sort是使用所謂的divide-and-conquer的方式來執行sorting。Divide-and conquer的意思便是將一個很大的陣列逐步的拆成較小的陣列，直到該陣列小到某一個規定值，例如一或兩個元件，然後直接將較小的陣列排序之後，再將所有的較小陣列組合成一個排序好的完整陣列。

7 Quick sort 如果S內的物件都互不相同，那麼E內的物件顯然只有一個，也就是pivot。
如果陣列S有至少兩個元件（如果只有一個或是沒有的話便無須做任何事），在其中選擇一個元件x，稱之為pivot。根據pivot的值，我們將S內的值放到三個不同的陣列內： i. L，S內小於pivot的物件 ii.E，S內等於pivot的物件 iii.G，S內大於pivot的物件 如果S內的物件都互不相同，那麼E內的物件顯然只有一個，也就是pivot。 用上述的方法遞迴(recursively)的排序L跟G。 循序將L，E跟G放回S，如此S便排序完成(Sorted)了。

8 Quick sort