3、排序算法
1）內部排序：
歸并排序沪么、交換排序（冒泡排序硼婿、快排）、選擇排序禽车、插入排序
冒泡排序
（1）比較相鄰的元素寇漫。如果第一個比第二個大，就交換他們兩個殉摔。
（2）對每一對相鄰元素作同樣的工作猪腕，從開始第一對到結尾的最后一對。這步做完后钦勘，最后的元素會是最大的數陋葡。
（3）針對所有的元素重復以上的步驟，除了最后一個彻采。
（4）持續(xù)每次對越來越少的元素重復上面的步驟腐缤，直到沒有任何一對數字需要比較。
時間復雜度：O(n^2)肛响，最優(yōu)時間復雜度：O(n)岭粤，平均時間復雜度：O(n^2)
public static void bubbleSort(Comparable[] a) {
??? int j, flag;
??? Comparable temp;
??? for (int i = 0; i
??????? flag = 0;
??????? for (j = 1; j
??????????? if(a[j].compareTo(a[j - 1]) < 0) {
??????????????? temp = a[j];
??????????????? a[j] = a[j -1];
??????????????? a[j - 1] =temp;
??????????????? flag = 1;
??????????? }
??????? }
??????? //如果沒有交換，代表已經排序完畢特笋，直接返回
??????? if (flag == 0) {
????? ??????return;
??????? }
??? }
}
插入排序
（1）從第一個元素開始剃浇，該元素可以認為已經被排序
（2）取出下一個元素，在已經排序的元素序列中從后向前掃描
（3）如果該元素（已排序）大于新元素猎物，將該元素移到下一位置
（4）重復步驟3虎囚，直到找到已排序的元素小于或者等于新元素的位置
（5）將新元素插入到該位置后
（6）重復步驟2~5
時間復雜度：O(n^2)，最優(yōu)時間復雜度：O(n),平均時間復雜度：O(n^2)
public static void insertionSort(Comparable[] a) {
??? int length = a.length;
??? Comparable temp;
??? for (int i = 1; i??< length; i++) {
??????? for (int j = i; j> 0 && a[j].compareTo(a[j - 1]) < 0; j--) {
??????????? temp = a[j];
??????????? a[j] = a[j - 1];
??????????? a[j - 1] = temp;
??????? }
??? }
}
// 對實現Comparable的類型進行排序蔫磨，先將大的元素都向右移動淘讥，減少一半交換次數
public static void insertionSort(Comparable[] a) {
??? int length = a.length;
??? Comparable temp;
??? int j;
??? for (int i = 1; i??< length; i++) {
? ? ? temp = a[i];
??????? for (j = i; j > 0&& temp.compareTo(a[j - 1]) < 0; j--) {
??????????? a[j] = a[j - 1];
??????? }
??????? a[j] = temp;
??? }
}
選擇排序
首先在未排序序列中找到最小元素，存放到排序序列的起始位置堤如，然后蒲列，再從剩余未排序元素中繼續(xù)尋找最小元素窒朋，然后放到已排序序列的末尾。
時間復雜度：O(n^2)蝗岖，最優(yōu)時間復雜度：O(n^2)侥猩，平均時間復雜度：O(n^2)
public static Integer[] selectSort(Integer[] arr)
{
??? List sortList = new ArrayList<>();
??? List numList =?new LinkedList(Arrays.asList(arr));
? ? int len = arr.length;
? ?for (int i = 0; i < len; i++)
??? {
? ? ? ? int smallest =findSmallest(numList);
??????? arr[i] = numList.get(smallest);
??????? numList.remove(smallest);
??? }
return arr;
}
private static int findSmallest(List numList)
{
int smallest = numList.get(0);
int smallestIndex = 0;
int len = numList.size();
for (int i = 0; i < len; i++)
??? {
if (numList.get(i) < smallest)
??????? {
??????????? smallest = numList.get(i);
??????????? smallestIndex = i;
??????? }
??? }
return smallestIndex;
}
希爾排序
希爾排序通過將比較的全部元素分為幾個區(qū)域來提升插入排序的性能。這樣可以讓一個元素可以一次性地朝最終位置前進一大步抵赢。然后算法再取越來越小的步長進行排序拭宁，算法的最后一步就是普通的插入排序，但是到了這步瓣俯，需排序的數據幾乎是已排好的了（此時插入排序較快）。
時間復雜度：根據步長而不同兵怯，最優(yōu)時間復雜度：O(n),平均時間復雜度：根據步長而不同
public static void shellSort(Comparable[] a) {
??? int length = a.length;
??? int h = 1;
??? Comparable temp;
??? while (h < length /3) {
??????? h = 3 * h + 1;
??? }
??? while (h >= 1) {
??????? for (int i = h; i< length; i++) {
??????????? for (int j = i;j >= h && a[j].compareTo(a[j - h]) < 0; j -= h) {
??????????????? temp = a[j];
??????????????? a[j] = a[j -h];
??????????????? a[j - h] =temp;
??????????? }
??????? }
??????? h /= 3;
??? }
}
堆排序
（1）創(chuàng)建最大堆（Build_Max_Heap）：將堆所有數據重新排序
（2）堆排序（HeapSort）：移除位在第一個數據的根節(jié)點彩匕，并做最大堆調整的遞歸運算
時間復雜度：O(nlogn)，最優(yōu)時間復雜度：O(nlogn),平均時間復雜度：O(nlogn)
public static void heapSort(Comparable[] a) {
??? int length = a.length;
??? Comparable temp;
??? for (int k = length / 2;k >= 1; k--) {
??????? sink(a, k, length);
??? }
??? while (length > 0) {
??????? temp = a[0];
??????? a[0] = a[length -1];
??????? a[length - 1] =temp;
??????? length--;
??????? sink(a, 1, length);
??? }
}
private static void sink(Comparable[] a, int k, int n) {
??? Comparable temp;
??? while (2 * k <= n) {
??????? int j = 2 * k;
??????? if (j < n&& a[j - 1].compareTo(a[j]) < 0) {
?????? ?????j++;
??????? }
??????? if (a[k -1].compareTo(a[j - 1]) >= 0) {
??????????? break;
??????? }
??????? temp = a[k - 1];
??????? a[k - 1] = a[j - 1];
??????? a[j - 1] = temp;
??????? k = j;
??? }
}
歸并排序
歸并操作（merge）媒区，也叫歸并算法驼仪，指的是將兩個已經排序的序列合并成一個序列的操作。歸并排序算法依賴歸并操作袜漩。
時間復雜度：O(nlogn)绪爸，最優(yōu)時間復雜度：O(n),平均時間復雜度：O(nlogn),空間復雜度O(n)
private staticComparable[] aux;
// 自頂向下
public staticvoid mergeSort(Comparable[] a) {
??? aux = new Comparable[a.length];
??? mergeSort(a, 0, a.length - 1);
}
public static void mergeSort(Comparable[] a, int lo, int hi) {
??? if (hi <= lo) {
??????? return;
??? }
??? int mid = (lo + hi)>>> 1;
??? mergeSort(a, lo, mid);
??? mergeSort(a, mid + 1,hi);
??? merge(a, lo, mid, hi);
}
public static void merge(Comparable[] a, int lo, int mid, int hi){
??? int i = lo, j = mid + 1;
??? for (int k = lo; k <=hi; k++) {
??????? aux[k] = a[k];
??? }
??? for (int k = lo; k <=hi; k++) {
??????? if (i > mid) {
??????????? a[k] = aux[j++];
??????? } else if (j >hi) {
??????????? a[k] = aux[i++];
??????? } else if(aux[j].compareTo(aux[i]) < 0) {
??????????? a[k] = aux[j++];
??????? } else {
??????????? a[k] = aux[i++];
??????? }
??? }
}
快速排序
快排步驟：
?*（1）選擇基準值；
?*（2）將數組分為兩個子數組：小于基準值的元素和大于基準值的元素宙攻；
?*（3）對這兩個子數組進行快速排序奠货。
時間復雜度：O(n^2)，最優(yōu)時間復雜度：O(nlogn),平均時間復雜度：O(nlogn)
快排的時間復雜度跟選取基準的方法有關座掘，一下是默認選擇了第一個元素作為基準递惋，隨機性較大。
可以在序列中選取開始中間結尾三個數的中位數作為基準溢陪，進行優(yōu)化萍虽。
public static List quickSort(List list)
{
int length = list.size();
if (length < 2)
??? {
??????? System.out.println("The size of list less than 2!");
? ? ? ? return list; // 基線條件：為空或者只包含一個元素的數組是“有序”的
??? }
int pivot = list.get(length / 2); // 遞歸條件，如果總是將第一個元素用作基準值形真，則最差算法運行時間為O（n^2）,如果選擇中間元素為基準值則最佳算法時間為O（nlogn）杉编，每次隨機選擇基準值則平均算法時間為O（nlogn）
??? List<Integer> less = new ArrayList<>();
??? List greater =?new ArrayList<>();
??? list.remove(length / 2);
for (int element : list)
??? {
if (element < pivot)
??????? {
??????????? less.add(element);
// 由所有小于基準值的元素組成的子數組
??????? }
else
??? ????{
??????????? greater.add(element);
// 由所有大于基準值的元素組成的子數組
??????? }
??? }
??? System.out.println("less is " + less);
??? List lessSort =quickSort(less);
// 對小于基準值的子數組遞歸執(zhí)行快速排序
??? List greaterSort =quickSort(greater);// 對大于基準值的子數組遞歸執(zhí)行快速排序
??? lessSort.add(pivot); // 組合小于基準值的子數組、基準值咆霜、大于基準值的子數組
??? lessSort.addAll(greaterSort);
return lessSort;
}
public static void main(String[] args)
{
??? List list =?new ArrayList<>();
??? list.add(9);
??? list.add(6);
??? list.add(0);
??? list.add(10);
??? list.add(-1);
??? list.add(2);
??? System.out.println(quickSort(list));
??? List linkedList =?new ArrayList<>(Arrays.asList(new Integer[] { 1, 2, 3 }));
??? linkedList.remove(1);
??? System.out.println(linkedList);
}
2）外部排序：
掌握利用內存和外部存儲處理超大數據集邓馒，至少要理解過程和思路、排序的穩(wěn)定性和效率等蛾坯。
1绒净、定義問題
??? 外部排序指的是大文件的排序，即待排序的記錄存儲在外存儲器上偿衰，待排序的文件無法一次裝入內存挂疆，需要在內存和外部存儲器之間進行多次數據交換改览，以達到排序整個文件的目的。外部排序最常用的算法是多路歸并排序缤言，即將原文件分解成多個能夠一次性裝入內存的部分宝当，分別把每一部分調入內存完成排序。然后胆萧，對已經排序的子文件進行多路歸并排序庆揩。
2、處理過程
? （1）按可用內存的大小跌穗，把外存上含有n個記錄的文件分成若干個長度為L的子文件订晌，把這些子文件依次讀入內存，并利用有效的內部排序方法對它們進行排序蚌吸，再將排序后得到的有序子文件重新寫入外存锈拨；
? （2）對這些有序子文件逐趟歸并，使其逐漸由小到大羹唠，直至得到整個有序文件為止奕枢。
內存排序環(huán)節(jié)：磁盤中的數據序列被分割成多個段（假定內存有限）讀入到內存中，在內存中用模板sort實現排序過程佩微，效率高缝彬！
多路歸并排序環(huán)節(jié)：依次從從每個已排序的段文件中（什么是段文件，看上面的內存排序環(huán)節(jié)哺眯，形象了點９惹场！）讀入一個數據奶卓，注意是一個壳贪；挑選最小的寫入的目標文件中。
假設文件需要分成k塊讀入寝杖，需要從小到大進行排序违施。
（1）依次讀入每個文件塊，在內存中對當前文件塊進行排序（應用恰當的內排序算法）瑟幕。此時磕蒲，每塊文件相當于一個由小到大排列的有序隊列。
（2）在內存中建立一個最小值堆只盹，讀入每塊文件的隊列頭辣往。
（3）彈出堆頂元素，如果元素來自第i塊殖卑，則從第i塊文件中補充一個元素到最小值堆站削。彈出的元素暫存至臨時數組。
（4）當臨時數組存滿時孵稽，將數組寫至磁盤许起，并清空數組內容十偶。
（5）重復過程（3）、（4）园细，直至所有文件塊讀取完畢惦积。
? 先從一個例子來看外排序中的歸并是如何進行的？
? 假設有一個含10000個記錄的文件猛频，首先通過10次內部排序得到10個初始歸并段R1～R10狮崩，其中每一段都含1000個記錄。然后對它們作如圖10.11所示的兩兩歸并鹿寻，直至得到一個有序文件為止如下圖
多路歸并排序
多路歸并排序算法在常見數據結構書中都有涉及睦柴。從2路到多路（k路），增大k可以減少外存信息讀寫時間毡熏，但k個歸并段中選取最小的記錄需要比較k-1次坦敌，為得到u個記錄的一個有序段共需要(u-1)(k-1)次，若歸并趟數為s次招刹，那么對n個記錄的文件進行外排時，內部歸并過程中進行的總的比較次數為s(n-1)(k-1)窝趣，若共有m個歸并段疯暑，則s=logkm,所以總的比較次數為： (向上取整)(logkm)(k-1)(n-1)=(向上取整)(log2m/log2k)(k-1)(n-1)，而(k-1)/log2k隨k增而增因此內部歸并時間隨k增長而增長了哑舒，抵消了外存讀寫減少的時間妇拯，這樣做不行，由此引出了“敗者樹”tree of loser的使用洗鸵。在內部歸并過程中利用敗者樹將k個歸并段中選取最小記錄比較的次數降為(向上取整)(log2k)次使總比較次數為(向上取整)(log2m)(n-1)越锈，與k無關。
多路歸并排序算法的過程大致為：
1）首先將k個歸并段中的首元素關鍵字依次存入b[0]--b[k-1]的葉子結點空間里膘滨，然后調用CreateLoserTree創(chuàng)建敗者樹甘凭，創(chuàng)建完畢之后最小的關鍵字下標（即所在歸并段的序號）便被存入ls[0]中。然后不斷循環(huán)：
2）把ls[0]所存最小關鍵字來自于哪個歸并段的序號得到為q火邓，將該歸并段的首元素輸出到有序歸并段里丹弱，然后把下一個元素關鍵字放入上一個元素本來所 在的葉子結點b[q]中，調用Adjust順著b[q]這個葉子結點往上調整敗者樹直到新的最小的關鍵字被選出來铲咨，其下標同樣存在ls[0]中躲胳。循環(huán)這個 操作過程直至所有元素被寫到有序歸并段里。
敗者樹
葉子節(jié)點記錄k個段中的最小數據纤勒，然后兩兩進行比賽坯苹。敗者樹是在雙親節(jié)點中記錄下剛剛進行完的這場比賽的敗者，讓勝者去參加更高一層的比賽摇天。決賽粹湃，根節(jié)點記錄輸者恐仑，所以需要重建一個新的根節(jié)點，記錄勝者(如下圖節(jié)點0）再芋。
示例：我們這里以四路歸并為例菊霜，假設每個歸并段已經在輸入緩沖區(qū)如下圖。
每路的第一個元素為勝利樹的葉子節(jié)點济赎，（5,7）比較出5勝出7失敗成為其根節(jié)點鉴逞，（29,9）比較9勝出29失敗成為其根節(jié)點，勝者（5,9）進行下次的比賽9失敗成為其根節(jié)點5勝出輸出到輸出緩沖區(qū)司训。由第一路歸并段輸出构捡，所有將第一路歸并段的第二個元素加到葉子節(jié)點如下圖：
加入葉子節(jié)點16進行第二次的比較，跟勝利樹一樣壳猜，由于右子樹葉子節(jié)點沒有發(fā)生變化其右子樹不用再繼續(xù)比較勾徽。
位圖算法：
問題描述：
輸入：給定一個文件，里面最多含有n個不重復的正整數（也就是說可能含有少于n個不重復正整數）统扳，且其中每個數都小于等于n喘帚，n=10^7。
輸出：得到按從小到大升序排列的包含所有輸入的整數的列表咒钟。
條件：最多有大約1MB的內存空間可用吹由，但磁盤空間足夠。且要求運行時間在5分鐘以下朱嘴，10秒為最佳結果倾鲫。
位圖方案。熟悉位圖的朋友可能會想到用位圖來表示這個文件集合萍嬉。例如正如編程珠璣一書上所述乌昔，用一個20位長的字符串來表示一個所有元素都小于20的簡單的非負整數集合，邊框用如下字符串來表示集合{1,2,3,5,8,13}：
0 1 1 1 0 1 0 01 0 0 0 0 1 0 0 0 0 0 0
上述集合中各數對應的位置則置1壤追，沒有對應的數的位置則置0磕道。
參考編程珠璣一書上的位圖方案，針對我們的10^7個數據量的磁盤文件排序問題行冰，我們可以這么考慮捅厂，由于每個7位十進制整數表示一個小于1000萬的整數。我們可以使用一個具有1000萬個位的字符串來表示這個文件资柔，其中焙贷，當且僅當整數i在文件中存在時，第i位為1贿堰。采取這個位圖的方案是因為我們面對的這個問題的特殊性：1辙芍、輸入數據限制在相對較小的范圍內，2、數據沒有重復故硅，3庶灿、其中的每條記錄都是單一的整數，沒有任何其它與之關聯的數據吃衅。
所以往踢，此問題用位圖的方案分為以下三步進行解決：
第一步，將所有的位都置為0徘层，從而將集合初始化為空峻呕。
第二步，通過讀入文件中的每個整數來建立集合趣效，將每個對應的位都置為1瘦癌。
第三步，檢驗每一位跷敬，如果該位為1讯私，就輸出對應的整數。
經過以上三步后西傀，產生有序的輸出文件斤寇。令n為位圖向量中的位數（本例中為1000 0000），程序可以用偽代碼表示如下：
上述的位圖方案拥褂，共需要掃描輸入數據兩次娘锁，具體執(zhí)行步驟如下：
第一次，只處理1—4999999之間的數據肿仑，這些數都是小于5000000的致盟，對這些數進行位圖排序碎税，只需要約5000000/8=625000Byte尤慰，也就是0.625M，排序后輸出雷蹂。
第二次伟端，掃描輸入文件時，只處理4999999-10000000的數據項匪煌，也只需要0.625M（可以使用第一次處理申請的內存）责蝠。
因此，總共也只需要0.625M
位圖的的方法有必要強調一下萎庭，就是位圖的適用范圍為針對不重復的數據進行排序霜医，若數據有重復，位圖方案就不適用了驳规。
