为准备面试将几个排序算法写了一下，熟悉熟悉，到时也不至于手生。
一 ﹑冒泡法
最简单的冒泡法，时间复杂度O(n)。
int bubble_sort( int a[] , int n )
{
int i , j ;
for ( i = 1 ; i <= n ; i ++ ) // 多少趟
{
for ( j = 0 ; j <= n - i ; j ++ )
{
if ( a[i] > a[j+1] )
{
swap(&a[i],&a[j]); // 交换
}
}
}
}
总结：
冒泡法，算法简单，易于实现，且整个过程可以很形象地关键字如泡泡一样上升。
二﹑选择排序
int select_sort( int a[] , int n )
{
int i , j , k ;
for ( i =1 ; i <= n ; i ++ )
{
k = 0 ;
for ( j = 1 ; j <= n - i ; j ++ )
{
if ( a[j] > a[k] )
{
k = j ;
}
}
swap(&a[k],&a[n-i]);
}
}
总结：
选择排序对冒泡法的交换进行改进。
三﹑快速排序
int qsort( int a[] , int low, int high )
{
if ( low == high )
{
return 0 ;
}
int i = partion(a,low,high);
qsort(a,low,i-1);
qsort(q,i+1,high);
}
partion算法1：
int partion( int a[] , int low , int high )
{
int x = a[low] ;
while( low < high )
{
for ( ; low < high && a[high] >= x ; ) high-- ;
swap(&a[high],&a[low]);
for ( ; low < high && a[low] <= x ; ) low++ ;
swap(&a[low],&a[high]);
}
return low ;
}
partion算法2：
int partion( int a[] , int low , int high )
{
int x = a[low] ;
while( low < high )
{
for ( ; low < high && a[high] >= x ; ) high-- ;
a[low] = a[high] ;
for ( l low < high && a[low] <= x ; ) low++;
a[high] = a[low] ;
}
a[low] = x ;
}
总结：
快排的平均性能O(nlgn) ， 这是每次将它分为两个均等的区间即T(n)=2T(n/2)。但是若本来有序的情况下，则是T(n)=T(1)+T(n-1)，可以看到退化为冒泡法啦。当然这里可以利用随机选取避免的。 快速排序的示例：这里使用3.14159来排序，呵呵，这个比较有意义。将本来没有意思的东西变得有意思这是某某的职责。当时，我感觉这个partion这个过程，就好像是将
枢纽像抛皮球一样从左抛到右，又从右抛到左。
四﹑堆排序
堆排序与元素的初始序列无关，在最坏的情况下也是O(lgn)，这个优点也是快速排序不能比拟的。堆排序的思想：建一个初始堆，然后交换堆顶元素和序列最末尾的一个元素，然后将该元素筛下去。
初始序列: 49 38 65 97 76 13 27 49~
图一 筛选97
图二 筛选65
图三 筛选38
图四 筛选49
至此完成初始堆的建立，交换13和97，然后又是重复调用该过程即可。如下图所示:
然后序列为 97 27 38 49~ 76 65 49重复执行上述过程即可。
附上源代码：
#include<stdio.h>
void swap( int &a , int &b )
{
int tmp ;
tmp = a ;
a = b ;
b = tmp ;
}
void heapadjust( int a[] , int s , int m )
{
int j ;
for ( j = 2*s ; j <= m ; j *=2 ) //若下标从0开始 heapadjust(a,0,0) 那么这里是一个死循环 
{
if ( j<m && a[j+1] < a[j] )
{
j++ ;
}
if( a[j] < a[s] )
{
swap(a[s],a[j]);
}
else
{
break ;
}
s = j ;
}
}
void heapsort( int a[] , int n )
{
int i ;
for ( i = n/2 ; i >= 1 ; i-- )
{
heapadjust(a,i,n);
}
for ( i = n ; i >= 1 ; i-- )
{
swap(a[1],a[i] );
heapadjust(a,1,i-1);
}
}
int main()
{
int i , n ;
int c[] = { 0,49 , 38 , 65 , 97 , 13 , 27 , 49 } ; //这里下标从1开始好
n = sizeof(c)/sizeof(int) ;
heapsort(c,n);
for ( i = 1 ; i < n ; i++ )
{
printf("\t%d",c[i] );
}
printf("\n");
#ifdef __cplusplus
printf("c++\n"); //查看是c++编译器么
#endif
return 0 ;
}
五﹑基数排序
传说中O(n+rd)的排序算法，前面的几种都是比较和移动的算法，而 基数排序借助多关键字的思想(摸扑克牌)，进行r次分配和收集。
#include<stdio.h>
#include<assert.h>
//算法仅考虑正数的情况 对于有负数的情况要先将负数打出来 然后额外排序
//可以将正数看成是字符串的形式
#define MAX_SPACE 1000
#define RADIX 10
typedef struct {
int key ;
int next ;
}SLCell;
typedef struct {
SLCell r[MAX_SPACE];
int keynum ;
int recnum ;
}SLList;
typedef int ArrType[RADIX];
ArrType front , end ;
//计算出第i位的数
int ord( int n , int i )
{
int r ;
assert(i!=0); //要经常使用断言 使程序更加稳定
r = ( n %(i*10) )/i ;
return r ;
}
//静态表中已按前i-1个关键字排好 下面排i个关键字
void Distribute( SLCell *r , int i , ArrType &f , ArrType &e )
{
int j , p ;
// 队首置空
for ( j = 0 ; j < RADIX ; j ++ )
{
f[j] = 0 ;
}
for ( p = r[0].next ; p ; p=r[p].next )
{
j = ord(r[p].key , i*10) ;
if ( !f[j] ) //插入静态链表中
{
f[j] = p ;
}
else
{
r[e[j]].next = p ;
}
e[j] = p ;
}
}
//这里传来i其实没用 主要是在Radixsort函数调用看起来美观
void Collect(SLCell *r , int i , ArrType &f , ArrType &e )
{
int j , t ;
for ( j = 0 ; j < RADIX && !f[j] ; j++ );
r[0].next = j ;
t = e[j] ;
while ( j < RADIX )
{
for (j++ ; !f[j] && j < RADIX ; j++) ; //找到下一个不为空队首
if ( f[j] )
{
r[t].next = f[j] ;
t = e[j] ;
}
}
r[t].next = 0 ;
}
void Radixsort( SLList &L )
{
int i ;
for( i = 0 ; i < L.recnum ; i++ )
{
L.r[i].next = i+ 1 ;
}
L.r[L.recnum].next = 0 ;
for ( i = 1 ; i <= L.keynum ; i++ ) //按关关键字从小到大分配 收集
{
Distribute(L.r,i,front,end);
Collect(L.r,i,front,end);
}
}
int main()
{
int n , i ;
int a[] = { 0,8, 9 , 10 , 12 , 15 ,16,100, 102,115} ;
n = sizeof(a) / sizeof(int) -1 ;
SLList list ;
for ( i = 1 ; i <= n ; i ++ )
{
list.r[i].key = a[i] ;
}
list.recnum = n ;
list.keynum = 3 ;
Radixsort(list);
for ( i = 1; i <=n ; i++ )
{
printf("\t%d",list.r[i]);
}
printf("\n");
return 0 ;
}