整理了几个排序算法，通过测试来看，最快的还是快速排序算法，简直不是一个数量级的速度。
//一些排序算法整理
//插入排序算法
//直接插入排序
void
direct_insert_sort(int *a,int len)
{
//思路：最后一个依次和前面的进行比较
//将满足的条件的往后移动，当然是从头
//开始且是从最小比较数组开始逐渐扩大
//到整个数组
int i,j,temp;
for(i = 1;i < len;++i) {
//获取最后一个索引数据
temp = a[i];
for(j = i - 1;j >= 0;--j) {
//从倒数第二个开始
if(a[j] > temp)//升序排列
a[j + 1] = a[j];
else
break;//立刻退出
}
//将最后一个位置插入到合适的位置
a[j + 1] = temp;
}
}
//希尔排序
void
shell_insert_sort(int *a,int len)
{
//思路：就是比直接插入排序多了层
//循环，这层循环是用来控制步进按
//照算法的本来思路是这样可以减少
//交换次数
int i,j,h,temp;
for(h = len / 2;h > 0;h /= 2) {
//内层其实本质还是直接插入
//算法思路
//注意下i += h和i++两者对算
//法的影响
for(i = h;i < len;i += h) {
//获取最后一个索引的值
temp = a[i];
for(j = i - h;j >= 0;j -= h) {
if(a[j] > temp)//升序排列
a[j + h] = a[j];
else
break;
}
//将找到的位置插入最后一个索引
a[j + h] = temp;
}
}
}
//选择排序
//冒泡排序
void
bubble_swap_sort(int *a,int len)
{
//思路：从数组最后开始两两比较
//将底层满足要求的数据逐渐交换
//到上层，可能导致交换次数太多
int i,j,temp;
//如果一次冒泡中没有发生交换可
//以认为此次排列已经结束
bool exchange = false;
for(i = 0;i < len - 1;++i) {
for(j = len - 1;j > i;--j) {
//满足条件的就进行交换
if(a[j] < a[j - 1]) {
temp = a[j];
a[j] = a[j - 1];
a[j - 1] = temp;
exchange = true;
}
}
if(exchange)
exchange = false;
else
break;
}
}
//快速排序
void
quick_swap_sort(int *a,int low,int high)
{
//思路：从数组中找一个值
//然后排列数组使其两边要
//么大于要么小于这个值，
//然后递归下去排序
//优势在于每次找中间值可
//以交换很多次。
int _low,_high,qivot;
if(low < high) {
_low = low;
_high = high;
//这里从最后一个开始
qivot = a[low];
//找中间值的办法就是逐渐逼近
//从头尾两端开始逼近，顺便也
//排序了
while(_low < _high) {
//既然是从low开始，那么首先
//就从high找小于qivot的（升
//序排列）
while(_low < _high && a[_high] > qivot)
--_high;//逐渐向中间逼近
if(_low < _high)//必然是找到了a[_high] > qivot的情况
a[_low++] = a[_high];
//这下a[_high]空出位置来了，所以从low找
//比qivot大的数据
while(_low < _high && a[_low] < qivot)
--_low;//逼近中间
if(_low < _high)
a[_high--] = a[_low];
}
//最后_low == _high那么这个位置就是qivot的位置
a[_low] = qivot;
//递归下去
quick_swap_sort(a,low,_high - 1);
quick_swap_sort(a,_low + 1,high);
}
}
//选择排序
//直接选择排序
void
direct_select_sort(int *a,int len)
{
//思路：就是遍历数组找到极值
//放到头或者尾，这样逐渐缩小
//范围到最小比较数组
int i,j,pos,temp;
for(i = 0;i < len - 1;++i) {
//从头开始获取一个值假设为极值
pos = i;
for(j = i + 1;j < len;++j) {
//满足条件
if(a[pos] > a[j])//升序
pos = j;
}
if(pos != i) {
//进行交换
temp = a[pos];
a[pos] = a[i];
a[i] = temp;
}
}
}
void
disp(int *a,int len)
{
int i = 0;
for(;i < len;i++) {
if(i != 0 && i % 16 == 0)
printf("\n");
printf(" %d",a[i]);
}
printf("\n");
}
#define TEST_ARRAY_LEN 100000
#define TEST_COUNT 1
int
main(int argc,char *argv[])
{
//int a[] = {1,8,4,0,9,6,3,7,2,18,74,5,64,12,39};
//int len = sizeof(a) / sizeof(a[0]);
//direct_insert_sort(a,len);
//shell_insert_sort(a,len);
//bubble_swap_sort(a,len);
//quick_swap_sort(a,0,len - 1);
//direct_select_sort(a,len);
disp(a,len);
return 0;
}
</div>
</div>