|
|
| 又稱分類”。按關鍵字大小遞增或遞減的次序，對文件中的全部記錄重新排列的過程。是計算機程序設計中的一種重要運算。分內部排序和外部排序兩大類。內部排序中常用的方法有插入排序、冒泡排序、快速排序、堆排序、基數排序等。 |
|
排序是計算機內經常進行的一種操作，其目的是將一組“無序”的記錄序列調整為“有序”的記錄序列。
內部排序和外部排序：
若整個排序過程不需要訪問外存便能完成，則稱此類排序問題為內部排序；
反之，若參加排序的記錄數量很大，
整個序列的排序過程不可能在內存中
完成，則稱此類排序問題為外部排序。
內部排序的過程是一個逐步擴大
記錄的有序序列長度的過程。
一、冒泡排序
已知一組無序數據a、a、……a[n]，需將其按升序排列。首先比較a與a的值，若a大於a則交換兩者的值，否則不變。再比較a與a的值，若a大於a則交換兩者的值，否則不變。再比較a與a，以此類推，最後比較a[n-1]與a[n]的值。這樣處理一輪後，a[n]的值一定是這組數據中最大的。再對a~a[n-1]以相同方法處理一輪，則a[n-1]的值一定是a~a[n-1]中最大的。再對a~a[n-2]以相同方法處理一輪，以此類推。共處理n-1輪後a、a、……a[n]就以升序排列了。
優點：穩定，比較次數已知；
缺點：慢，每次衹能移動相鄰兩個數據，移動數據的次數多。
二、選擇排序
已知一組無序數據a、a、……a[n]，需將其按升序排列。首先比較a與a的值，若a大於a則交換兩者的值，否則不變。再比較a與a的值，若a大於a則交換兩者的值，否則不變。再比較a與a，以此類推，最後比較a與a[n]的值。這樣處理一輪後，a的值一定是這組數據中最小的。再將a與a~a[n]以相同方法比較一輪，則a的值一定是a~a[n]中最小的。再將a與a~a[n]以相同方法比較一輪，以此類推。共處理n-1輪後a、a、……a[n]就以升序排列了。
優點：穩定，比較次數與冒泡排序一樣，數據移動次數比冒泡排序少；
缺點：相對之下還是慢。
三、插入排序
已知一組升序排列數據a、a、……a[n]，一組無序數據b、b、……b[m]，需將二者合併成一個升序數列。首先比較b與a的值，若b大於a，則跳過，比較b與a的值，若b仍然大於a，則繼續跳過，直到b小於a數組中某一數據a[x]，則將a[x]~a[n]分別嚮後移動一位，將b插入到原來a[x]的位置這就完成了b的插入。b~b[m]用相同方法插入。（若無數組a，可將b當作n=1的數組a）
優點：穩定，快；
缺點：比較次數不一定，比較次數越少，插入點後的數據移動越多，特別是當數據總量龐大的時候，但用鏈表可以解决這個問題。
四、縮小增量排序
由希爾在1959年提出，又稱希爾排序。
已知一組無序數據a、a、……a[n]，需將其按升序排列。發現當n不大是，插入排序的效果很好。首先取一增量d(d<n)，將a、a[1+d]、a[1+2d]……列為第一組，a、a[2+d]、a[2+2d]……列為第二組……，a[d]、a[2d]、a[3d]……列為最後一組以次類推，在各組內用插入排序，然後取d'<d，重複上述操作，直到d=1。
優點：快，數據移動少；
缺點：不穩定，d的取值是多少，應取多少個不同的值，都無法確切知道，衹能憑經驗來取。
五、快速排序
快速排序是冒泡排序的改進版，是目前已知的最快的排序方法。
已知一組無序數據a、a、……a[n]，需將其按升序排列。首先任取數據a[x]作為基準。比較a[x]與其它數據並排序，使a[x]排在數據的第k位，並且使a~a[k-1]中的每一個數據<a[x]，a[k+1]~a[n]中的每一個數據>a[x]，然後采用分治的策略分別對a~a[k-1]和a[k+1]~a[n]兩組數據進行快速排序。
優點：極快，數據移動少；
缺點：不穩定。 |
|
排序是計算機內經常進行的一種操作，其目的是將一組“無序”的記錄序列調整為“有序”的記錄序列。
內部排序和外部排序：
若整個排序過程不需要訪問外存便能完成，則稱此類排序問題為內部排序；
反之，若參加排序的記錄數量很大，整個序列的排序過程不可能在內存中完成，則稱此類排序問題為外部排序。
內部排序的過程是一個逐步擴大記錄的有序序列長度的過程。
內排序的方法有許多種，按所用策略不同，可歸納為五類：插入排序、選擇排序、交換排序、歸併排序和分配排序。
其中，插入排序主要包括直接插入排序和希爾排序兩種；選擇排序主要包括直接選擇排序和堆排序；交換排序主要包括氣（冒）泡排序和快速排序。
一、冒泡排序
已知一組無序數據a、a、……a[n]，需將其按升序排列。首先比較a與a的值，若a大於a則交換兩者的值，否則不變。再比較a與a的值，若a大於a則交換兩者的值，否則不變。再比較a與a，以此類推，最後比較a[n-1]與a[n]的值。這樣處理一輪後，a[n]的值一定是這組數據中最大的。再對a~a[n-1]以相同方法處理一輪，則a[n-1]的值一定是a~a[n-1]中最大的。再對a~a[n-2]以相同方法處理一輪，以此類推。共處理n-1輪後a、a、……a[n]就以升序排列了。
優點：穩定；
缺點：慢，每次衹能移動相鄰兩個數據。
二、選擇排序
冒泡排序的改進版。
每一趟從待排序的數據元素中選出最小（或最大）的一個元素，順序放在已排好序的數列的最後，直到全部待排序的數據元素排完。
選擇排序是不穩定的排序方法。
n個記錄的文件的直接選擇排序可經過n-1趟直接選擇排序得到有序結果：
①初始狀態：無序區為R[1..n]，有序區為空。
②第1趟排序
在無序區R[1..n]中選出關鍵字最小的記錄R[k]，將它與無序區的第1個記錄R交換，使R[1..1]和R[2..n]分別變為記錄個數增加1個的新有序區和記錄個數減少1個的新無序區。
……
③第i趟排序
第i趟排序開始時，當前有序區和無序區分別為R[1..i-1]和R(1≤i≤n-1)。該趟排序從當前無序區中選出關鍵字最小的記錄 R[k]，將它與無序區的第1個記錄R交換，使R[1..i]和R分別變為記錄個數增加1個的新有序區和記錄個數減少1個的新無序區。
這樣，n個記錄的文件的直接選擇排序可經過n-1趟直接選擇排序得到有序結果。
優點：移動數據的次數已知（n-1次）；
缺點：比較次數多。
三、插入排序
已知一組升序排列數據a、a、……a[n]，一組無序數據b、b、……b[m]，需將二者合併成一個升序數列。首先比較b與a的值，若b大於a，則跳過，比較b與a的值，若b仍然大於a，則繼續跳過，直到b小於a數組中某一數據a[x]，則將a[x]~a[n]分別嚮後移動一位，將b插入到原來a[x]的位置這就完成了b的插入。b~b[m]用相同方法插入。（若無數組a，可將b當作n=1的數組a）
優點：穩定，快；
缺點：比較次數不一定，比較次數越少，插入點後的數據移動越多，特別是當數據總量龐大的時候，但用鏈表可以解决這個問題。
三、縮小增量排序
由希爾在1959年提出，又稱希爾排序(shell排序)。
已知一組無序數據a、a、……a[n]，需將其按升序排列。發現當n不大時，插入排序的效果很好。首先取一增量d(d<n)，將a、a[1+d]、a[1+2d]……列為第一組，a、a[2+d]、a[2+2d]……列為第二組……，a[d]、a[2d]、a[3d]……列為最後一組以次類推，在各組內用插入排序，然後取d'<d，重複上述操作，直到d=1。
優點：快，數據移動少；
缺點：不穩定，d的取值是多少，應取多少個不同的值，都無法確切知道，衹能憑經驗來取。
四、快速排序
快速排序是目前已知的最快的排序方法。
已知一組無序數據a、a、……a[n]，需將其按升序排列。首先任取數據a[x]作為基準。比較a[x]與其它數據並排序，使a[x]排在數據的第k位，並且使a~a[k-1]中的每一個數據<a[x]，a[k+1]~a[n]中的每一個數據>a[x]，然後采用分治的策略分別對a~a[k-1]和a[k+1]~a[n]兩組數據進行快速排序。
優點：極快，數據移動少；
缺點：不穩定。
五、箱排序
已知一組無序正整數數據a、a、……a[n]，需將其按升序排列。首先定義一個數組x[m],且m>=a、a、……a[n]，接着循環n次，每次x[a]++.
優點：快，效率達到O(1)
缺點：數據範圍必須為正整數並且比較小
六、歸併排序
歸併排序是多次將兩個或兩個以上的有序表合併成一個新的有序表。最簡單的歸併是直接將兩個有序的子表合併成一個有序的表。
歸併排序是穩定的排序.即相等的元素的順序不會改變.如輸入記錄 1(1) 3(2) 2(3) 2(4) 5(5) (括號中是記錄的關鍵字)時輸出的 1(1) 2(3) 2(4) 3(2) 5(5) 中的2 和 2 是按輸入的順序.這對要排序數據包含多個信息而要按其中的某一個信息排序,要求其它信息盡量按輸入的順序排列時很重要.這也是它比快速排序優勢的地方. |
|
paixu
排序
sorting
將文件中的各個記錄按關鍵字值（見數據查找）的遞升或遞降次序重新排列成為一個新的記錄序列，這是數據處理的一項基本功能。經過排序的文件便於分類比較或進一步處理。例如，對於一個未經排序的文件，在查畢整個文件之前不能判定某個給定的關鍵字值確實不在該文件中。組織排序之後，則無需查畢整個文件就能作出這一判斷。排序是數據處理，特別是批處理任務中最常用的操作之一。對計算機內存儲器中的記錄進行排序稱為內排序。對存儲在外部設備中的文件記錄排序稱為外排序，外排序需要以內存儲器作為過渡介質來進行。
內排序 常用的內排序有三種算法。
①綫性查找排序算法 以綫性查找法為基礎的排序算法。在內存儲器中確定一個與被排序文件同樣大小的區域作為新區，用綫性查找法在原文件中找出具有最小（或最大）關鍵字值的記錄,放入新區第一記錄位置,再從原文件中找出第二個最小（或最大）關鍵字值的記錄，放入新區第二個記錄位置。重複上述過程，直至原文件中所有記錄都已放入新區為止。這種算法簡單，但效率很低，衹適於對少量記錄的排序。
②互換排序算法 對原文件中不合指定順序的兩相鄰記錄互換位置。有三種互換算法。a.綫性查找互換算法：將第一記錄逐一與其後面的記錄比較，並與較小關鍵字值的記錄互換，結果使最小關鍵字值的記錄處於第一記錄位置。然後從第二記錄開始，重複上述過程，使第二小關鍵字值記錄處於第二記錄位置。如此繼續，直到關鍵字值最大的記錄處於最後記錄位置為止。b.相鄰比較互換算法：將相鄰記錄比較，並按指定次序互換其位置。第一個記錄和第二個記錄比較，第二個和第三個比較，直到倒數第二個和最後一個比較。從頭到尾算完一遍，然後進行第二遍，直至某一遍沒有一個比較需要互換位置時為止。c.起泡互換排序算法：首先將第二個記錄與第一個記錄比較，必要時互換。然後將第三個記錄與第二個記錄比較，必要時互換。若互換，則新的第二個記錄與第一個記錄比較，必要時互換。第三個記錄再與第二個記錄比較，重複上述過程。使一個記錄如同起泡一樣，上升到適當的位置，在它上面再沒有關鍵字值比它大（或小）的記錄。直到最後一個記錄經過比較而不再上升為止。
③合併排序算法 先將文件中的各個記錄分為合乎次序的若幹組，然後分別兩組兩組地合併，使組數減少一半；再如此繼續合併，直到全部合為一組為止。
外排序 外排序包括兩個步驟。①把要排序的文件中的一組記錄讀入內存儲器的排序區，對讀入的記錄按上面講到的內排序法進行排序，排序之後輸出到外存儲器。重複這一過程，每次一組，直到原文件所有記錄被處理完畢。②將上一步分組排好序的記錄兩組兩組地合併排序。在內存容量允許的條件下，每組中包含的記錄越大越好，這樣可減少合併的次數。
（羅大衛）
|
|
- : rank, reorder, Sorting
- n.: compositor, ordering, taxis
- v.: sort
- vt.: collate
|
|
- n. mise en ordre
|
|
| 編程 | 算法 | 分治 | vb | 超鏈分析 | 搜索引擎 | 相關性 | pagerank | | 計算機 | 冒泡排序 | 冒泡 | 冒泡法 | 選擇 | 定位 | 交換 | 程序 | | 數據結構 | 更多結果... |
|