1 部分排序算法列表
- InsertionSort method.插入排序
- BubbleSort method.冒泡排序
- HeapSort method.堆排序
- ShellSort method.希尔排序
- SelectionSort method.选择排序
- MergeSort method.合并排序
- QuickSort method.快速排序
- CountingSort method.计数排序
2 算法实现
#define SWAP(nx,ny)/
nx^=ny;/
ny^=nx;/
nx^=ny;
//////////////////////////////////////////////////////////////////////////
/*
**marco used in heapSort
*/
#define PARENT(i) ((i - 1) / 2 )
#define LEFT(i) (2*(i) + 1)
#define RIGHT(i) (2*(i) + 2)
/////////////////////一般的swap函数///////////////////////////////////////
void swap(int&a,int&b)
{
int temp = a;
a = b;
b = temp;
}
///////////////////////输出函数////////////////////////////////////////////
void print(int a[],int len)
{
for (int i = 0;i< len;i++)
printf("%-3d",a[i]);
printf("/n");
}
///////////////////////重置函数////////////////////////////////////////
void randCast(int a[],int len)
{
for(int i = 0;i < len / 2;++i)
{
swap(a[i],a[rand() % len]);
}
}
/////////////////////////寻找最大值////////////////////////////////////////
int findMax(int a[],int len)
{
int m = a[0];
for(int i = 1;i < len;++i)
{
if (a[i] > m)
{
m = a[i];
}
}
return m;
}
///////////////////////// 插入排序 ///////////////////////////////////////
/*
**类型:比较排序、原地排序、稳定排序
**时间复杂度O(n^2)
**最坏:逆序O(n^2)
**最优:顺序O(n)
*/
void insertionSort(int array[],int len)
{
int key;
for(int j = 1;j < len;j++)
{
key = array[j];
for(int i = j - 1;i >= 0;i--)
{
if(array[i] > key)
array[i + 1] = array[i];
else
break;
}
array[i+1] = key;
}
}
/////////////////////////插入排序(递归版本)///////////////////////////////////////////
/*
**类型:比较排序、原地排序、稳定排序
**时间复杂度O(n^2)
**最坏:逆序O(n^2)
**最优:顺序O(n)
*/
void insertionSort_rec(int array[],int len)
{
int key,i;
if(len == 0)
return;
insertionSort_rec(array,len - 1);
i= len - 2;
key=array[len - 1];
while(i >= 0 && array[i]>key)
{
array[i+1]=array[i];
i=i-1;
}
array[i+1]=key;
}
///////////////////////// 选择排序 //////////////////////////////////////////
/*
**类型:比较排序、原地排序、稳定排序
**时间复杂度O(n^2)
**逆序O(n^2)
**顺序O(n^2)
*/
void selectionSort(int array[],int len)
{
int min_index;
for(int i = 0;i < len - 1; i++)
{
min_index = i;
for(int j = i + 1;j < len;j++)
{
if(array[j] < array[min_index])
min_index = j;
}
swap(array[i],array[min_index]);
}
}
/////////////////////////// 冒泡排序 ///////////////////////////////////////
/*
**类型:比较排序、原地排序、稳定排序
**时间复杂度O(n^2)
**逆序O(n^2)
**顺序O(n)
*/
void bubbleSort(int array[], int len)
{
int flag;
for (int j = len-1; j != 0; --j)
{
flag = 0;
for (int i=len - 1; i != len - 1 - j; --i)
{
if (array[i-1]>array[i])
{
swap(array[i-1],array[i]);
flag = 1;
}
}
if (flag == 0)
return;
}
}
///////////////////////// 快速排序 //////////////////////////////////////////
/*
**类型:比较排序、原地排序、非稳定排序
**时间复杂度O(nlgn)
**最坏:划分不对称O(n^2)
**最优:划分对称O(nlgn)
*/
int partition (int array[], int p, int r)
{
int x = array[ r ];
int i = p - 1;
for (int j = p; j <= r - 1; j++)
if (array[j] <= x )
{
i++;
swap(array[i],array[j]);
}
swap( array [ i + 1 ], array [ r ]);
return i+1;
}
void quickSort (int array [], int p, int r )
{
int q;
if ( p < r )
{
q = partition(array, p, r);
quickSort (array, p, q - 1 );
quickSort (array, q + 1, r);
}
}
////////////////////////堆排序/////////////////////////////////////////
/*
**类型:比较排序、原地排序、非稳定排序
**时间复杂度O(nlgn)
*/
int heapSize;
void maxHeapify(int A[],int i)
{
int l = LEFT(i),r = RIGHT(i),largest;
if ((l <= heapSize) && (A[l] > A[i]))
largest = l;
else
largest = i;
if ((r <= heapSize) && (A[r] > A[largest]))
largest = r;
if(largest != i)
{
swap(A[i],A[largest]);
maxHeapify(A,largest);
}
}
void buildMaxHeap(int A[],int len)
{
heapSize = len - 1;
for(int i = len / 2 - 1;i >= 0;--i)
maxHeapify(A,i);
}
void heapSort(int A[],int len)
{
buildMaxHeap(A,len);
for (int i = len - 1;i >= 1;--i)
{
SWAP(A[0],A[i]);
heapSize -= 1;
maxHeapify(A,0);
}
}
//////////////////////////shell排序/////////////////////////////////////
/*
**类型:比较排序、原地排序、非稳定排序
**最差:O(nlog^2(n))
**最优:O(n)
*/
void shellSort (int a[], int n)
{
int i, j, k, h, v;
int cols[16] = {1391376, 463792, 198768, 86961, 33936, 13776, 4592,
1968, 861, 336, 112, 48, 21, 7, 3, 1};
for (k=0; k<16; k++)
{
h=cols[k];
for (i=h; i<n; i++)
{
v=a[i];
j=i;
while (j>=h && a[j-h]>v)
{
a[j]=a[j-h];
j=j-h;
}
a[j]=v;
}
}
}
/////////////////////////////合并排序/////////////////////////////////////
/*
**类型:比较排序、非原地排序、稳定排序
**时间复杂度O(nlgn)
*/
void Merge(int Array[], int p, int q, int r)
{
int n1 = q - p + 1;
int n2 = r - q;
int* LArray = new int[n1];
int* RArray = new int[n2];
int i = 0, j = 0, k = p;
for(i = 0; i < n1; ++i)
{
LArray[i] = Array[p+i];
}
for(i = 0; i < n2; ++i)
{
RArray[i] = Array[q+i+1];
}
i = j = 0;
while(true)
{
if(i == n1 || j == n2)
{
break;
}
if(LArray[i] < RArray[j])
{
Array[k++] = LArray[i++];
}
else
{
Array[k++] = RArray[j++];
}
}
if(i == n1 && (j != n2))
{
for(; j < n2; ++j)
{
Array[k] = RArray[j];
++k;
}
}
if((j == n2) && (i != n1))
{
for(; i < n1; ++i)
{
Array[k] = LArray[i];
++k;
}
}
delete [] LArray;
delete [] RArray;
}
void mergeSort(int Array[], int p , int r)
{
int q;
if(p < r)
{
q = (p+r)/2;
mergeSort(Array, p, q);
mergeSort(Array, q+1, r);
Merge(Array, p, q, r);
}
}
///////////////////////////计数排序//////////////////////////////////////
/*
**类型:非比较排序、非原地排序、稳定排序
**时间复杂度O(n)
*/
void countingSort(int A[],int B[],int range,int len)
{
int* C = new int[range];
memset(C,0,sizeof(int)*range);
for(int j = 0;j < len;++j)
C[A[j]] += 1;
for(int i = 1;i < range;++i)
C[i] = C[i] + C[i - 1];
for(j = len - 1;j >= 0;--j)
{
B[C[A[j]] - 1] = A[j];
C[A[j]] -= 1;
}
delete [] C;
}
int main()
{
typedef void (*fun_ptr)(int a[],int len);
fun_ptr func[] = {insertionSort,insertionSort_rec,bubbleSort,
heapSort,shellSort,selectionSort};
char *funcName[]={"insertionSort","insertionSort_rec","bubbleSort",
"heapSort","shellSort","selectionSort"};
int a[]={2,4,1,3,6,7,9,8,0,5,14,11,10};
const int len = sizeof(a)/sizeof(*a);
int b[len],Id;
printf("The initial array is:/n");
print(a,len);
printf("Select a method to sort the array:/n");
printf("input the corresponding number to select,-1 to quit)/n/n");
printf("/t/tMethod List/n");
printf("1.InsertionSort method./n");
printf("2.InsertionSort method,using recursion method./n");
printf("3.BubbleSort method./n");
printf("4.HeapSort method./n");
printf("5.ShellSort method./n");
printf("6.SelectionSort method./n");
printf("7.MergeSort method./n");
printf("8.QuickSort method./n");
printf("9.CountingSort method./n/n");
while(scanf("%d",&Id) == 1,Id != -1)
{
if(Id <= 6)
{
printf("Initial array:");
randCast(a,len);
print(a,len);
func[Id - 1](a,len);
printf("After %s,result:",funcName[Id -1]);
print(a,len);
}
else if (Id == 7)
{
printf("Initial array:");
randCast(a,len);
print(a,len);
mergeSort(a,0,len);
printf("After mergeSort,result:");
print(a,len);
}
else if(Id == 8)
{
printf("Initial array:");
randCast(a,len);
print(a,len);
quickSort(a,0,len);
printf("After quickSort,result:");
print(a,len);
}
else if(Id == 9)
{
printf("Initial array:");
randCast(a,len);
print(a,len);
countingSort(a,b,findMax(a,len) + 1,len);
printf("After CountingSort,is:");
print(b,len);
}
else
{
printf("No such method!");
break;
}
}
return 0;
}
3 结果
附注:
1.合并排序参考了http://blog.csdn.net/summericeyl/archive/2010/02/26/5327761.aspx上的的程序
2.希尔排序程序来自http://www.iti.fh-flensburg.de/lang/algorithmen/sortieren/shell/shellen.htm上的程序
3.冒泡程序参考了http://blog.csdn.net/delphiwcdj/archive/2010/03/28/5424432.aspx上的程序
4.其余算法思想均来自Cormen等著的《算法导论》