java常見(jiàn)的排序分為：
專注于為中小企業(yè)提供成都網(wǎng)站建設(shè)、成都做網(wǎng)站服務(wù),電腦端+手機(jī)端+微信端的三站合一,更高效的管理,為中小企業(yè)吉水免費(fèi)做網(wǎng)站提供優(yōu)質(zhì)的服務(wù)。我們立足成都，凝聚了一批互聯(lián)網(wǎng)行業(yè)人才，有力地推動(dòng)了上千家企業(yè)的穩(wěn)健成長(zhǎng)，幫助中小企業(yè)通過(guò)網(wǎng)站建設(shè)實(shí)現(xiàn)規(guī)模擴(kuò)充和轉(zhuǎn)變。
1 插入類排序
主要就是對(duì)于一個(gè)已經(jīng)有序的序列中，插入一個(gè)新的記錄。它包括：直接插入排序，折半插入排序和希爾排序
2 交換類排序
這類排序的核心就是每次比較都要“交換”，在每一趟排序都會(huì)兩兩發(fā)生一系列的“交換”排序，但是每一趟排序都會(huì)讓一個(gè)記錄排序到它的最終位置上。它包括：起泡排序，快速排序
3 選擇類排序
每一趟排序都從一系列數(shù)據(jù)中選擇一個(gè)最大或最小的記錄，將它放置到第一個(gè)或最后一個(gè)為位置交換，只有在選擇后才交換，比起交換類排序，減少了交換記錄的時(shí)間。屬于它的排序：簡(jiǎn)單選擇排序，堆排序
4 歸并類排序
將兩個(gè)或兩個(gè)以上的有序序列合并成一個(gè)新的序列
5 基數(shù)排序
主要基于多個(gè)關(guān)鍵字排序的。
下面針對(duì)上面所述的算法，講解一些常用的java代碼寫的算法
二 插入類排序之直接插入排序
直接插入排序,一般對(duì)于已經(jīng)有序的隊(duì)列排序效果好。
基本思想：每趟將一個(gè)待排序的關(guān)鍵字按照大小插入到已經(jīng)排序好的位置上。
算法思路，從后往前先找到要插入的位置，如果小于則就交換，將元素向后移動(dòng)，將要插入數(shù)據(jù)插入該位置即可。時(shí)間復(fù)雜度為O(n2),空間復(fù)雜度為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;
// 每次比較都是對(duì)于已經(jīng)有序的
while (j = 0 data[j] temp) {
data[j + 1] = data[j];
j--;
}
data[j + 1] = temp;
}
// 輸出排序好的數(shù)據(jù)
for (int k = 0; k data.length; k++) {
System.out.print(data[k] + " ");
}
}
}
三 插入類排序之折半插入排序(二分法排序)
條件：在一個(gè)已經(jīng)有序的隊(duì)列中，插入一個(gè)新的元素
折半插入排序記錄的比較次數(shù)與初始序列無(wú)關(guān)
思想：折半插入就是首先將隊(duì)列中取最小位置low和最大位置high，然后算出中間位置mid
將中間位置mid與待插入的數(shù)據(jù)data進(jìn)行比較，
如果mid大于data，則就表示插入的數(shù)據(jù)在mid的左邊，high=mid-1;
如果mid小于data，則就表示插入的數(shù)據(jù)在mid的右邊,low=mid+1
最后整體進(jìn)行右移操作。
時(shí)間復(fù)雜度O(n2),空間復(fù)雜度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 };
// 存放臨時(shí)要插入的元素?cái)?shù)據(jù)
int temp;
int low, mid, high;
for (int i = 1; i data.length; i++) {
temp = data[i];
// 在待插入排序的序號(hào)之前進(jìn)行折半插入
low = 0;
high = i - 1;
while (low = high) {
mid = (low + high) / 2;
if (temp data[mid])
high = mid - 1;
else
// low=high的時(shí)候也就是找到了要插入的位置，
// 此時(shí)進(jìn)入循環(huán)中，將low加1，則就是要插入的位置了
low = mid + 1;
}
// 找到了要插入的位置，從該位置一直到插入數(shù)據(jù)的位置之間數(shù)據(jù)向后移動(dòng)
for (int j = i; j = low + 1; j--)
data[j] = data[j - 1];
// low已經(jīng)代表了要插入的位置了
data[low] = temp;
}
for (int k = 0; k data.length; k++) {
System.out.print(data[k] + " ");
}
}
}
四 插入類排序之希爾排序
希爾排序，也叫縮小增量排序，目的就是盡可能的減少交換次數(shù)，每一個(gè)組內(nèi)最后都是有序的。
將待續(xù)按照某一種規(guī)則分為幾個(gè)子序列，不斷縮小規(guī)則，最后用一個(gè)直接插入排序合成
空間復(fù)雜度為O(1)，時(shí)間復(fù)雜度為O(nlog2n)
算法先將要排序的一組數(shù)按某個(gè)增量d（n/2,n為要排序數(shù)的個(gè)數(shù)）分成若干組，每組中記錄的下標(biāo)相差d.對(duì)每組中全部元素進(jìn)行直接插入排序，然后再用一個(gè)較小的增量（d/2）對(duì)它進(jìn)行分組，在每組中再進(jìn)行直接插入排序。當(dāng)增量減到1時(shí)，進(jìn)行直接插入排序后，排序完成。
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)
{
//利用這個(gè)在將組內(nèi)倍數(shù)減小
//這里依次為5,3,2,1
d1 = Math.ceil(d1 / 2);
//d為增量每個(gè)分組之間索引的增量
int d = (int) d1;
//每個(gè)分組內(nèi)部排序
for (int x = 0; x d; x++)
{
//組內(nèi)利用直接插入排序
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]+" ");
}
}
五 交換類排序之冒泡排序
交換類排序核心就是每次比較都要進(jìn)行交換
冒泡排序：是一種交換排序
每一趟比較相鄰的元素，較若大小不同則就會(huì)發(fā)生交換，每一趟排序都能將一個(gè)元素放到它最終的位置！每一趟就進(jìn)行比較。
時(shí)間復(fù)雜度O(n2)，空間復(fù)雜度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;
// 排序的比較趟數(shù),每一趟都會(huì)將剩余最大數(shù)放在最后面
for (int i = 0; i data.length - 1; i++) {
// 每一趟從開(kāi)始進(jìn)行比較，將該元素與其余的元素進(jìn)行比較
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] + " ");
}
}
給你介紹4種排序方法及源碼，供參考
1.冒泡排序
主要思路： 從前往后依次交換兩個(gè)相鄰的元素，大的交換到后面，這樣每次大的數(shù)據(jù)就到后面，每一次遍歷，最大的數(shù)據(jù)到達(dá)最后面，時(shí)間復(fù)雜度是O(n^2)。
public?static?void?bubbleSort(int[]?arr){
for(int?i?=0;?i??arr.length?-?1;?i++){
for(int?j=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次選擇后，前面就都是最小元素的排列了，時(shí)間復(fù)雜度是O(n^2）。
public?static?void?selectSort(int[]?arr){
for(int?i?=?0;?i?arr.length?-1;?i++){
for(int?j?=?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.插入排序
主要思路：使用了兩層嵌套循環(huán)，逐個(gè)處理待排序的記錄。每個(gè)記錄與前面已經(jīng)排好序的記錄序列進(jìn)行比較，并將其插入到合適的位置，時(shí)間復(fù)雜度是O(n^2）。
public?static?void?insertionSort(int[]?arr){
int?j;
for(int?p?=?1;?p??arr.length;?p++){
int?temp?=?arr[p];???//保存要插入的數(shù)據(jù)
//將無(wú)序中的數(shù)和前面有序的數(shù)據(jù)相比，將比它大的數(shù)，向后移動(dòng)
for(j=p;?j0??temp?arr[j-1];?j--){
arr[j]?=?arr[j-1];
}
//正確的位置設(shè)置成保存的數(shù)據(jù)
arr[j]?=?temp;
}
}
4.希爾排序
主要思路：用步長(zhǎng)分組，每個(gè)分組進(jìn)行插入排序，再慢慢減小步長(zhǎng)，當(dāng)步長(zhǎng)為1的時(shí)候完成一次插入排序，? 希爾排序的時(shí)間復(fù)雜度是：O（nlogn）～O（n2），平均時(shí)間復(fù)雜度大致是O(n^1.5)
public?static?void?shellSort(int[]?arr){
int?j?;
for(int?gap?=?arr.length/2;?gap??0?;?gap/=2){
for(int?i?=?gap;?i??arr.length;?i++){
int?temp?=?arr[i];
for(j?=?i;?j=gap??temparr[j-gap];?j-=gap){
arr[j]?=?arr[j-gap];
}
arr[j]?=?temp;
}
}
}
本節(jié)內(nèi)容是排序算法系列之一： 希爾排序 ，主要講解了希爾排序的主體思路，選取了一個(gè)待排序的數(shù)字列表對(duì)希爾排序算法進(jìn)行了演示，給出了希爾排序算法的 Java 代碼實(shí)現(xiàn)，幫助大家可以更好的理解希爾排序算法。
希爾排序（Shell Sort），是計(jì)算機(jī)科學(xué)與技術(shù)領(lǐng)域中較為簡(jiǎn)單的一種排序算法。
希爾排序是插入排序的一種，有時(shí)候也被稱為 “縮小增量排序”。它是插入排序的改進(jìn)版，與插入排序的不同之處在于，希爾排序會(huì)優(yōu)先比較距離較遠(yuǎn)的元素。希爾排序是按照其設(shè)計(jì)者希爾（Donald Shell）的名字命名而來(lái)，并于 1959 年公布出來(lái)。
在介紹完希爾排序之后，我們一起來(lái)看一下希爾排序的實(shí)現(xiàn)步驟具體是什么樣的吧。這里我們假設(shè)待排序的序列為 [9,2,11,7,12,5]，我們按照從小到大的序列進(jìn)行排序。
選擇一個(gè)增量序列 k1，k2, … km，其中 k1k2…km=1，即增量序列大小依次減小，并且最后一個(gè)增量序列大小為 1。
按照增量序列的個(gè)數(shù) m，對(duì)整個(gè)待排序序列進(jìn)行 m 趟排序。
每一趟排序，根據(jù)對(duì)應(yīng)的增量 ki，需要將待排序的序列分成對(duì)應(yīng)長(zhǎng)度的子序列，分別在子序列上面進(jìn)行直接插入排序。當(dāng)且僅當(dāng)增量序列為 1 時(shí)，整個(gè)序列作為一個(gè)整體處理。
其實(shí)，上面的 步驟 1 和 步驟 2 都是在排序之前進(jìn)行的處理，選擇對(duì)應(yīng)的增量。上面的 步驟 3 每執(zhí)行一次，就相當(dāng)于是進(jìn)行了一次插入排序，只是每次都會(huì)選擇一個(gè)增量，將整個(gè)待排序序列按照增量進(jìn)行劃分，然后在對(duì)應(yīng)增量上面進(jìn)行插入排序。接下來(lái)，讓我們用上面的待排序數(shù)字隊(duì)列 [9,2,11,7,12,5] 進(jìn)行整個(gè)算法步驟的排序演示工作。
按照 2.1 節(jié)的排序步驟，我們需要先選擇對(duì)應(yīng)的希爾排序中的增量值，按照一般性的原則，我們可以將增量按照待排序的序列長(zhǎng)度依次整除 2，直到增量為 1 停止，得到對(duì)應(yīng)的增量。如下：
接著，我們調(diào)用 2.1 中的 步驟 2, 步驟 3 ，按照增量值的取法，依次進(jìn)行對(duì)應(yīng)序列的插入排序，首先我們?nèi)≡隽恐禐?3，對(duì)應(yīng)排序示例如下：
在完成增量為 3 的插入排序之后，我們接著進(jìn)行增量為 1 的插入排序，這個(gè)步驟其實(shí)跟我們之前的插入排序步驟完全一致。整個(gè)過(guò)程如下：
從上面的示例可以看出，其實(shí)整個(gè)希爾排序的過(guò)程，就是根據(jù)增量大小依次進(jìn)行插入排序，本質(zhì)上還是針對(duì)插入排序的一種優(yōu)化。
在說(shuō)明希爾排序的整個(gè)過(guò)程之后，接下來(lái)，我們看看如何用 Java 代碼實(shí)現(xiàn)希爾排序算法。
運(yùn)行結(jié)果如下：
代碼中的第 8 行初始化一個(gè)需要排序的數(shù)組，后面按照從小到大的排序規(guī)則，實(shí)現(xiàn)了數(shù)組的排序。第 12 行至 30 行是整個(gè)希爾排序的流程。第 14 行代碼表示希爾排序中的增量每次整除 2 取得，第 17 行至 25 行是一個(gè) for 循環(huán)結(jié)構(gòu)，表明按照增量進(jìn)行插入排序。最后第 32 行代碼輸出排序好的數(shù)組。
本節(jié)主要學(xué)習(xí)了希爾排序算法，通過(guò)本節(jié)課程的學(xué)習(xí)，需要熟悉希爾排序的算法流程，知道希爾排序算法的實(shí)現(xiàn)思路，可以自己用代碼實(shí)現(xiàn)希爾排序算法。至此，我們已經(jīng)學(xué)習(xí)了排序算法中的冒泡排序、插入排序、選擇排序、希爾排序。
重慶分公司
重慶分公司
