排序演算法復雜度java

① 常見的排序演算法哪個效率最高

快速排序法。

② java 合並排序 求程序

網路文庫找了一個http://wenku..com/view/332fd62d453610661ed9f414.html
四、合並排序 1、基本思想
合並排序的基本操作是：首先將待排序序列劃分為兩個長度相等的子序列；然後分別對兩個子序列進行歸並排序，得到兩個有序的子序列；最後將兩個有序的子序列合並成一個有序數列。
MergeSort(A[2*n]) {
divide A[2*n] into A[1,……,n],A[n-1,……,2*n];//劃分 MergeSort(A[1,……,n]);//歸並排序前半個子序列
MergeSort(A[[n-1,……,2*n]);//歸並排序後半個子序列 Merge;//合並 }
2、演算法復雜度分析
合並步的時間復雜度為O(n)。合並排序演算法的時間復雜度為O(nlog2n)。
3、編程實現
public int[] MergeSort(int[] A, int[] tempA, int s, int t){
//如果序列中有一個以上的元素，即s<t則進行排序
if(s < t){
int center = (s + t) / 2;
MergeSort(A, tempA, s, center)
;//歸並排序前半個子序列
MergeSort(A, tempA, center + 1, t);
//歸並排序後半個子序列
Merge(A,tempA, s, center, t);
//合並
}
return tempA;
}

public int[] Merge(int[] A, int[] tempA, int s, int m, int t){ int n = t- s + 1;
//n為數據總個數
int i=s;j=m+1;k=s
while(i <= m&& j <= t){
//取A[i]和A[j]中較小者放入tempA[k]
if(A[i]<=A[j]){
tempA[k++] = A[i++]; }
else{
tempA[k++] = A[j++]; } }
if(i<=m) while(i<=m)
tempA[k++]=A[i++];//處理前一個子序列
else while(j<=t)
tempA[k++]=A[j++];//處理後一個子序列
return tempA;
}

③ 哪位幫我講講java中的快速排序法

快速排序是對冒泡排序的一種改進。它的基本思想是：通過一躺排序將要排序的數據分割成獨立的兩部分，其中一部分的所有數據都比另外一部分的所有數據都要小，然後再按次方法對這兩部分數據分別進行快速排序，整個排序過程可以遞歸進行，以此達到整個數據變成有序序列。最壞情況的時間復雜度為O(n2)，最好情況時間復雜度為O(nlog2n)。

另外 java沒指針概念 可以認為是句柄
假設要排序的數組是A[1]……A[N]，首先任意選取一個數據（通常選用第一個數據）作為關鍵數據，然後將所有比它的數都放到它前面，所有比它大的數都放到它後面，這個過程稱為一躺快速排序。一趟快速排序的演算法是：

1）、設置兩個變數I、J，排序開始的時候I：=1，J：=N；

2）以第一個數組元素作為關鍵數據，賦值給X，即X：=A[1]；

3）、從J開始向前搜索，即由後開始向前搜索（J：=J-1），找到第一個小於X的值，兩者交換；

4）、從I開始向後搜索，即由前開始向後搜索（I：=I+1），找到第一個大於X的值，兩者交換；

5）、重復第3、4步，直到I=J；

例如：待排序的數組A的值分別是：（初始關鍵數據X：=49）

A[1] A[2] A[3] A[4] A[5] A[6] A[7]：

49 38 65 97 76 13 27

進行第一次交換後： 27 38 65 97 76 13 49

( 按照演算法的第三步從後面開始找)

進行第二次交換後： 27 38 49 97 76 13 65

( 按照演算法的第四步從前面開始找>X的值，65>49,兩者交換，此時I：=3 )

進行第三次交換後： 27 38 13 97 76 49 65

( 按照演算法的第五步將又一次執行演算法的第三步從後開始找)

進行第四次交換後： 27 38 13 49 76 97 65

( 按照演算法的第四步從前面開始找大於X的值，97>49,兩者交換，此時J：=4 )

此時再執行第三步的時候就發現I=J，從而結束一躺快速排序，那麼經過一躺快速排序之後的結果是：27 38 13 49 76 97 65，即所以大於49的數全部在49的後面，所以小於49的數全部在49的前面。

快速排序就是遞歸調用此過程——在以49為中點分割這個數據序列，分別對前面一部分和後面一部分進行類似的快速排序，從而完成全部數據序列的快速排序，最後把此數據序列變成一個有序的序列，根據這種思想對於上述數組A的快速排序的全過程如圖6所示：

初始狀態 {49 38 65 97 76 13 27}

進行一次快速排序之後劃分為 {27 38 13} 49 {76 97 65}

分別對前後兩部分進行快速排序 {13} 27 {38}

結束 結束 {49 65} 76 {97}

49 {65} 結束

結束

④ Java數組排序 幾種排序方法詳細一點

JAVA中在運用數組進行排序功能時，一般有四種方法：快速排序法、冒泡法、選擇排序法、插入排序法。

快速排序法主要是運用了Arrays中的一個方法Arrays.sort（）實現。

冒泡法是運用遍歷數組進行比較，通過不斷的比較將最小值或者最大值一個一個的遍歷出來。

選擇排序法是將數組的第一個數據作為最大或者最小的值，然後通過比較循環，輸出有序的數組。

插入排序是選擇一個數組中的數據，通過不斷的插入比較最後進行排序。下面我就將他們的實現方法一一詳解供大家參考。

<1>利用Arrays帶有的排序方法快速排序

publicclassTest2{
publicstaticvoidmain(String[]args){
int[]a={5,4,2,4,9,1};
Arrays.sort(a);//進行排序
for(inti:a){
System.out.print(i);
}
}
}

<2>冒泡排序演算法

publicstaticint[]bubbleSort(int[]args){//冒泡排序演算法
for(inti=0;i<args.length-1;i++){
for(intj=i+1;j<args.length;j++){
if(args[i]>args[j]){
inttemp=args[i];
args[i]=args[j];
args[j]=temp;
}
}
}
returnargs;
}

<3>選擇排序演算法

publicstaticint[]selectSort(int[]args){//選擇排序演算法
for(inti=0;i<args.length-1;i++){
intmin=i;
for(intj=i+1;j<args.length;j++){
if(args[min]>args[j]){
min=j;
}
}
if(min!=i){
inttemp=args[i];
args[i]=args[min];
args[min]=temp;
}
}
returnargs;
}

<4>插入排序演算法

publicstaticint[]insertSort(int[]args){//插入排序演算法
for(inti=1;i<args.length;i++){
for(intj=i;j>0;j--){
if(args[j]<args[j-1]){
inttemp=args[j-1];
args[j-1]=args[j];
args[j]=temp;
}elsebreak;
}
}
returnargs;
}

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

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

1、冒泡排序

特點：效率低，實現簡單

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

⑥ java排序演算法有多少種

演算法和語言無關吧，語言只是把具體的演算法實現出來而已。據我了解的排序演算法11-13種。排序演算法嘛 主要就是個思想而已。不同的演算法時間復雜度不一樣，空間復雜度也不一樣，當然執行的效率也不一樣。當然採用哪種演算法還取決於你要實現什麼樣的功能。就好比說：要同時盡快的找出最大最小，或者盡快的找出最值的位置等等。冒泡排序（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) 最壞情況; 對於大的、亂數串列一般相信是最快的已知排序
等。

⑦ 用java冒泡排序和遞歸演算法

冒泡排序

（1）基本思想：在要排序的一組數中，對當前還未排好序的范圍內的全部數，自上而下對相鄰的兩個數依次進行比較和調整，讓較大的數往下沉，較小的往上冒。即：每當兩相鄰的數比較後發現它們的排序與排序要求相反時，就將它們互換。

（2）用java實現

ublicclassbubbleSort{

publicbubbleSort(){

inta[]={1,54,6,3,78,34,12,45};

inttemp=0;

for(inti=0;i<a.length;i++){

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

if(a[i]>a[j]){

temp=a[i];

a[i]=a[j];

a[j]=temp;

}

}

}

for(inti=0;i<a.length;i++)

System.out.println(a[i]);

}

}

遞歸

遞歸演算法，就是程序的自身調用。表現在一段程序中往往會遇到調用自身的那樣一種coding策略，可以利用大道至簡的思想，把一個大的復雜的問題層層轉換為一個小的和原問題相似的問題來求解的這樣一種策略。能看到我們會用很少的語句解決了非常大的問題，所以遞歸策略的最主要體現就是小的代碼量解決了非常復雜的問題。

java代碼：

packagecom.cjq.filedown;

publicclassFab{

publicstaticvoidmain(Stringargs[]){
System.out.println(fab(5));
}

privatestaticintfab(intindex){
if(index==1||index==2){
return1;
}else{
returnfab(index-1)+fab(index-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中有哪幾種常用的排序方法

1、冒泡排序
冒泡排序是一個比較簡單的排序方法。在待排序的數列基本有序的情況下排序速度較快。若要排序的數有n個，則需要n-1輪排序，第j輪排序中，從第一個數開始，相鄰兩數比較，若不符合所要求的順序，則交換兩者的位置；直到第n+1-j個數為止，第一個數與第二個數比較，第二個數與第三個數比較，......，第n-j個與第n+1-j個比較，共比較n-1次。此時第n+1-j個位置上的數已經按要求排好，所以不參加以後的比較和交換操作。例如：第一輪排序：第一個數與第二個數進行比較，若不符合要求的順序，則交換兩者的位置，否則繼續進行二個數與第三個數比較......。直到完成第n-1個數與第n個數的比較。此時第n個位置上的數已經按要求排好，它不參與以後的比較和交換操作；第二輪排序：第一個數與第二個數進行比較，......直到完成第n-2個數與第n-1個數的比較；......第n-1輪排序：第一個數與第二個數進行比較，若符合所要求的順序，則結束冒泡法排序；若不符合要求的順序，則交換兩者的位置，然後結束冒泡法排序。
共n-1輪排序處理，第j輪進行n-j次比較和至多n-j次交換。
從以上排序過程可以看出，較大的數像氣泡一樣向上冒，而較小的數往下沉，故稱冒泡法。

2、選擇排序
選擇法的原理是先將第一個數與後面的每一個數依次比較,不斷將將小的賦給第一個數,從而找出最小的,然後第二個數與後面的每一個數依次比較,從而找出第二小的,然後第三個數與後面的

3、插入排序
插入排序的原理是對數組中的第i個元素，認為它前面的i-1個已經排序好，然後將它插入到前面的i-1個元素中。插入排序對少量元素的排序較為有效.

4、快速排序
快速排序是對冒泡排序的一種改進。它的基本思想是：通過一次排序將要排序的數據分割成獨立的兩部分，其中一部分的所有數據都比另外一部分的所有數據都要小，然後再按次方法對這兩部分數據分別進行快速排序，整個排序過程可以遞歸進行，以此大道整個數據變成有序序列。