_____谈谈排序算法
交换排序——>冒泡排序-->快速排序
选择排序——>简单选择排序——>堆排序
插入排序——>直接插入排序——>希尔排序
_____排序算法对比
| 名称 | 稳定性 | 时间复杂度 | 空间复杂度 | 描述 | 数据对象为链表 | ||
| 平均 | 最坏 | ||||||
| 冒泡排序 | 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 -1; if ( *(MyType*)a == *(MyType*)b ) return 0; if ( *(MyType*)a > *(MyType*)b ) return 1;} //我写的
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 )>=0) { 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)>=0 ) { 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-1>0) quickSort(base,size,low,left-1,compar); quickSort(base,size,left+1,high,compar);}void qsort (void* base, size_t num, size_t size, int (*compar)(const void*,const void*)){ quickSort(base,size,0,num-1,compar);}