Decrease-and-Conquer-10
Decrease-and-Conquer分為兩種
和Devide-and-Conquer的區(qū)別在于Decrease-and-Conquer只解決一個(gè)實(shí)例犬庇，而Devide-and-Conquer解決很多相同的子實(shí)例
-
Decrease-and-Conquer by-a-Constant
In this approach, the size of the problem is reduced by some constant in each iteration of the algorithm.包含
- Insertion Sort
- topological sorting
- Decrease-and-Conquer by-a-Factor
- Decrease-by-a-constant-factor
binary search - Decrease-by-a-variable-factor
interpolation search
5.1Insertion Sort
-
步驟：
1.sort the first n ? 1 items, then
將前n-1個(gè)元素排好序
2.locate the cell that should hold the last item,
shift all elements to its right to the right, and
place the last element.
將最后一個(gè)元素與前面的元素做對(duì)比墓塌，若最后一個(gè)元素小于對(duì)比的元素卫旱，則對(duì)比的元素往后移，直至找到小于最后一個(gè)元素的值掏导，并將最后一個(gè)元素放入這個(gè)元素之后提针。
Insertion Sort總結(jié)
1.最差時(shí)間復(fù)雜度和平均時(shí)間復(fù)雜度都為Theta(n^2)，當(dāng)數(shù)組為逆向排序時(shí)
2.但時(shí)間復(fù)雜度為Theta(n)锋叨，當(dāng)數(shù)組為 almost-sorted input。
3.有的數(shù)組的-1或0或最后一個(gè)位置會(huì)為空宛篇，用來(lái)放置哨兵post a sentinel娃磺，放置最小值，用以結(jié)束循環(huán)叫倍，可以將排序的速度提高一個(gè)常數(shù)偷卧，但不改變Theta其仍為n^2
4.Insertion Sort易于理解應(yīng)用
5.適用于小的數(shù)組
6.Insertion Sort是stable的，是in-place的
7.decrease-and-conquer by a constant
5.2 Shellsort: Motivation
間隔選擇：
1.從最大的k開(kāi)始吆倦，然后用小一點(diǎn)的ks听诸，若為小數(shù)組則選用2/3最佳
2.認(rèn)為1、4蚕泽、13蛇更、40、121赛糟、364派任、1093是最好的間隔選擇，n=n*3+1璧南，但也要考慮運(yùn)行的次數(shù)（例20000應(yīng)該選擇364掌逛，雖然1093是可以容納的更大間隔數(shù)，但要做1093次Insertion Sort）
-
步驟
1.可以把這個(gè)數(shù)組看作是k個(gè)列表的交錯(cuò)
2.使用插入排序分別對(duì)每個(gè)列表進(jìn)行排序
3.然后使用最后一次插入排序?qū)Φ玫降恼麄€(gè)數(shù)組進(jìn)行排序
Shellsort總結(jié)
1.相較于 insertion sort來(lái)說(shuō)比較次數(shù)更少司倚，選擇最好間隔差時(shí)(n=n3+1)的最差時(shí)間復(fù)雜度為* O(n^1.5).
2.猜想時(shí)間復(fù)雜度有可能接近O(n^1.25).
3.Shellsort不是stable的豆混，是in-place的**
5.3Binary Search
This is a well-known approach for searching for an element k in a sorted array
-
步驟
1.首先與數(shù)組的中間元素A[m]進(jìn)行比較。
2.如果A[m] = k动知，就做完了皿伺。
3.如果A[m] >k，遞歸搜索子數(shù)組直到A[m?1]盒粮。
4.如果A[m] <k鸵鸥，從A[m + 1]遞歸搜索子數(shù)組。
10-11
Binary Search總結(jié)
1.最差時(shí)間復(fù)雜度為Theta(log2(n)),當(dāng)要找的k不在隊(duì)列的時(shí)候是最差的情況丹皱。
2.平均時(shí)間復(fù)雜度為Theta(logn)
5.4Russian Peasant Multiplication
5.5Lomuto Partitioning分區(qū)
用于找中間值妒穴，或者第幾小的值
Partitioning an array around some pivot element p means reorganizing the array so that all elements to the left of p are no greater than p, while those to the right are no smaller. 分區(qū)，將小于p的放置在左邊摊崭，大于等于p的放在右邊
5.4Quickselect
Finding the kth-smallest Element
-
步驟
1.利用Lomuto Partitioning，將數(shù)組A的第一個(gè)元素找到其是第幾小的值(設(shè)為m)
2.將A按照m分為兩個(gè)部分呢簸，若要找的k小于m在前一部分找矮台，若要找的k大于m在后一部分找乏屯，重復(fù)1
Quickselect 總結(jié)
1.最差時(shí)間復(fù)雜度為Theta(n^2)，當(dāng)數(shù)組已經(jīng)排好序時(shí)
2.平均時(shí)間復(fù)雜度為Theta(n)
3.Quickselect是stable的瘦赫，是in-place的
5.5Interpolation Search
總結(jié)
1.適用于數(shù)組是已經(jīng)排好序的情況
2.適用于非均勻分布的大數(shù)組
3.找到要找的k更靠近最大值還是最小值
