首先 選擇排序 和 冒泡排序 的時間復雜度比 快速排序 希爾排序 高
選擇排序(Selection Sort)每一趟從待排序的記錄中選出關鍵字最小的記錄,順序放在已排好序的子文件的最後,直到全部記錄排序完畢。
冒泡排序(Bubble sort)原理是臨近的數字兩兩進行比較,按照從小到大或者從大到小的順序進行交換。
兩個排序演算法時間復雜度相同但冒泡排序交換次數比選擇排序多(交換比較費時)，
所以性能最差是冒泡排序
⑵ java里,幾種排序方法各有什麼優缺點
一、冒泡排序
已知一組無序數據a[1]、a[2]、……a[n]，需將其按升序排列。首先比較 a[1]與a[2]的值，若a[1]大於a[2]則交換兩者的值，否則不變。再比較a[2]與a[3]的值，若a[2]大於a[3]則交換兩者的值，否則不變。再比較a[3]與a[4]，以此類推，最後比較a[n-1]與a[n]的值。這樣處理一輪後，a[n]的值一定是這組數據中最大的。再對 a[1]~a[n-1]以相同方法處理一輪，則a[n-1]的值一定是a[1]~a[n-1]中最大的。再對a[1]~a[n-2]以相同方法處理一輪，以此類推。共處理n-1輪後a[1]、a[2]、……a[n]就以升序排列了。
優點：穩定；
缺點：慢，每次只能移動相鄰兩個數據。
二、選擇排序
冒泡排序的改進版。
每一趟從待排序的數據元素中選出最小（或最大）的一個元素，順序放在已排好序的數列的最後，直到全部待排序的數據元素排完。
選擇排序是不穩定的排序方法。
n個記錄的文件的直接選擇排序可經過n-1趟直接選擇排序得到有序結果：
①初始狀態：無序區為R[1..n]，有序區為空。
②第1趟排序
在無序區R[1..n]中選出關鍵字最小的記錄R[k]，將它與無序區的第1個記錄R[1]交換，使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[1]、a[2]、……a[n]，一組無序數據b[1]、 b[2]、……b[m]，需將二者合並成一個升序數列。首先比較b[1]與a[1]的值，若b[1]大於a[1]，則跳過，比較b[1]與a[2]的值，若b[1]仍然大於a[2]，則繼續跳過，直到b[1]小於a數組中某一數據a[x]，則將a[x]~a[n]分別向後移動一位，將b[1]插入到原來 a[x]的位置這就完成了b[1]的插入。b[2]~b[m]用相同方法插入。（若無數組a，可將b[1]當作n=1的數組a）
優點：穩定，快；
缺點：比較次數不一定，比較次數越少，插入點後的數據移動越多，特別是當數據總量龐大的時候，但用鏈表可以解決這個問題。
三、縮小增量排序
由希爾在1959年提出，又稱希爾排序(shell排序)。
已知一組無序數據a[1]、a[2]、……a[n]，需將其按升序排列。發現當n不大時，插入排序的效果很好。首先取一增量d(d<n)，將a[1]、a[1+d]、a[1+2d]……列為第一組，a[2]、a[2+d]、 a[2+2d]……列為第二組……，a[d]、a[2d]、a[3d]……列為最後一組以次類推，在各組內用插入排序，然後取d'<d，重復上述操作，直到d=1。
優點：快，數據移動少；
缺點：不穩定，d的取值是多少，應取多少個不同的值，都無法確切知道，只能憑經驗來取。
四、快速排序
快速排序是目前已知的最快的排序方法。
已知一組無序數據a[1]、a[2]、……a[n]，需將其按升序排列。首先任取數據 a[x]作為基準。比較a[x]與其它數據並排序，使a[x]排在數據的第k位，並且使a[1]~a[k-1]中的每一個數據<a[x]，a[k+1]~a[n]中的每一個數據>a[x]，然後採用分治的策略分別對a[1]~a[k-1]和a[k+1]~a[n] 兩組數據進行快速排序。
優點：極快，數據移動少；
缺點：不穩定。
五、箱排序
已知一組無序正整數數據a[1]、a[2]、……a[n]，需將其按升序排列。首先定義一個數組x[m],且m>=a[1]、a[2]、……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 是按輸入的順序.這對要排序數據包含多個信息而要按其中的某一個信息排序,要求其它信息盡量按輸入的順序排列時很重要.這也是它比快速排序優勢的地方.
⑶ 請給出java幾種排序方法
java常見的排序分為：
1 插入類排序
主要就是對於一個已經有序的序列中，插入一個新的記錄。它包括：直接插入排序，折半插入排序和希爾排序
2 交換類排序
這類排序的核心就是每次比較都要「交換」，在每一趟排序都會兩兩發生一系列的「交換」排序，但是每一趟排序都會讓一個記錄排序到它的最終位置上。它包括：起泡排序，快速排序
3 選擇類排序
每一趟排序都從一系列數據中選擇一個最大或最小的記錄，將它放置到第一個或最後一個為位置交換，只有在選擇後才交換，比起交換類排序，減少了交換記錄的時間。屬於它的排序：簡單選擇排序，堆排序
4 歸並類排序
將兩個或兩個以上的有序序列合並成一個新的序列
5 基數排序
主要基於多個關鍵字排序的。
下面針對上面所述的演算法，講解一些常用的java代碼寫的演算法
二 插入類排序之直接插入排序
直接插入排序,一般對於已經有序的隊列排序效果好。
基本思想：每趟將一個待排序的關鍵字按照大小插入到已經排序好的位置上。
演算法思路，從後往前先找到要插入的位置，如果小於則就交換，將元素向後移動，將要插入數據插入該位置即可。時間復雜度為O(n2),空間復雜度為O(1)
package sort.algorithm;
public class DirectInsertSort {
public static void main(String[] args) {
// TODO Auto-generated method stub
int data[] = { 2, 6, 10, 3, 9, 80, 1, 16, 27, 20 };
int temp, j;
for (int i = 1; i < data.length; i++) {
temp = data[i];
j = i - 1;
// 每次比較都是對於已經有序的
while (j >= 0 && data[j] > temp) {
data[j + 1] = data[j];
j--;
}
data[j + 1] = temp;
}
// 輸出排序好的數據
for (int k = 0; k < data.length; k++) {
System.out.print(data[k] + " ");
}
}
}
三 插入類排序之折半插入排序(二分法排序)
條件：在一個已經有序的隊列中，插入一個新的元素
折半插入排序記錄的比較次數與初始序列無關
思想：折半插入就是首先將隊列中取最小位置low和最大位置high，然後算出中間位置mid
將中間位置mid與待插入的數據data進行比較，
如果mid大於data，則就表示插入的數據在mid的左邊，high=mid-1;
如果mid小於data，則就表示插入的數據在mid的右邊,low=mid+1
最後整體進行右移操作。
時間復雜度O(n2),空間復雜度O(1)
package sort.algorithm;
//折半插入排序
public class HalfInsertSort {
public static void main(String[] args) {
int data[] = { 2, 6, 10, 3, 9, 80, 1, 16, 27, 20 };
// 存放臨時要插入的元素數據
int temp;
int low, mid, high;
for (int i = 1; i < data.length; i++) {
temp = data[i];
// 在待插入排序的序號之前進行折半插入
low = 0;
high = i - 1;
while (low <= high) {
mid = (low + high) / 2;
if (temp < data[mid])
high = mid - 1;
else
// low=high的時候也就是找到了要插入的位置，
// 此時進入循環中，將low加1，則就是要插入的位置了
low = mid + 1;
}
// 找到了要插入的位置，從該位置一直到插入數據的位置之間數據向後移動
for (int j = i; j >= low + 1; j--)
data[j] = data[j - 1];
// low已經代表了要插入的位置了
data[low] = temp;
}
for (int k = 0; k < data.length; k++) {
System.out.print(data[k] + " ");
}
}
}
四 插入類排序之希爾排序
希爾排序，也叫縮小增量排序，目的就是盡可能的減少交換次數，每一個組內最後都是有序的。
將待續按照某一種規則分為幾個子序列，不斷縮小規則，最後用一個直接插入排序合成
空間復雜度為O(1)，時間復雜度為O(nlog2n)
演算法先將要排序的一組數按某個增量d（n/2,n為要排序數的個數）分成若干組，每組中記錄的下標相差d.對每組中全部元素進行直接插入排序，然後再用一個較小的增量（d/2）對它進行分組，在每組中再進行直接插入排序。當增量減到1時，進行直接插入排序後，排序完成。
package sort.algorithm;
public class ShellSort {
public static void main(String[] args) {
int a[] = { 1, 54, 6, 3, 78, 34, 12, 45, 56, 100 };
double d1 = a.length;
int temp = 0;
while (true)
{
//利用這個在將組內倍數減小
//這里依次為5,3,2,1
d1 = Math.ceil(d1 / 2);
//d為增量每個分組之間索引的增量
int d = (int) d1;
//每個分組內部排序
for (int x = 0; x < d; x++)
{
//組內利用直接插入排序
for (int i = x + d; i < a.length; i += d) {
int j = i - d;
temp = a[i];
for (; j >= 0 && temp < a[j]; j -= d) {
a[j + d] = a[j];
}
a[j + d] = temp;
}
}
if (d == 1)
break;
}
for (int i = 0; i < a.length; i++)
System.out.print(a[i]+" ");
}
}
五 交換類排序之冒泡排序
交換類排序核心就是每次比較都要進行交換
冒泡排序：是一種交換排序
每一趟比較相鄰的元素，較若大小不同則就會發生交換，每一趟排序都能將一個元素放到它最終的位置！每一趟就進行比較。
時間復雜度O(n2)，空間復雜度O(1)
package sort.algorithm;
//冒泡排序：是一種交換排序
public class BubbleSort {
// 按照遞增順序排序
public static void main(String[] args) {
// TODO Auto-generated method stub
int data[] = { 2, 6, 10, 3, 9, 80, 1, 16, 27, 20, 13, 100, 37, 16 };
int temp = 0;
// 排序的比較趟數,每一趟都會將剩餘最大數放在最後面
for (int i = 0; i < data.length - 1; i++) {
// 每一趟從開始進行比較，將該元素與其餘的元素進行比較
for (int j = 0; j < data.length - 1; j++) {
if (data[j] > data[j + 1]) {
temp = data[j];
data[j] = data[j + 1];
data[j + 1] = temp;
}
}
}
for (int i = 0; i < data.length; i++)
System.out.print(data[i] + " ");
}
}
⑷ 幾種經典的數據排序及其Java實現
數據排序方法有很多，比如選擇排序、冒泡法、插入排序、希爾排序、快速排序、歸並排序等，下面給你著重介紹3種：
1、選擇排序
思想
n個記錄的文件的直接選擇排序可經過n-1趟直接選擇排序得到有序結果：
①初始狀態：無序區為R[1..n]，有序區為空。
②第1趟排序
在無序區R[1..n]中選出關鍵字最小的記錄R[k]，將它與無序區的第1個記錄R[1]交換，使R[1..1]和R[2..n]分別變為記錄個數增加1個的新有序區和記錄個數減少1個的新無序區。
……
③第i趟排序
第i趟排序開始時，當前有序區和無序區分別為R[1..i-1]和R(i..n）。該趟排序從當前無序區中選出關鍵字最小的記錄 R[k]，將它與無序區的第1個記錄R交換，使R[1..i]和R分別變為記錄個數增加1個的新有序區和記錄個數減少1個的新無序區。
排序實例
初始關鍵字 [49 38 65 97 76 13 27 49]
第一趟排序後 13 [38 65 97 76 49 27 49]
第二趟排序後 13 27 [65 97 76 49 38 49]
第三趟排序後 13 27 38 [97 76 49 65 49]
第四趟排序後 13 27 38 49 [76 97 65 49 ]
第五趟排序後 13 27 38 49 49 [97 65 76]
第六趟排序後 13 27 38 49 49 65 [97 76]
第七趟排序後 13 27 38 49 49 65 76 [97]
最後排序結果 13 27 38 49 49 65 76 97
2、冒泡法
原理
冒泡排序演算法的運作如下：
比較相鄰的元素。如果第一個比第二個大，就交換他們兩個。
對每一對相鄰元素作同樣的工作，從開始第一對到結尾的最後一對。在這一點，最後的元素應該會是最大的數。
針對所有的元素重復以上的步驟，除了最後一個。
持續每次對越來越少的元素重復上面的步驟，直到沒有任何一對數字需要比較。
演算法分析
演算法穩定性
冒泡排序就是把小的元素往前調或者把大的元素往後調。比較是相鄰的兩個元素比較，交換也發生在這兩個元素之間。所以，如果兩個元素相等，我想你是不會再無聊地把他們倆交換一下的；如果兩個相等的元素沒有相鄰，那麼即使通過前面的兩兩交換把兩個相鄰起來，這時候也不會交換，所以相同元素的前後順序並沒有改變，所以冒泡排序是一種穩定排序演算法。
3、插入排序
插入排序（Insertion Sort）的演算法描述是一種簡單直觀的排序演算法。它的工作原理是通過構建有序序列，對於未排序數據，在已排序序列中從後向前掃描，找到相應位置並插入。插入排序在實現上，通常採用in-place排序（即只需用到O(1)的額外空間的排序），因而在從後向前掃描過程中，需要反復把已排序元素逐步向後挪位，為最新元素提供插入空間。
演算法描述一般來說，插入排序都採用in-place在數組上實現。具體演算法描述如下：從第一個元素開始，該元素可以認為已經被排序取出下一個元素，在已經排序的元素序列中從後向前掃描如果該元素（已排序）大於新元素，將該元素移到下一位置重復步驟3，直到找到已排序的元素小於或者等於新元素的位置將新元素插入到該位置後重復步驟2~5如果比較操作的代價比交換操作大的話，可以採用二分查找法來減少比較操作的數目。該演算法可以認為是插入排序的一個變種，稱為二分查找排序。
⑸ 常見的排序演算法哪個效率最高
快速排序法。
⑹ java怎麼實現排序
Java實現幾種常見排序方法
日常操作中常見的排序方法有：冒泡排序、快速排序、選擇排序、插入排序、希爾排序，甚至還有基數排序、雞尾酒排序、桶排序、鴿巢排序、歸並排序等。
以下常見演算法的定義
1. 插入排序：插入排序基本操作就是將一個數據插入到已經排好序的有序數據中，從而得到一個新的、個數加一的有序數據，演算法適用於少量數據的排序，時間復雜度為O(n^2)。是穩定的排序方法。插入排序的基本思想是：每步將一個待排序的紀錄，按其關鍵碼值的大小插入前面已經排序的文件中適當位置上，直到全部插入完為止。
2. 選擇排序：選擇排序（Selection sort）是一種簡單直觀的排序演算法。它的工作原理是每一次從待排序的數據元素中選出最小（或最大）的一個元素，存放在序列的起始位置，直到全部待排序的數據元素排完。 選擇排序是不穩定的排序方法。
3. 冒泡排序：冒泡排序（Bubble Sort），是一種計算機科學領域的較簡單的排序演算法。它重復地走訪過要排序的數列，一次比較兩個元素，如果他們的順序錯誤就把他們交換過來。走訪數列的工作是重復地進行直到沒有再需要交換，也就是說該數列已經排序完成。這個演算法的名字由來是因為越大的元素會經由交換慢慢「浮」到數列的頂端。
4. 快速排序：快速排序（Quicksort）是對冒泡排序的一種改進。它的基本思想是：通過一趟排序將要排序的數據分割成獨立的兩部分，其中一部分的所有數據都比另外一部分的所有數據都要小，然後再按此方法對這兩部分數據分別進行快速排序，整個排序過程可以遞歸進行，以此達到整個數據變成有序序列。
5. 歸並排序：歸並排序是建立在歸並操作上的一種有效的排序演算法,該演算法是採用分治法（Divide and Conquer）的一個非常典型的應用。將已有序的子序列合並，得到完全有序的序列；即先使每個子序列有序，再使子序列段間有序。若將兩個有序表合並成一個有序表，稱為二路歸並。
6. 希爾排序：希爾排序(Shell Sort)是插入排序的一種。也稱縮小增量排序，是直接插入排序演算法的一種更高效的改進版本。希爾排序是非穩定排序演算法。希爾排序是把記錄按下標的一定增量分組，對每組使用直接插入排序演算法排序；隨著增量逐漸減少，每組包含的關鍵詞越來越多，當增量減至1時，整個文件恰被分成一組，演算法便終止。
https://www.cnblogs.com/wangmingshun/p/5635292.html