以var a = [4,2,6,3,1,9,5,7,8,0];為例子。
創(chuàng)新互聯(lián)建站專注于企業(yè)營銷型網(wǎng)站建設(shè)、網(wǎng)站重做改版、克東網(wǎng)站定制設(shè)計(jì)、自適應(yīng)品牌網(wǎng)站建設(shè)、H5技術(shù)、購物商城網(wǎng)站建設(shè)、集團(tuán)公司官網(wǎng)建設(shè)、外貿(mào)網(wǎng)站制作、高端網(wǎng)站制作、響應(yīng)式網(wǎng)頁設(shè)計(jì)等建站業(yè)務(wù)，價(jià)格優(yōu)惠性價(jià)比高，為克東等各大城市提供網(wǎng)站開發(fā)制作服務(wù)。
1.希爾排序。 希爾排序是在插入排序上面做的升級。是先跟距離較遠(yuǎn)的進(jìn)行比較的一些方法。
function shellsort(arr){ var i,k,j,len=arr.length,gap = Math.ceil(len/2),temp; while(gap0){ for (var k = 0; k gap; k++) { var tagArr = []; tagArr.push(arr[k]) for (i = k+gap; i len; i=i+gap) { temp = arr[i]; tagArr.push(temp); for (j=i-gap; j -1; j=j-gap) { if(arr[j]temp){ arr[j+gap] = arr[j]; }else{ break; } } arr[j+gap] = temp; } console.log(tagArr,"gap:"+gap);//輸出當(dāng)前進(jìn)行插入排序的數(shù)組。 console.log(arr);//輸出此輪排序后的數(shù)組。 } gap = parseInt(gap/2); } return arr; }
過程輸出：
[4, 9] "gap:5" [4, 2, 6, 3, 1, 9, 5, 7, 8, 0] [2, 5] "gap:5" [4, 2, 6, 3, 1, 9, 5, 7, 8, 0] [6, 7] "gap:5" [4, 2, 6, 3, 1, 9, 5, 7, 8, 0] [3, 8] "gap:5" [4, 2, 6, 3, 1, 9, 5, 7, 8, 0] [1, 0] "gap:5" [4, 2, 6, 3, 0, 9, 5, 7, 8, 1] [4, 6, 0, 5, 8] "gap:2" [0, 2, 4, 3, 5, 9, 6, 7, 8, 1] [2, 3, 9, 7, 1] "gap:2" [0, 1, 4, 2, 5, 3, 6, 7, 8, 9] [0, 1, 4, 2, 5, 3, 6, 7, 8, 9] "gap:1" [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
由輸出可以看到。第一輪間隔為5。依次對這些間隔的數(shù)組插入排序。
間隔為5：
[4, 9] "gap:5" [4, 2, 6, 3, 1, 9, 5, 7, 8, 0] [2, 5] "gap:5" [4, 2, 6, 3, 1, 9, 5, 7, 8, 0] [6, 7] "gap:5" [4, 2, 6, 3, 1, 9, 5, 7, 8, 0] [3, 8] "gap:5" [4, 2, 6, 3, 1, 9, 5, 7, 8, 0] [1, 0] "gap:5" [4, 2, 6, 3, 0, 9, 5, 7, 8, 1] [4, 6, 0, 5, 8] "gap:2" [0, 2, 4, 3, 5, 9, 6, 7, 8, 1] [2, 3, 9, 7, 1] "gap:2" [0, 1, 4, 2, 5, 3, 6, 7, 8, 9] [0, 1, 4, 2, 5, 3, 6, 7, 8, 9] "gap:1" [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
間隔為2：
[4, 2, 6, 3, 0, 9, 5, 7, 8, 1] 4 6 0 5 8 2 3 9 7 1
排序后：
[0, 1, 4, 2, 5, 3, 6, 7, 8, 9]
間隔為1：
排序后：
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]。
2.快速排序。把一個(gè)數(shù)組以數(shù)組中的某個(gè)值為標(biāo)記。比這個(gè)值小的放到數(shù)組的左邊，比這個(gè)值得大的放到數(shù)組的右邊。然后再遞歸 對左邊和右邊的數(shù)組進(jìn)行同樣的操作。直到排序完成。通常以數(shù)組的第一個(gè)值為標(biāo)記。
代碼:
function quickSort(arr){ var len = arr.length,leftArr=[],rightArr=[],tag; if(len2){ return arr; } tag = arr[0]; for(i=1;ilen;i++){ if(arr[i]=tag){ leftArr.push(arr[i]) }else{ rightArr.push(arr[i]); } } return quickSort(leftArr).concat(tag,quickSort(rightArr)); }
3.歸并排序。把一系列排好序的子序列合并成一個(gè)大的完整有序序列。從最小的單位開始合并。然后再逐步合并合并好的有序數(shù)組。最終實(shí)現(xiàn)歸并排序。
合并兩個(gè)有序數(shù)組的方法：
function subSort(arr1,arr2){ var len1 = arr1.length,len2 = arr2.length,i=0,j=0,arr3=[],bArr1 = arr1.slice(),bArr2 = arr2.slice(); while(bArr1.length!=0 || bArr2.length!=0){ if(bArr1.length == 0){ arr3 = arr3.concat(bArr2); bArr2.length = 0; }else if(bArr2.length == 0){ arr3 = arr3.concat(bArr1); bArr1.length = 0; }else{ if(bArr1[0]=bArr2[0]){ arr3.push(bArr1[0]); bArr1.shift(); }else{ arr3.push(bArr2[0]); bArr2.shift(); } } } return arr3; }
歸并排序：
function mergeSort(arr){ var len= arr.length,arrleft=[],arrright =[],gap=1,maxgap=len-1,gapArr=[],glen,n; while(gapmaxgap){ gap = Math.pow(2,n); if(gap=maxgap){ gapArr.push(gap); } n++; } glen = gapArr.length; for (var i = 0; i glen; i++) { gap = gapArr[i]; for (var j = 0; j len; j=j+gap*2) { arrleft = arr.slice(j, j+gap); arrright = arr.slice(j+gap,j+gap*2); console.log("left:"+arrleft,"right:"+arrright); arr = arr.slice(0,j).concat(subSort(arrleft,arrright),arr.slice(j+gap*2)); } } return arr; }
排序[4,2,6,3,1,9,5,7,8,0]輸出：
left:4 right:2 left:6 right:3 left:1 right:9 left:5 right:7 left:8 right:0 left:2,4 right:3,6 left:1,9 right:5,7 left:0,8 right: left:2,3,4,6 right:1,5,7,9 left:0,8 right: left:1,2,3,4,5,6,7,9 right:0,8
看出來從最小的單位入手。
第一輪先依次合并相鄰元素：4,2; 6,3; 1,9; 5,7; 8,0
合并完成之后變成： [2,4,3,6,1,9,5,7,0,8]
第二輪以2個(gè)元素為一個(gè)單位進(jìn)行合并：[2,4],[3,6]; [1,9],[5,7]; [0,8],[];
合并完成之后變成：[2,3,4,6,1,5,7,9,0,8]
第三輪以4個(gè)元素為一個(gè)單位進(jìn)行合并：[2,3,4,6],[1,5,7,9]; [0,8],[]
合并完成之后變成： [1,2,3,4,5,6,7,9,0,8];
第四輪以8個(gè)元素為一個(gè)單位進(jìn)行合并： [1,2,3,4,5,6,7,9],[0,8];
合并完成。 [0,1,2,3,4,5,6,7,8,9];
package temp;
import sun.misc.Sort;
/**
* @author zengjl
* @version 1.0
* @since 2007-08-22
* @Des java幾種基本排序方法
*/
/**
* SortUtil:排序方法
* 關(guān)于對排序方法的選擇：這告訴我們，什么時(shí)候用什么排序最好。當(dāng)人們渴望先知道排在前面的是誰時(shí)，
* 我們用選擇排序；當(dāng)我們不斷拿到新的數(shù)并想保持已有的數(shù)始終有序時(shí)，我們用插入排序；當(dāng)給出的數(shù)
* 列已經(jīng)比較有序，只需要小幅度的調(diào)整一下時(shí)，我們用冒泡排序。
*/
public class SortUtil extends Sort {
/**
* 插入排序法
* @param data
* @Des 插入排序(Insertion Sort)是，每次從數(shù)列中取一個(gè)還沒有取出過的數(shù)，并按照大小關(guān)系插入到已經(jīng)取出的數(shù)中使得已經(jīng)取出的數(shù)仍然有序。
*/
public int[] insertSort(int[] data) {
1/11頁
int temp;
for (int i = 1; i data.length; i++) {
for (int j = i; (j 0) (data[j] data[j - 1]); j--) {
swap(data, j, j - 1);
}
}
return data;
}
/**
* 冒泡排序法
* @param data
* @return
* @Des 冒泡排序(Bubble Sort)分為若干趟進(jìn)行，每一趟排序從前往后比較每兩個(gè)相鄰的元素的大?。ㄒ虼艘惶伺判蛞容^n-1對位置相鄰的數(shù)）并在
* 每次發(fā)現(xiàn)前面的那個(gè)數(shù)比緊接它后的數(shù)大時(shí)交換位置；進(jìn)行足夠多趟直到某一趟跑完后發(fā)現(xiàn)這一趟沒有進(jìn)行任何交換操作（最壞情況下要跑n-1趟，
* 這種情況在最小的數(shù)位于給定數(shù)列的最后面時(shí)發(fā)生）。事實(shí)上，在第一趟冒泡結(jié)束后，最后面那個(gè)數(shù)肯定是最大的了，于是第二次只需要對前面n-1
* 個(gè)數(shù)排序，這又將把這n-1個(gè)數(shù)中最小的數(shù)放到整個(gè)數(shù)列的倒數(shù)第二個(gè)位置。這樣下去，冒泡排序第i趟結(jié)束后后面i個(gè)數(shù)都已經(jīng)到位了，第i+1趟實(shí)
* 際上只考慮前n-i個(gè)數(shù)（需要的比較次數(shù)比前面所說的n-1要小）。這相當(dāng)于用數(shù)學(xué)歸納法證明了冒泡排序的正確性
java常見的排序分為：
1 插入類排序
主要就是對于一個(gè)已經(jīng)有序的序列中，插入一個(gè)新的記錄。它包括：直接插入排序，折半插入排序和希爾排序
2 交換類排序
這類排序的核心就是每次比較都要“交換”，在每一趟排序都會(huì)兩兩發(fā)生一系列的“交換”排序，但是每一趟排序都會(huì)讓一個(gè)記錄排序到它的最終位置上。它包括：起泡排序，快速排序
3 選擇類排序
每一趟排序都從一系列數(shù)據(jù)中選擇一個(gè)最大或最小的記錄，將它放置到第一個(gè)或最后一個(gè)為位置交換，只有在選擇后才交換，比起交換類排序，減少了交換記錄的時(shí)間。屬于它的排序：簡單選擇排序，堆排序
4 歸并類排序
將兩個(gè)或兩個(gè)以上的有序序列合并成一個(gè)新的序列
5 基數(shù)排序
主要基于多個(gè)關(guān)鍵字排序的。
下面針對上面所述的算法，講解一些常用的java代碼寫的算法
二 插入類排序之直接插入排序
直接插入排序,一般對于已經(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;
// 每次比較都是對于已經(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ù)與初始序列無關(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];
// 在待插入排序的序號之前進(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.對每組中全部元素進(jìn)行直接插入排序，然后再用一個(gè)較小的增量（d/2）對它進(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++) {
// 每一趟從開始進(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] + " ");
}
}
package?p1;
import?java.util.Arrays;
public?class?Guy
{
/**
?*?歸并排序
?*/
private?static?void?mergeSort?(?int[]?array,?int?start,?int?end,?int[]?tempArray?)
{
if?(end?=?start)
{
return;
}
int?middle?=?(?start?+?end?)?/?2;
mergeSort?(array,?start,?middle,?tempArray);
mergeSort?(array,?middle?+?1,?end,?tempArray);
int?k?=?0,?leftIndex?=?0,?rightIndex?=?end?-?start;
System.arraycopy?(array,?start,?tempArray,?0,?middle?-?start?+?1);
for?(?int?i?=?0;?i??end?-?middle;?i++?)
{
tempArray[end?-?start?-?i]?=?array[middle?+?i?+?1];
}
while?(k??end?-?start?+?1)
{
if?(tempArray[rightIndex]??tempArray[leftIndex])?//?從小到大
{
array[k?+?start]?=?tempArray[leftIndex++];
}
else
{
array[k?+?start]?=?tempArray[rightIndex--];
}
k++;
}
}
public?static?void?main?(?String[]?args?)
{
int[]?array?=?new?int[]?{?11,?213,?134,?65,?77,?78,?23,?43?};
mergeSort?(array,?0,?array.length?-?1,?new?int[array.length]);
System.out.println?(Arrays.toString?(array));
}
}
debug一下，可以監(jiān)視里面每個(gè)變量的值，
不過用斷言會(huì)更專業(yè)一些，
我對算法還不是很在行
邏輯問題還得你慢慢調(diào)試
重慶分公司
重慶分公司
