睡眠排序java

⑴ java幾種簡單的排序源代碼

給你介紹4種排序方法及源碼，供參考

1.冒泡排序

主要思路： 從前往後依次交換兩個相鄰的元素，大的交換到後面，這樣每次大的數據就到後面，每一次遍歷，最大的數據到達最後面，時間復雜度是O(n^2)。

• publicstaticvoidbubbleSort(int[]arr){

• for(inti=0;i<arr.length-1;i++){

• for(intj=0;j<arr.length-1;j++){

• if(arr[j]>arr[j+1]){

• arr[j]=arr[j]^arr[j+1];

• arr[j+1]=arr[j]^arr[j+1];

• arr[j]=arr[j]^arr[j+1];

• }

• }

• }

• }

2.選擇排序

主要思路：每次遍歷序列，從中選取最小的元素放到最前面，n次選擇後，前面就都是最小元素的排列了，時間復雜度是O(n^2）。

• publicstaticvoidselectSort(int[]arr){

• for(inti=0;i<arr.length-1;i++){

• for(intj=i+1;j<arr.length;j++){

• if(arr[j]<arr[i]){

• arr[j]=arr[j]^arr[i];

• arr[i]=arr[j]^arr[i];

• arr[j]=arr[j]^arr[i];

• }

• }

• }

• }

3.插入排序

主要思路：使用了兩層嵌套循環，逐個處理待排序的記錄。每個記錄與前面已經排好序的記錄序列進行比較，並將其插入到合適的位置，時間復雜度是O(n^2）。

• publicstaticvoidinsertionSort(int[]arr){

• intj;

• for(intp=1;p<arr.length;p++){

• inttemp=arr[p];//保存要插入的數據

• //將無序中的數和前面有序的數據相比，將比它大的數，向後移動

• for(j=p;j>0&&temp<arr[j-1];j--){

• arr[j]=arr[j-1];

• }

• //正確的位置設置成保存的數據

• arr[j]=temp;

• }

• }

4.希爾排序

主要思路：用步長分組，每個分組進行插入排序，再慢慢減小步長，當步長為1的時候完成一次插入排序， 希爾排序的時間復雜度是：O（nlogn）～O（n2），平均時間復雜度大致是O(n^1.5)

• publicstaticvoidshellSort(int[]arr){

• intj;

• for(intgap=arr.length/2;gap>0;gap/=2){

• for(inti=gap;i<arr.length;i++){

• inttemp=arr[i];

• for(j=i;j>=gap&&temp<arr[j-gap];j-=gap){

• arr[j]=arr[j-gap];

• }

• arr[j]=temp;

• }

• }

• }

⑵ 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中排序方法有哪些

1、直接插入排序：最基本的插入排序，將第i個插入到前i-1個中的適當位置。
2、折半插入排序：因為是已經確定了前部分是有序序列，所以在查找插入位置的時候可以用折半查找的方法進行查找，提高效率。
3、 希爾排序： 又稱縮小增量排序法。把待排序序列分成若干較小的子序列，然後逐個使用直接插入排序法排序，最後再對一個較為有序的序列進行一次排序，主要是為了減少移動的次數，提高效率。原理應該就是從無序到漸漸有序，要比直接從無序到有序移動的次數會少一些。
4、 冒泡排序：反復掃描待排序序列，在掃描的過程中順次比較相鄰的兩個元素的大小，若逆序就交換位置。第一趟，從第一個數據開始，比較相鄰的兩個數據，（以升序為例）如果大就交換，得到一個最大數據在末尾；然後進行第二趟，只掃描前n-1個元素，得到次大的放在倒數第二位。以此類推，最後得到升序序列。如果在掃描過程中，發現沒有交換，說明已經排好序列，直接終止掃描。所以最多進行n-1趟掃描。
5、快速排序： 思想：冒泡排序一次只能消除一個逆序，為了能一次消除多個逆序，採用快速排序。以一個關鍵字為軸，從左從右依次與其進行對比，然後交換，第一趟結束後，可以把序列分為兩個子序列，然後再分段進行快速排序，達到高效。
此外還有選擇、歸並、分配排序等等及它們的子類排序

⑷ java實現幾種常見排序演算法

下面給你介紹四種常用排序演算法：

1、冒泡排序

特點：效率低，實現簡單

思想（從小到大排）：每一趟將待排序序列中最大元素移到最後，剩下的為新的待排序序列，重復上述步驟直到排完所有元素。這只是冒泡排序的一種，當然也可以從後往前排。

⑸ Java排序一共有幾種

排序演算法

所謂排序，就是使一串記錄，按照其中的某個或某些關鍵字的大小，遞增或遞減的排列起來的操作。

分類

在計算機科學所使用的排序演算法通常被分類為：

計算的復雜度（最差、平均、和最好表現），依據串列（list）的大小（n）。一般而言，好的表現是O。(n log n)，且壞的行為是Ω(n2)。對於一個排序理想的表現是O(n)。僅使用一個抽象關鍵比較運算的排序演算法總平均上總是至少需要Ω(n log n)。

記憶體使用量（以及其他電腦資源的使用）

穩定度：穩定排序演算法會依照相等的關鍵（換言之就是值）維持紀錄的相對次序。也就是一個排序演算法是穩定的，就是當有兩個有相等關鍵的紀錄R和S，且在原本的串列中R出現在S之前，在排序過的串列中R也將會是在S之前。

一般的方法：插入、交換、選擇、合並等等。交換排序包含冒泡排序（bubble sort）和快速排序（quicksort）。選擇排序包含shaker排序和堆排序（heapsort）。

當相等的元素是無法分辨的，比如像是整數，穩定度並不是一個問題。然而，假設以下的數對將要以他們的第一個數字來排序。

(4, 1) (3, 1) (3, 7) (5, 6)

在這個狀況下，有可能產生兩種不同的結果，一個是依照相等的鍵值維持相對的次序，而另外一個則沒有：

(3, 1) (3, 7) (4, 1) (5, 6) (維持次序)

(3, 7) (3, 1) (4, 1) (5, 6) (次序被改變)

不穩定排序演算法可能會在相等的鍵值中改變紀錄的相對次序，但是穩定排序演算法從來不會如此。不穩定排序演算法可以被特別地時作為穩定。作這件事情的一個方式是人工擴充鍵值的比較，如此在其他方面相同鍵值的兩個物件間之比較，就會被決定使用在原先資料次序中的條目，當作一個同分決賽。然而，要記住這種次序通常牽涉到額外的空間負擔。

排列演算法列表

在這個表格中，n是要被排序的紀錄數量以及k是不同鍵值的數量。

穩定的

冒泡排序（bubble sort） — O(n2)

雞尾酒排序 (Cocktail sort, 雙向的冒泡排序) — O(n2)

插入排序 （insertion sort）— O(n2)

桶排序 （bucket sort）— O(n); 需要 O(k) 額外 記憶體

計數排序 (counting sort) — O(n+k); 需要 O(n+k) 額外 記憶體

歸並排序 （merge sort）— O(n log n); 需要 O(n) 額外記憶體

原地歸並排序 — O(n2)

二叉樹排序 （Binary tree sort） — O(n log n); 需要 O(n) 額外記憶體

鴿巢排序 (Pigeonhole sort) — O(n+k); 需要 O(k) 額外記憶體

基數排序 （radix sort）— O(n·k); 需要 O(n) 額外記憶體

Gnome sort — O(n2)

Library sort — O(n log n) with high probability, 需要 (1+ε)n 額外記憶體

不穩定

選擇排序 （selection sort）— O(n2)

希爾排序 （shell sort）— O(n log n) 如果使用最佳的現在版本

Comb sort — O(n log n)

堆排序 （heapsort）— O(n log n)

Smoothsort — O(n log n)

快速排序 （quicksort）— O(n log n) 期望時間, O(n2) 最壞情況; 對於大的、亂數串列一般相信是最快的已知排序

Introsort — O(n log n)

Patience sorting — O(n log n + k) 最外情況時間, 需要 額外的 O(n + k) 空間, 也需要找到最長的遞增子序列（longest increasing subsequence）

不實用的排序演算法

Bogo排序 — O(n × n!) 期望時間, 無窮的最壞情況。

Stupid sort — O(n3); 遞回版本需要 O(n2) 額外記憶體

Bead sort — O(n) or O(√n), 但需要特別的硬體

Pancake sorting — O(n), 但需要特別的硬體

排序的演算法

排序的演算法有很多，對空間的要求及其時間效率也不盡相同。下面列出了一些常見的排序演算法。這裡面插入排序和冒泡排序又被稱作簡單排序，他們對空間的要求不高，但是時間效率卻不穩定；而後面三種排序相對於簡單排序對空間的要求稍高一點，但時間效率卻能穩定在很高的水平。基數排序是針對關鍵字在一個較小范圍內的排序演算法。

插入排序

冒泡排序

選擇排序

快速排序

堆排序

歸並排序

基數排序

希爾排序

插入排序

插入排序是這樣實現的：

首先新建一個空列表，用於保存已排序的有序數列（我們稱之為"有序列表"）。

從原數列中取出一個數，將其插入"有序列表"中，使其仍舊保持有序狀態。

重復2號步驟，直至原數列為空。

插入排序的平均時間復雜度為平方級的，效率不高，但是容易實現。它藉助了"逐步擴大成果"的思想，使有序列表的長度逐漸增加，直至其長度等於原列表的長度。

冒泡排序

冒泡排序是這樣實現的：

首先將所有待排序的數字放入工作列表中。

從列表的第一個數字到倒數第二個數字，逐個檢查：若某一位上的數字大於他的下一位，則將它與它的下一位交換。

重復2號步驟，直至再也不能交換。

冒泡排序的平均時間復雜度與插入排序相同，也是平方級的，但也是非常容易實現的演算法。

選擇排序

選擇排序是這樣實現的：

設數組內存放了n個待排數字，數組下標從1開始，到n結束。

i=1

從數組的第i個元素開始到第n個元素，尋找最小的元素。

將上一步找到的最小元素和第i位元素交換。

如果i=n－1演算法結束，否則回到第3步

選擇排序的平均時間復雜度也是O(n²)的。

快速排序

現在開始，我們要接觸高效排序演算法了。實踐證明，快速排序是所有排序演算法中最高效的一種。它採用了分治的思想：先保證列表的前半部分都小於後半部分，然後分別對前半部分和後半部分排序，這樣整個列表就有序了。這是一種先進的思想，也是它高效的原因。因為在排序演算法中，演算法的高效與否與列表中數字間的比較次數有直接的關系，而"保證列表的前半部分都小於後半部分"就使得前半部分的任何一個數從此以後都不再跟後半部分的數進行比較了，大大減少了數字間不必要的比較。但查找數據得另當別論了。

堆排序

堆排序與前面的演算法都不同，它是這樣的：

首先新建一個空列表，作用與插入排序中的"有序列表"相同。

找到數列中最大的數字，將其加在"有序列表"的末尾，並將其從原數列中刪除。

重復2號步驟，直至原數列為空。

堆排序的平均時間復雜度為nlogn,效率高（因為有堆這種數據結構以及它奇妙的特徵，使得"找到數列中最大的數字"這樣的操作只需要O(1)的時間復雜度，維護需要logn的時間復雜度），但是實現相對復雜（可以說是這里7種演算法中比較難實現的）。

看起來似乎堆排序與插入排序有些相像，但他們其實是本質不同的演算法。至少，他們的時間復雜度差了一個數量級，一個是平方級的，一個是對數級的。

平均時間復雜度

插入排序 O(n2)

冒泡排序 O(n2)

選擇排序 O(n2)

快速排序 O(n log n)

堆排序 O(n log n)

歸並排序 O(n log n)

基數排序 O(n)

希爾排序 O(n1.25)