1. 3. 用任意一種編程語言（C/C++/Java/C#/VB.NET）寫出任意一種你所知的排序演算法（比如：冒泡排序， 歸並排
#include<stdio.h>
#include<stdlib.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排序(不用)演算法復雜度沒算清楚
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)
{
//實現對數組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)
{
//實現對數組a[]中a[first]到a[last]升序的「插入」排序
//最壞情況為n的平方，，多用於小數組
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)
{
//實現對數組a[]中a[first]到a[last]升序的「選擇」排序
int i, j, temp, num;
for(i=first; i<last; 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)
{
//合並排序演算法中的實現合並的子程序
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("內存分配失敗！！！");
return;
}
for(i=0; i<iLLength; i++)
{
L[i] = a[p+i];
}
for(j=0; j<iRLength; j++)
{
R[j] = a[q+j+1];
}
i = 0;
j = 0;
for(k=p; k<=r; k++)
{
if((i<iLLength) && (j<iRLength) && (L[i]<=R[j]) || (j == iRLength))
{
a[k] = L[i];
i++;
}
else if(j<iRLength)
{
a[k] = R[j];
j++;
}
}
free(R);free(L);
}
void MergeSort(int a[],const int p,const int r)
{
//合並排序演算法-主程序
//n*lg(n),系數較小
int q;
if(p<r)
{
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)
{
//快速排序的(關鍵)分治過程
int temp, x, i, j;
x = a[r];
i = p - 1;
for(j=p; j<r; 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)
{
//快速排序演算法-主程序
//與下面的「尾遞歸實現方法」比較，缺點：右邊數組的遞歸不是必須的，增加了運行堆棧深度和調用開銷
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)
{
//快速排序演算法-主程序
//「尾遞歸實現方法」是對上面的快速排序主程序實現的一種優化
//系數較小,常用大數組
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)
{
//希爾排序演算法的關鍵子程序-插入排序子程序
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個增量，實現對數組a[]中a[p]到a[r]的排序
//dlta[]可能取值如：1,2,3,5,9 dala[k]=2^(t-k+1)-1 其中0<=k<=t<=ld(b-1)
//增量序列的最後一個值必須是1
//增量序列中的值沒有除1以外的因子， 其精確時間復雜度：數學上尚未解決的難題
int k;
for(k=0; k<t; k++)
{
ShellInsert(a,p,r,dlta[k]);
}
}
/************************堆排序***********************/
//堆排序，不如快速排序
//但是可用其來實現「優先順序隊列」
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);
}
}