資源描述：
《java各種排序算法》由會員上傳分享，免費在線閱讀，更多相關內(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ù)已有的順序一般來說，當數(shù)據(jù)規(guī)模較小時，應選擇直接插入排序或冒泡排序。任何排序算法在數(shù)據(jù)量小時基本體現(xiàn)不出來差距?？紤]數(shù)據(jù)的類型，比如如果全部是正整數(shù)，那么考慮使用桶排序為最優(yōu)?？紤]數(shù)據(jù)已有順序，快排是一
2、種不穩(wěn)定的排序（當然可以改進），對于大部分排好的數(shù)據(jù)，快排會浪費大量不必要的步驟。數(shù)據(jù)量極小，而起已經(jīng)基本排好序，冒泡是最佳選擇。我們說快排好，是指大量隨機數(shù)據(jù)下，快排效果最理想。而不是所有情況。3）總結(jié)：——按平均的時間性能來分：1）時間復雜度為O(nlogn)的方法有：快速排序、堆排序和歸并排序，其中以快速排序為最好；2）時間復雜度為O(n2)的有：直接插入排序、起泡排序和簡單選擇排序，其中以直接插入為最好，特別是對那些對關鍵字近似有序的記錄序列尤為如此；3）時間復雜度為O(n)的排序方法只有，基數(shù)排序。當待排記錄序列按關鍵字順序有序時，直接插入排序
3、和起泡排序能達到O(n)的時間復雜度;而對于快速排序而言，這是最不好的情況，此時的時間性能蛻化為O(n2)，因此是應該盡量避免的情況。簡單選擇排序、堆排序和歸并排序的時間性能不隨記錄序列中關鍵字的分布而改變。——按平均的空間性能來分（指的是排序過程中所需的輔助空間大?。?）所有的簡單排序方法(包括：直接插入、起泡和簡單選擇)和堆排序的空間復雜度為O(1)；2）快速排序為O(logn)，為棧所需的輔助空間;3）歸并排序所需輔助空間最多，其空間復雜度為O(n);4）鏈式基數(shù)排序需附設隊列首尾指針，則空間復雜度為O(rd)?！判蚍椒ǖ姆€(wěn)定性能：1）穩(wěn)定的
4、排序方法指的是，對于兩個關鍵字相等的記錄，它們在序列中的相對位置，在排序之前和經(jīng)過排序之后，沒有改變。2）當對多關鍵字的記錄序列進行LSD方法排序時，必須采用穩(wěn)定的排序方法。3）對于不穩(wěn)定的排序方法，只要能舉出一個實例說明即可。4）快速排序，希爾排序和堆排序是不穩(wěn)定的排序方法。4）插入排序：包括直接插入排序，希爾插入排序。直接插入排序：將一個記錄插入到已經(jīng)排序好的有序表中。1,sorted數(shù)組的第0個位置沒有放數(shù)據(jù)。2，從sorted第二個數(shù)據(jù)開始處理：如果該數(shù)據(jù)比它前面的數(shù)據(jù)要小，說明該數(shù)據(jù)要往前面移動。首先將該數(shù)據(jù)備份放到sorted的第0位置當哨兵
5、。然后將該數(shù)據(jù)前面那個數(shù)據(jù)后移。然后往前搜索，找插入位置。找到插入位置之后講第0位置的那個數(shù)據(jù)插入對應位置。O(n*n),當待排記錄序列為正序時，時間復雜度提高至O(n)。希爾排序（縮小增量排序diminishingincrementsort）：先將整個待排記錄序列分割成若干個子序列分別進行直接插入排序，待整個序列中的記錄基本有序時，再對全體記錄進行一次直接插入排序。面試穿什么，這里找答案！插入排序Java代碼：publicclassInsertionSort{//插入排序：直接插入排序，希爾排序publicvoidstraightInsertionSo
6、rt(double[]sorted){intsortedLen=sorted.length;for(intj=2;j=0;k--){if(sorted[k]>sorted[0]){sorted[k+1]=sorted[k];}else{insertPos=k+1;break;}}sort
7、ed[insertPos]=sorted[0];}}}publicvoidshellInertionSort(double[]sorted,intinc){intsortedLen=sorted.length;for(intj=inc+1;j=0;k-=inc){if(sorted[k]>sorted[0]){sorted[k+inc]=so
8、rted[k];//數(shù)據(jù)結(jié)構(gòu)課本上這個地方?jīng)]有給出判讀，出錯：if(k-inc<
