_____谈谈排序算法
交换排序——>冒泡排序-->快速排序
选择排序——>简单选择排序——>堆排序
插入排序——>直接插入排序——>希尔排序
_____排序算法对比
|
名称 |
稳定性 |
时间复杂度 |
空间复杂度 |
描述 |
数据对象为链表 |
||
|
平均 |
最坏 |
||||||
|
冒泡排序 |
Y |
O(n^2) |
O(1) |
无序区，有序区。 |
|
||
|
选择排序 |
|
O(n^2) |
O(1) |
有序区，无序区 |
稳定性Y,其它同数组 |
||
|
插入排序 |
Y |
O(n^2) |
O(1) |
有序区，无序区 |
同数组 |
||
|
堆排序 |
|
O(n log n) |
O(1) |
最大堆，有序区 |
|
||
|
归并排序 |
Y |
O(n log n) |
O(n)+O(log n) |
将数据分为两段，逐段排序 |
空间复杂度O(1) |
||
|
快速排序 |
|
O(n log n) |
O(n^2) |
O(log n)-O(n) |
选择基数，调整方位 |
|
|
|
希尔排序 |
|
O(n log n) |
O(n^2) |
O(1) |
每次循环按间隔进行插入排序 |
|
|
快速排序针对小数目数组列表的优化为最佳的排列方法。
-------库函数
在stdlib 中定义了qsort库函数
void qsort (void* base, size_t num, size_t size,
int (*compar)(const void*,const void*));
//这是一个泛型函数，适用于不同的类型。
int compareMyType (const void * a, const void * b)
{
if ( *(MyType*)a < *(MyType*)b ) return -;
if ( *(MyType*)a == *(MyType*)b ) return ;
if ( *(MyType*)a > *(MyType*)b ) return ;
}
//我写的
void quickSort(void* base,size_t size,size_t low,size_t high,int (*compar)(const void*,const void*))
{
int left = low;
int right = high;
int keyPos = low; //set the first element key
uchar keyBuffer[size];
if(low >= high)
return;
memcpy( keyBuffer, (uchar *)base + keyPos*size, size ); while(right>left )
{
while( right>left && compar( (uchar *)base + right*size,keyBuffer )>=)
{
right--;
}
memcpy( (uchar *)base + left*size, (uchar *)base + right*size, size ); //right considered to store key
while( right>left && compar(keyBuffer, (uchar *)base + left*size)>= )
{
left++;
}
memcpy( (uchar *)base + right*size, (uchar *)base + left*size, size ); //left considered to store key
}
memcpy((uchar *)base + left*size,keyBuffer,size);
if(left->)
quickSort(base,size,low,left-,compar);
quickSort(base,size,left+,high,compar);
} void qsort (void* base, size_t num, size_t size,
int (*compar)(const void*,const void*))
{
quickSort(base,size,,num-,compar);
}