java各種排序算法

《java各種排序算法》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。

1、Java各種排序算法及代碼1）分類：1）插入排序（直接插入排序、希爾排序）2）交換排序（冒泡排序、快速排序）3）選擇排序（直接選擇排序、堆排序）4）歸并排序5）分配排序（箱排序、基數(shù)排序）所需輔助空間最多：歸并排序所需輔助空間最少：堆排序平均速度最快：快速排序不穩(wěn)定：快速排序，希爾排序，堆排序。1）選擇排序算法的時候1.數(shù)據(jù)的規(guī)模；2.數(shù)據(jù)的類型；3.數(shù)據(jù)已有的順序一般來說，當(dāng)數(shù)據(jù)規(guī)模較小時，應(yīng)選擇直接插入排序或冒泡排序。任何排序算法在數(shù)據(jù)量小時基本體現(xiàn)不出來差距?？紤]數(shù)據(jù)的類型，比如如果全部是正整數(shù)，那么考慮

2、使用桶排序為最優(yōu)?？紤]數(shù)據(jù)已有順序，快排是一種不穩(wěn)定的排序（當(dāng)然可以改進），對于大部分排好的數(shù)據(jù)，快排會浪費大量不必要的步驟。數(shù)據(jù)量極小，而起已經(jīng)基本排好序，冒泡是最佳選擇。我們說快排好，是指大量隨機數(shù)據(jù)下，快排效果最理想。而不是所有情況。3）總結(jié)：——按平均的時間性能來分：1）時間復(fù)雜度為O(nlogn)的方法有：快速排序、堆排序和歸并排序，其中以快速排序為最好；2）時間復(fù)雜度為O(n2)的有：直接插入排序、起泡排序和簡單選擇排序，其中以直接插入為最好，特別是對那些對關(guān)鍵字近似有序的記錄序列尤為如此；3）時間

3、復(fù)雜度為O(n)的排序方法只有，基數(shù)排序。當(dāng)待排記錄序列按關(guān)鍵字順序有序時，直接插入排序和起泡排序能達到O(n)的時間復(fù)雜度;而對于快速排序而言，這是最不好的情況，此時的時間性能蛻化為O(n2)，因此是應(yīng)該盡量避免的情況。簡單選擇排序、堆排序和歸并排序的時間性能不隨記錄序列中關(guān)鍵字的分布而改變?！雌骄目臻g性能來分（指的是排序過程中所需的輔助空間大?。?）所有的簡單排序方法(包括：直接插入、起泡和簡單選擇)和堆排序的空間復(fù)雜度為O(1)；2）快速排序為O(logn)，為棧所需的輔助空間;3）歸并排序所需輔

4、助空間最多，其空間復(fù)雜度為O(n);4）鏈?zhǔn)交鶖?shù)排序需附設(shè)隊列首尾指針，則空間復(fù)雜度為O(rd)?！判蚍椒ǖ姆€(wěn)定性能：1）穩(wěn)定的排序方法指的是，對于兩個關(guān)鍵字相等的記錄，它們在序列中的相對位置，在排序之前和經(jīng)過排序之后，沒有改變。2）當(dāng)對多關(guān)鍵字的記錄序列進行LSD方法排序時，必須采用穩(wěn)定的排序方法。3）對于不穩(wěn)定的排序方法，只要能舉出一個實例說明即可。4）快速排序，希爾排序和堆排序是不穩(wěn)定的排序方法。4）插入排序：包括直接插入排序，希爾插入排序。直接插入排序：將一個記錄插入到已經(jīng)排序好的有序表中。1,so

5、rted數(shù)組的第0個位置沒有放數(shù)據(jù)。2，從sorted第二個數(shù)據(jù)開始處理：如果該數(shù)據(jù)比它前面的數(shù)據(jù)要小，說明該數(shù)據(jù)要往前面移動。首先將該數(shù)據(jù)備份放到sorted的第0位置當(dāng)哨兵。然后將該數(shù)據(jù)前面那個數(shù)據(jù)后移。然后往前搜索，找插入位置。找到插入位置之后講第0位置的那個數(shù)據(jù)插入對應(yīng)位置。O(n*n),當(dāng)待排記錄序列為正序時，時間復(fù)雜度提高至O(n)。希爾排序（縮小增量排序diminishingincrementsort）：先將整個待排記錄序列分割成若干個子序列分別進行直接插入排序，待整個序列中的記錄基本有序時，再對

6、全體記錄進行一次直接插入排序。面試穿什么，這里找答案！插入排序Java代碼：publicclassInsertionSort{//插入排序：直接插入排序，希爾排序publicvoidstraightInsertionSort(double[]sorted){intsortedLen=sorted.length;for(intj=2;j

7、[j-1];//前面的那個后移。intinsertPos=0;for(intk=j-2;k>=0;k--){if(sorted[k]>sorted[0]){sorted[k+1]=sorted[k];}else{insertPos=k+1;break;}}sorted[insertPos]=sorted[0];}}}publicvoidshellInertionSort(double[]sorted,intinc){intsortedLen=sorted.length;for(intj=inc+1;j

8、edLen;j++){if(sorted[j]=0;k-=inc){if(sorted[k]>sorted[0]){sorted[k+inc]=sorted[k];//數(shù)據(jù)結(jié)構(gòu)課本上這個地方?jīng)]有給出判讀，出錯：if(k-inc<