#includestdio.h
讓客戶滿意是我們工作的目標(biāo)，不斷超越客戶的期望值來(lái)自于我們對(duì)這個(gè)行業(yè)的熱愛(ài)。我們立志把好的技術(shù)通過(guò)有效、簡(jiǎn)單的方式提供給客戶，將通過(guò)不懈努力成為客戶在信息化領(lǐng)域值得信任、有價(jià)值的長(zhǎng)期合作伙伴，公司提供的服務(wù)項(xiàng)目有：域名注冊(cè)、網(wǎng)站空間、營(yíng)銷(xiāo)軟件、網(wǎng)站建設(shè)、珠海網(wǎng)站維護(hù)、網(wǎng)站推廣。
#includestdlib.h
void BubbleSort(int a[], const int first, const int last);//冒泡排序
void InsertSort(int a[], const int first, const int last);//插入排序
void SelectSort(int a[], const int first, const int last);//選擇排序
void MergeSort(int a[], const int p, const int r);//合并排序
void QuickSort(int a[],const int p,const int r);//快速排序
void ShellSort(int a[],const int p,const int r,const int dlta[],const int t);//希爾排序
void HeapSort(int a[],const int p, int r); //堆排序
void StoogeSort(int a[],const int p,const int r);//Stooge排序(不用)算法復(fù)雜度沒(méi)算清楚
void main()
{
//插入排序算法
int a[11] = {6,4,5,3,2,1};
int dlta[]={9,5,3,2,1};
//BubbleSort(a,0,5);
//InsertSort(a,0,5);
//SelectSort(a,0,5);
//MergeSort(a,0,5);
//QuickSort(a,0,5);
//ShellSort(a,0,5,dlta,5);
HeapSort(a,0,5);
//StoogeSort(a,0,5);
for(int i=0; i=5;i++)
{
printf("%d ",a[i]);
}
}
/************************冒泡排序***********************/
void BubbleSort(int a[], int first, int last)
{
//實(shí)現(xiàn)對(duì)數(shù)組a[]中a[first]到a[last]升序的“冒泡”排序
int i,j,temp;
for(i=first; i=last; i++)
{
for(j=first; j last-i; j++)
{
if(a[j] a[j+1])
{
temp = a[j];
a[j] = a[j+1];
a[j+1] = temp;
}
}
}
}
/************************插入排序***********************/
void InsertSort(int a[], int first, int last)
{
//實(shí)現(xiàn)對(duì)數(shù)組a[]中a[first]到a[last]升序的“插入”排序
//最壞情況為n的平方，，多用于小數(shù)組
int i,j,temp;
for(i=first+1; i=last; i++)
{
temp = a[i];
j = i - 1;
while((j = 0) (a[j] temp))
{
a[j+1] = a[j];
j--;
}
a[j+1] = temp;
}
}
/************************選擇排序***********************/
void SelectSort(int a[], int first, int last)
{
//實(shí)現(xiàn)對(duì)數(shù)組a[]中a[first]到a[last]升序的“選擇”排序
int i, j, temp, num;
for(i=first; ilast; i++)
{
num = i;
for(j=i+1; j=last; j++)
{
if(a[j] a[num])
{
num = j;
}
}
if(i != num)
{
temp = a[num];
a[num] = a[i];
a[i] = temp;
}
}
}
/************************合并排序***********************/
void Merge(int a[],const int p,const int q,const int r)
{
//合并排序算法中的實(shí)現(xiàn)合并的子程序
int iLLength,iRLength;
int *L, *R, i, j, k;
iLLength = q - p + 1;
iRLength = r - q;
L = (int *)malloc(iLLength*sizeof(int)); //或者 C++中 new int[iLLength];
R = (int *)malloc(iRLength*sizeof(int)); //或者 C++中 new int[iRLength];
if(L == 0 || R== 0)
{
printf("內(nèi)存分配失?。。?！");
return;
}
for(i=0; iiLLength; i++)
{
L[i] = a[p+i];
}
for(j=0; jiRLength; j++)
{
R[j] = a[q+j+1];
}
i = 0;
j = 0;
for(k=p; k=r; k++)
{
if((iiLLength) (jiRLength) (L[i]=R[j]) || (j == iRLength))
{
a[k] = L[i];
i++;
}
else if(jiRLength)
{
a[k] = R[j];
j++;
}
}
free(R);free(L);
}
void MergeSort(int a[],const int p,const int r)
{
//合并排序算法-主程序
//n*lg(n),系數(shù)較小
int q;
if(pr)
{
q = (p+r)/2;
MergeSort(a,p,q);
MergeSort(a,q+1,r);
Merge(a,p,q,r);
}
}
/************************Stooge排序***********************/
void StoogeSort(int a[],const int p,const int r)
{
//Stooge算法
int temp, k;
if(a[p]a[r])
{
temp = a[p];
a[p] = a[r];
a[r] = temp;
}
if((p+1) = r)
{
return;
}
k = (r-p+1)/3;
StoogeSort(a,p,r-k);
StoogeSort(a,p+k,r);
StoogeSort(a,p,r-k);
}
/************************快速排序*********************/
int QuickPartition(int a[],const int p,const int r)
{
//快速排序的(關(guān)鍵)分治過(guò)程
int temp, x, i, j;
x = a[r];
i = p - 1;
for(j=p; jr; j++)
{
if(a[j] = x)
{
i = i + 1;
temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
temp = a[i+1];
a[i+1] = a[r];
a[r] = temp;
return (i+1);
}
/*
void QuickSort(int a[],const int p,const int r)
{
//快速排序算法-主程序
//與下面的“尾遞歸實(shí)現(xiàn)方法”比較，缺點(diǎn)：右邊數(shù)組的遞歸不是必須的，增加了運(yùn)行堆棧深度和調(diào)用開(kāi)銷(xiāo)
int q;
if(p r)
{
q = QuickPartition(a, p, r);
QuickSort(a, p, q-1);
QuickSort(a, q+1, r);
}
}
*/
void QuickSort(int a[],int p,const int r)
{
//快速排序算法-主程序
//“尾遞歸實(shí)現(xiàn)方法”是對(duì)上面的快速排序主程序?qū)崿F(xiàn)的一種優(yōu)化
//系數(shù)較小,常用大數(shù)組
int q;
while(p r)
{
q = QuickPartition(a, p, r);
QuickSort(a, p, q-1);
p = q + 1;
}
}
/************************希爾排序**********************/
void ShellInsert(int a[],const int p,const int r, int dk)
{
//希爾排序算法的關(guān)鍵子程序-插入排序子程序
int i, j, temp;
for(i=p+dk; i=r; i++)
{
if(a[i] a[i-dk])
{
temp = a[i];
for(j=i-dk; ((j=0) (temp a[j])); j -= dk)
{
a[j+dk] = a[j];
}
a[j+dk] = temp;
}
}
}
void ShellSort(int a[],const int p,const int r,const int dlta[],const int t)
{
//希爾排序算法-主程序
//按增量序列dlta[]中的前t個(gè)增量，實(shí)現(xiàn)對(duì)數(shù)組a[]中a[p]到a[r]的排序
//dlta[]可能取值如：1,2,3,5,9 dala[k]=2^(t-k+1)-1 其中0=k=t=ld(b-1)
//增量序列的最后一個(gè)值必須是1
//增量序列中的值沒(méi)有除1以外的因子， 其精確時(shí)間復(fù)雜度：數(shù)學(xué)上尚未解決的難題
int k;
for(k=0; kt; k++)
{
ShellInsert(a,p,r,dlta[k]);
}
}
/************************堆排序***********************/
//堆排序，不如快速排序
//但是可用其來(lái)實(shí)現(xiàn)“優(yōu)先級(jí)隊(duì)列”
int Parent(int i)
{
return ((i+1)/2-1);
}
int Right(int i)
{
return (2*(i+1)-1);
}
int Left(int i)
{
return (2*(i+1));
}
void Max_Heapify(int a[],const int hplast,const int i)
{
int l, r,largest,temp;
l = Left(i);
r = Right(i);
largest = ((l=hplast) (a[l]a[i])) ? l:i;
if((r=hplast) (a[r]a[largest]))
{
largest = r;
}
if(largest != i)
{
temp = a[i];
a[i] = a[largest];
a[largest] = temp;
Max_Heapify(a,hplast,largest);
}
}
void Build_Max_Heap(int a[],const int p, const int r)
{
int i;
for(i = (p+r)/2; i=p; i--)
{
Max_Heapify(a,r,i);
}
}
void HeapSort(int a[],const int p, int r)
{
int i,temp;
Build_Max_Heap(a,p,r);
for(i = r; i p; i--)
{
temp = a[p];
a[p] = a[i];
a[i] = temp;
r -= 1;
Max_Heapify(a,r,0);
}
}
結(jié)構(gòu)體無(wú)法初始化值，你可以用類(lèi)實(shí)現(xiàn)，或者寫(xiě)一個(gè)構(gòu)造函數(shù)，把值傳進(jìn)去。
Public Structure wheelmodel
Public ID As Short
Public swapway() As Short
Public start As Short
Public Sub New(ByVal Size As UShort) 'Size就是傳入的數(shù)組的大小
swapway = New Short(Size) {}
End Sub
End Structure
調(diào)用的時(shí)候：
Dim x As wheelmodel = New wheelmodel(10)
看了你說(shuō)遞歸的效率低。那么你可以不用的。
給出的方法就是先生成第一個(gè)排列，然后每次調(diào)用下面的函數(shù)給出下一個(gè)排列，這樣生成的效率很高，這個(gè)函數(shù)可以內(nèi)聯(lián)。
這個(gè)是很經(jīng)典的排列組合算法??？在網(wǎng)上能搜到一大堆。
大概是那種帶指向的移動(dòng)的算法。我給你搜一個(gè)吧。
我找了幾個(gè)，這個(gè)是我覺(jué)得說(shuō)的比較清楚的，你可以仔細(xì)參考一下，看不懂的話再搜點(diǎn)別的好了。。
全排列的算法跟這個(gè)不太一樣的。需要有點(diǎn)改動(dòng)的。
至于語(yǔ)言的話，應(yīng)該不會(huì)有太大問(wèn)題吧。。basic版的確實(shí)比較少，現(xiàn)在我也比較懶不想動(dòng)手寫(xiě)。。還是要靠你自己啦。
★生成排列的算法：
比如要生成5，4，3，2，1的全排列，首先找出一個(gè)最小的排列12345, 然后依次調(diào)用n!次STL算法中的next_permutation()即可輸出所有的全排列情況。所以這種算法的細(xì)節(jié)就是STL algorithm中next_permutation()的實(shí)現(xiàn)機(jī)制。詳細(xì)的實(shí)現(xiàn)代碼，大伙可以參考侯捷的《STL源代碼剖析》，在這里我只說(shuō)一下我的理解：
1 首先從最尾端開(kāi)始往前尋找兩個(gè)相鄰元素，令第一個(gè)元素為*i,第二個(gè)元素為*ii，且滿足*i*ii，找到這樣一組相鄰的元素后。
2 再?gòu)淖钗捕碎_(kāi)始往前檢驗(yàn)，找出第一個(gè)大于*i的元素，令為*k，將i,k元素對(duì)調(diào)。
3 再將ii及ii之后的所有元素顛倒排列，此即所求之"下一個(gè)"排列。
prev_permutation()算法的思路也基本相同，只不過(guò)它們尋找的"拐點(diǎn)"不同，在next_permutation()算法中尋找的是峰值拐點(diǎn)，而在prev_permutation()算法中尋找的是谷值拐點(diǎn)。另外，在第二步中，prev_permutation()要找的是第一個(gè)小于*i的元素而不是第一個(gè)大于*i的元素。
具體例子，有空再舉，現(xiàn)在時(shí)間太晚了:)
★生成組合的算法：
如下面截圖所示，分全組合和r-組合兩種情況。
這里有一段核心代碼：
//--------------------------------------------------------
// Generate next combination (algorithm from Rosen p. 286)
//--------------------------------------------------------
public int[] getNext () {
if (numLeft.equals (total)) {
numLeft = numLeft.subtract (BigInteger.ONE);
return a;
}
int i = r - 1;
while (a[i] == n - r + i) {
i--;
}
a[i] = a[i] + 1;
for (int j = i + 1; j r; j++) {
a[j] = a[i] + j - i;
}
numLeft = numLeft.subtract (BigInteger.ONE);
return a; //這里返回的a數(shù)組，存儲(chǔ)的就是下標(biāo)的排列組合。
}
到這里，也許大伙會(huì)有一個(gè)疑問(wèn)，假如要求的不是數(shù)字的排列組合，而是字符或字符串的排列組合呢？怎么辦？其實(shí)很簡(jiǎn)單，你只要拿數(shù)組的下標(biāo)來(lái)做排列組合，返回他們下標(biāo)的排列組合，然后再到原數(shù)組中讀取字符串值，就可以輸出全部的排列組合結(jié)果。
重慶分公司
重慶分公司
