大家好，今天來為大家解答shellsort排序這個問題的一些問題點，包括shell sort 第n列排序也一樣很多人還不知道，因此呢，今天就來為大家分析分析，現(xiàn)在讓我們一起來看看吧！如果解決了您的問題，還望您關注下本站哦，謝謝~
C語言多項排序
1、穩(wěn)定排序和非穩(wěn)定排序
簡單地說就是所有相等的數(shù)經(jīng)過某種排序方法后，仍能保持它們在排序之前的相對次序，我們就說這種排序方法是穩(wěn)定的。反之，就是非穩(wěn)定的。
比如：一組數(shù)排序前是a1,a2,a3,a4,a5，其中a2=a4，經(jīng)過某種排序后為a1,a2,a4,a3,a5，則我們說這種排序是穩(wěn)定的，因為a2排序前在a4的前面，排序后它還是在a4的前面。假如變成a1,a4,a2,a3,a5就不是穩(wěn)定的了。
2、內(nèi)排序和外排序
在排序過程中，所有需要排序的數(shù)都在內(nèi)存，并在內(nèi)存中調整它們的存儲順序，稱為內(nèi)排序；
在排序過程中，只有部分數(shù)被調入內(nèi)存，并借助內(nèi)存調整數(shù)在外存中的存放順序排序方法稱為外排序。
3、算法的時間復雜度和空間復雜度
所謂算法的時間復雜度，是指執(zhí)行算法所需要的計算工作量。
一個算法的空間復雜度，一般是指執(zhí)行這個算法所需要的內(nèi)存空間。
二、各類排序算法分析
1、冒泡排序
====================================================
算法思想簡單描述：
在要排序的一組數(shù)中，對當前還未排好序的范圍內(nèi)的全部數(shù)，自上而下對相鄰的兩個數(shù)依次進行比較和調整，讓較大的數(shù)往下沉，較小的往上冒。即：每當兩相鄰的數(shù)比較后發(fā)現(xiàn)它們的排序與排序要求相反時，就將它們互換。
下面是一種改進的冒泡算法，它記錄了每一遍掃描后最后下沉數(shù)的位置k，這樣可以減少外層循環(huán)掃描的次數(shù)。
冒泡排序是穩(wěn)定的。算法時間復雜度O(n2)--[n的平方]
=====================================================
＃include<iostream.h>
voidBubbleSort(int*pData,intCount)
{
intiTemp;
for(inti=1;i<Count;i++)
{
for(intj=Count-1;j>=i;j--)
{
if(pData[j]<pData[j-1])
{
iTemp=pData[j-1];
pData[j-1]=pData[j];
pData[j]=iTemp;
}
}
}
}
voidmain()
{
intdata[]={10,9,8,7,6,5,4};
BubbleSort(data,7);
for(inti=0;i<7;i++)
cout<<data[i]<<"";
cout<<"\n";
}
倒序(最糟情況)
第一輪：10,9,8,7->10,9,7,8->10,7,9,8->7,10,9,8(交換3次)
第二輪：7,10,9,8->7,10,8,9->7,8,10,9(交換2次)
第一輪：7,8,10,9->7,8,9,10(交換1次)
循環(huán)次數(shù)：6次
交換次數(shù)：6次
其他：
第一輪：8,10,7,9->8,10,7,9->8,7,10,9->7,8,10,9(交換2次)
第二輪：7,8,10,9->7,8,10,9->7,8,10,9(交換0次)
第一輪：7,8,10,9->7,8,9,10(交換1次)
循環(huán)次數(shù)：6次
交換次數(shù)：3次
上面我們給出了程序段，現(xiàn)在我們分析它：這里，影響我們算法性能的主要部分是循環(huán)和交換，顯然，次數(shù)越多，性能就越差。從上面的程序我們可以看出循環(huán)的次數(shù)是固定的，為1+2+...+n-1。寫成公式就是1/2*(n-1)*n。現(xiàn)在注意，我們給出O方法的定義：
若存在一常量K和起點n0，使當n>=n0時，有f(n)<=K*g(n),則f(n)=O(g(n))。（呵呵，不要說沒學好數(shù)學呀，對于編程數(shù)學是非常重要的！！！）
現(xiàn)在我們來看1/2*(n-1)*n，當K=1/2，n0=1，g(n)=n*n時，1/2*(n-1)*n<=1/2*n*n=K*g(n)。所以f(n)=O(g(n))=O(n*n)。所以我們程序循環(huán)的復雜度為O(n*n)。再看交換。從程序后面所跟的表可以看到，兩種情況的循環(huán)相同，交換不同。其實交換本身同數(shù)據(jù)源的有序程度有極大的關系，當數(shù)據(jù)處于倒序的情況時，交換次數(shù)同循環(huán)一樣（每次循環(huán)判斷都會交換），復雜度為O(n*n)。當數(shù)據(jù)為正序，將不會有交換。復雜度為O(0)。亂序時處于中間狀態(tài)。正是由于這樣的原因，我們通常都是通過循環(huán)次數(shù)來對比算法。
2、選擇排序
====================================================
算法思想簡單描述：
在要排序的一組數(shù)中，選出最小的一個數(shù)與第一個位置的數(shù)交換；然后在剩下的數(shù)當中再找最小的與第二個位置的數(shù)交換，如此循環(huán)到倒數(shù)第二個數(shù)和最后一個數(shù)比較為止。
選擇排序是不穩(wěn)定的。算法復雜度O(n2)--[n的平方]
====================================================
＃include<iostream.h>
voidSelectSort(int*pData,intCount)
{
intiTemp;
intiPos;
for(inti=0;i<Count-1;i++)
{
iTemp=pData[i];
iPos=i;
for(intj=i+1;j<Count;j++)
{
if(pData[j]<iTemp)
{
iTemp=pData[j];
iPos=j;
}
}
pData[iPos]=pData[i];
pData[i]=iTemp;
}
}
voidmain()
{
intdata[]={10,9,8,7,6,5,4};
SelectSort(data,7);
for(inti=0;i<7;i++)
cout<<data[i]<<"";
cout<<"\n";
}
倒序(最糟情況)
第一輪：10,9,8,7->(iTemp=9)10,9,8,7->(iTemp=8)10,9,8,7->(iTemp=7)7,9,8,10(交換1次)
第二輪：7,9,8,10->7,9,8,10(iTemp=8)->(iTemp=8)7,8,9,10(交換1次)
第一輪：7,8,9,10->(iTemp=9)7,8,9,10(交換0次)
循環(huán)次數(shù)：6次
交換次數(shù)：2次
其他：
第一輪：8,10,7,9->(iTemp=8)8,10,7,9->(iTemp=7)8,10,7,9->(iTemp=7)7,10,8,9(交換1次)
第二輪：7,10,8,9->(iTemp=8)7,10,8,9->(iTemp=8)7,8,10,9(交換1次)
第一輪：7,8,10,9->(iTemp=9)7,8,9,10(交換1次)
循環(huán)次數(shù)：6次
交換次數(shù)：3次
遺憾的是算法需要的循環(huán)次數(shù)依然是1/2*(n-1)*n。所以算法復雜度為O(n*n)。我們來看他的交換。由于每次外層循環(huán)只產(chǎn)生一次交換（只有一個最小值）。所以f(n)<=n所以我們有f(n)=O(n)。所以，在數(shù)據(jù)較亂的時候，可以減少一定的交換次數(shù)。
3、直接插入排序
====================================================
算法思想簡單描述：
在要排序的一組數(shù)中，假設前面(n-1)[n>=2]個數(shù)已經(jīng)是排好順序的，現(xiàn)在要把第n個數(shù)插到前面的有序數(shù)中，使得這n個數(shù)也是排好順序的。如此反復循環(huán)，直到全部排好順序。
直接插入排序是穩(wěn)定的。算法時間復雜度O(n2)--[n的平方]
=====================================================
#include<iostream.h>
voidSelectSort(int*pData,intCount)
{
intiTemp;
intiPos;
for(inti=0;i<Count-1;i++)
{
iTemp=pData[i];
iPos=i;
for(intj=i+1;j<Count;j++)
{
if(pData[j]<iTemp)
{
iTemp=pData[j];
iPos=j;
}
}
pData[iPos]=pData[i];
pData[i]=iTemp;
}
}
voidmain()
{
intdata[]={10,9,8,7,6,5,4};
SelectSort(data,7);
for(inti=0;i<7;i++)
cout<<data[i]<<"";
cout<<"\n";
}
倒序(最糟情況)
第一輪：10,9,8,7->9,10,8,7(交換1次)(循環(huán)1次)
第二輪：9,10,8,7->8,9,10,7(交換1次)(循環(huán)2次)
第一輪：8,9,10,7->7,8,9,10(交換1次)(循環(huán)3次)
循環(huán)次數(shù)：6次
交換次數(shù)：3次
其他：
第一輪：8,10,7,9->8,10,7,9(交換0次)(循環(huán)1次)
第二輪：8,10,7,9->7,8,10,9(交換1次)(循環(huán)2次)
第一輪：7,8,10,9->7,8,9,10(交換1次)(循環(huán)1次)
循環(huán)次數(shù)：4次
交換次數(shù)：2次
上面結尾的行為分析事實上造成了一種假象，讓我們認為這種算法是簡單算法中最好的，其實不是，因為其循環(huán)次數(shù)雖然并不固定，我們?nèi)钥梢允褂肙方法。從上面的結果可以看出，循環(huán)的次數(shù)f(n)<=1/2*n*(n-1)<=1/2*n*n。所以其復雜度仍為O(n*n)（這里說明一下，其實如果不是為了展示這些簡單排序的不同，交換次數(shù)仍然可以這樣推導）。現(xiàn)在看交換，從外觀上看，交換次數(shù)是O(n)（推導類似選擇法），但我們每次要進行與內(nèi)層循環(huán)相同次數(shù)的‘=’操作。正常的一次交換我們需要三次‘=’而這里顯然多了一些，所以我們浪費了時間。
個人認為在簡單排序算法中，選擇法是最好的。
4、希爾排序
====================================================
算法思想簡單描述：
在直接插入排序算法中，每次插入一個數(shù)，使有序序列只增加1個節(jié)點，并且對插入下一個數(shù)沒有提供任何幫助。如果比較相隔較遠距離（稱為增量）的數(shù)，使得數(shù)移動時能跨過多個元素，則進行一次比較就可能消除
多個元素交換。D.L.shell于1959年在以他名字命名的排序算法中實現(xiàn)了這一思想。算法先將要排序的一組數(shù)按某個增量d分成若干組，每組中記錄的下標相差d.對每組中全部元素進行排序，然后再用一個較小的增量對它進行，在每組中再進行排序。當增量減到1時，整個要排序的數(shù)被分成
一組，排序完成。
下面的函數(shù)是一個希爾排序算法的一個實現(xiàn)，初次取序列的一半為增量，以后每次減半，直到增量為1。
希爾排序是不穩(wěn)定的。
=====================================================
這個排序非常復雜，看了程序就知道了。首先需要一個遞減的步長，這里我們使用的是9、5、3、1（最后的步長必須是1）。工作原理是首先對相隔9-1個元素的所有內(nèi)容排序，然后再使用同樣的方法對相隔5-1個元素的排序，以次類推。
＃include<iostream.h>
voidShellSort(int*pData,intCount)
{
intstep[4];
step[0]=9;
step[1]=5;
step[2]=3;
step[3]=1;
inti,Temp;
intk,s,w;
for(inti=0;i<4;i++)
{
k=step[i];
s=-k;
for(intj=k;j<Count;j++)
{
iTemp=pData[j];
w=j-k;//求上step個元素的下標
if(s==0)
{
s=-k;
s++;
pData[s]=iTemp;
}
while((iTemp<pData[w])&&(w>=0)&&(w<=Count))
{
pData[w+k]=pData[w];
w=w-k;
}
pData[w+k]=iTemp;
}
}
}
voidmain()
{
intdata[]={10,9,8,7,6,5,4,3,2,1,-10,-1};
ShellSort(data,12);
for(inti=0;i<12;i++)
cout<<data[i]<<"";
cout<<"\n";
}
呵呵，程序看起來有些頭疼。不過也不是很難，把s==0的塊去掉就輕松多了，這里是避免使用0步長造成程序異常而寫的代碼。這個代碼我認為很值得一看。這個算法的得名是因為其發(fā)明者的名字D.L.SHELL。依照參考資料上的說法：“由于復雜的數(shù)學原因避免使用2的冪次步長，它能降低算法效率。”另外算法的復雜度為n的1.2次冪。同樣因為非常復雜并“我也不知道過程"，我們只有結果了。
5、快速排序
====================================================
算法思想簡單描述：
快速排序是對冒泡排序的一種本質改進。它的基本思想是通過一趟掃描后，使得排序序列的長度能大幅度地減少。在冒泡排序中，一次掃描只能確保最大數(shù)值的數(shù)移到正確位置，而待排序序列的長度可能只減少1。快速排序通過一趟掃描，就能確保某個數(shù)（以它為基準點吧）的左邊各數(shù)都比它小，右邊各數(shù)都比它大。然后又用同樣的方法處理它左右兩邊的數(shù)，直到基準點的左右只有一個元素為止。它是由C.A.R.Hoare于1962年提出的。
顯然快速排序可以用遞歸實現(xiàn)，當然也可以用棧化解遞歸實現(xiàn)。下面的函數(shù)是用遞歸實現(xiàn)的，有興趣的朋友可以改成非遞歸的。
快速排序是不穩(wěn)定的。最理想情況算法時間復雜度O(nlog2n)，最壞O(n2)
=====================================================
＃include<iostream.h>
voidrun(int*pData,intleft,intright)
{
inti,j;
intmiddle,iTemp;
i=left;
j=right;
middle=pData[(left+right)/2];//求中間值
do{
while((pData[i]<middle)&&(i<right))//從左掃描大于中值的數(shù)
i++;
while((pData[j]>middle)&&(j>left))//從右掃描大于中值的數(shù)
j--;
if(i<=j)//找到了一對值
{
//交換
iTemp=pData[i];
pData[i]=pData[j];
pData[j]=iTemp;
i++;
j--;
}
}while(i<=j);//如果兩邊掃描的下標交錯，就停止（完成一次）
//當左邊部分有值(left<j)，遞歸左半邊
if(left<j)
run(pData,left,j);
//當右邊部分有值(right>i)，遞歸右半邊
if(right>i)
run(pData,i,right);
}
voidQuickSort(int*pData,intCount)
{
run(pData,0,Count-1);
}
voidmain()
{
intdata[]={10,9,8,7,6,5,4};
QuickSort(data,7);
for(inti=0;i<7;i++)
cout<<data[i]<<"";
cout<<"\n";
}
這里我沒有給出行為的分析，因為這個很簡單，我們直接來分析算法：首先我們考慮最理想的情況
1.數(shù)組的大小是2的冪，這樣分下去始終可以被2整除。假設為2的k次方，即k=log2(n)。
2.每次我們選擇的值剛好是中間值，這樣，數(shù)組才可以被等分。
第一層遞歸，循環(huán)n次，第二層循環(huán)2*(n/2)......所以共有n+2(n/2)+4(n/4)+...+n*(n/n)=n+n+n+...+n=k*n=log2(n)*n所以算法復雜度為O(log2(n)*n)其他的情況只會比這種情況差，最差的情況是每次選擇到的middle都是最小值或最大值，那么他將變成交換法（由于使用了遞歸，情況更糟）。但是你認為這種情況發(fā)生的幾率有多大？？呵呵，你完全不必擔心這個問題。實踐證明，大多數(shù)的情況，快速排序總是最好的。如果你擔心這個問題，你可以使用堆排序，這是一種穩(wěn)定的O(log2(n)*n)算法，但是通常情況下速度要慢于快速排序（因為要重組堆）。
6、堆排序
====================================================
算法思想簡單描述：
堆排序是一種樹形選擇排序，是對直接選擇排序的有效改進。
堆的定義如下：具有n個元素的序列（h1,h2,...,hn),當且僅當滿足（hi>=h2i,hi>=2i+1）或（hi<=h2i,hi<=2i+1）(i=1,2,...,n/2)時稱之為堆。在這里只討論滿足前者條件的堆。
由堆的定義可以看出，堆頂元素（即第一個元素）必為最大項。完全二叉樹可以很直觀地表示堆的結構。堆頂為根，其它為左子樹、右子樹。
初始時把要排序的數(shù)的序列看作是一棵順序存儲的二叉樹，調整它們的存儲順序，使之成為一個堆，這時堆的根節(jié)點的數(shù)最大。然后將根節(jié)點與堆的最后一個節(jié)點交換。然后對前面(n-1)個數(shù)重新調整使之成為堆。依此類推，直到只有兩個節(jié)點的堆，并對它們作交換，最后得到有n個節(jié)點的有序序列。
從算法描述來看，堆排序需要兩個過程，一是建立堆，二是堆頂與堆的最后一個元素交換位置。所以堆排序有兩個函數(shù)組成。一是建堆的滲透函數(shù)，二是反復調用滲透函數(shù)實現(xiàn)排序的函數(shù)。
堆排序是不穩(wěn)定的。算法時間復雜度O(nlog2n)。
====================================================
voidsift(int*x,intn,ints)
{
intt,k,j;
t=*(x+s);
k=s;
j=2*k+1;
while(j
{
if(j
<*(x+j+1))*判斷是否滿足堆的條件：滿足就繼續(xù)下一輪比較，否則調整。*&&*(x+j)/>{
j++;
}
if(t<*(x+j))
{
*(x+k)=*(x+j);
k=j;
j=2*k+1;
}
else
{
break;
}
}
*(x+k)=t;
}
voidheap_sort(int*x,intn)
{
inti,k,t;
int*p;
for(i=n/2-1;i>=0;i--)
{
sift(x,n,i);
}
for(k=n-1;k>=1;k--)
{
t=*(x+0);
*(x+0)=*(x+k);
*(x+k)=t;
sift(x,k,0);
}
}
voidmain()
{
#defineMAX4
int*p,i,a[MAX];
p=a;
printf("Input%dnumberforsorting:\n",MAX);
for(i=0;i
{
scanf("%d",p++);
}
printf("\n");
p=a;
select_sort(p,MAX);
for(p=a,i=0;i
{
printf("%d",*p++);
}
printf("\n");
system("pause");
}
其他的交換法，雙向冒泡法等等就不具體介紹了。
三、幾種排序算法的比較和選擇
1.選取排序方法需要考慮的因素：
(1)待排序的元素數(shù)目n；
(2)元素本身信息量的大小；
(3)關鍵字的結構及其分布情況；
(4)語言工具的條件，輔助空間的大小等。
四、小結：
(1)若n較小(n<=50)，則可以采用直接插入排序或直接選擇排序。由于直接插入排序所需的記錄移動操作較直接選擇排序多，因而當記錄本身信息量較大時，用直接選擇排序較好。
(2)若文件的初始狀態(tài)已按關鍵字基本有序，則選用直接插入或冒泡排序為宜。
(3)若n較大，則應采用時間復雜度為O(nlog2n)的排序方法：快速排序、堆排序或歸并排序。快速排序是目前基于比較的內(nèi)部排序法中被認為是最好的方法。
(4)在基于比較排序方法中，每次比較兩個關鍵字的大小之后，僅僅出現(xiàn)兩種可能的轉移，因此可以用一棵二叉樹來描述比較判定過程，由此可以證明：當文件的n個關鍵字隨機分布時，任何借助于"比較"的排序算法，至少需要O(nlog2n)的時間。
(5)當記錄本身信息量較大時，為避免耗費大量時間移動記錄，可以用鏈表作為存儲結構。
JavaScript排序算法之希爾排序的2個實例
代碼示例：
functionshellSort(arr){
letlen=arr.length;
//gap即為增量
for(letgap=Math.floor(len/2);gap>0;gap=Math.floor(gap/2)){
for(leti=gap;i<len;i++){
letj=i;
letcurrent=arr[i];
while(j-gap>=0&¤t<arr[j-gap]){
arr[j]=arr[j-gap];
j=j-gap;
}
arr[j]=current;
}
}
}
vararr=[3,5,7,1,4,56,12,78,25,0,9,8,42,37];
shellSort(arr);
OK，本文到此結束，希望對大家有所幫助。
