#include <stdio.h>
//定义一个返回值为int,参数为（int，int）的函数指针类型为cmp
typedef int (*cmp)(int, int);
void printA (int num[], int len)
{
int i;
for (i = 0;i < len; i++)
printf ("%d ",num[i]);
putchar ('\n');
}
//交换
void swap (int a[], int i, int j)
{
int tmp = a[i];
a[i] = a[j];
a[j] = tmp;
}
//升序判断
int cmp_up (int a, int b)
{
return (a - b);
}
//降序判断
int cmp_down (int a, int b)
{
return (b - a);
}
/*
1、sort()函数中回调 cmp_down()和cmp_up()函数；
2、函数通过cmp类型的函数指针func传入。
*/
//冒泡排序
void bubble_sort (int num[], int len, cmp func)
{
int i, j;
for (i = 0; i < len-1; i++) //N个数比较N-1轮
{
for (j = 0; j < len-i-1; j++) //第i轮比较N-i-1次
{
//根据排序条件交换相邻两数
if (func (num[j], num[j+1]) > 0)
{
swap (num, j, j+1);
}
}
}
}
//鸡尾酒排序
void cocktail_sort (int num[], int len, cmp func)
{
int i;
int left = 0;
int right = len - 1;
//从两端向中间查找最大和最小的元素
while (left < right)
{
//向右查找最大的（小）元素放在最右边
for (i = left;i < right; i++)
{
if (func (num[i], num[i+1]) > 0)
swap (num, i, i+1);
}
right--;
向左查找最小的（大）元素放在最左边
for (i = right;i > left; i--)
{
if (func (num[i], num[i-1]) < 0)
swap (num, i, i-1);
}
left++;
}
}
//选择排序
void select_sort (int num[], int len, cmp func)
{
int i, j;
for (i = 0;i < len-1; i++) //N个数比较N-1轮
{
int index = i;
//查找最小（大）元素及其下标
for (j = i+1;j < len; j++)
{
if (func (num[index], num[j]) > 0)
//if (num[index] > num[j])
index = j;
}
if (index != i) //交换元素，将最小（大）元素换至当前最前面
{
swap (num, i, index);
}
}
}
//插入排序
void insert_sort (int num[], int len, cmp func)
{
int i, j, get;
//默认第一个元素是排好序的，取后面的元素依次比较，
//插入数列中第一个小于（大于）它的数的后面
for (i = 1;i < len; i++)
{
get = num[i]; //记录取的数
j = i-1;
while (j >= 0 && (func(num[j],get) > 0))
{
num[j+1] = num[j]; //不满足条件的元素后移
j--;
}
num[j+1] = get; //插入元素
}
}
//二分法插入排序
void dic_sort (int num[], int len, cmp func)
{
int left, right, mid, i, j, get;
for (i = 1;i < len; i++)
{
left = 0;
right = i; //开始时左右边界分别为 0、i
get = num[i];
while (left <= right)
{
mid = (left + right)/2;
if ((func(num[mid], get)) > 0) //所取元素小于中间元素，插在中间元素前面
{
right = mid - 1; //右边界改变
}
else //否则插在中间元素后面
{
left = mid + 1; //左边界改变
}
}
for (j = i-1;j >= left; j--)
{
num[j+1] = num[j]; //插入位置后的元素后移
}
num[left] = get; //元素插入队列
}
}
//希尔排序
void shell_sort (int num[], int len, cmp func)
{
int i, j, get;
int gap = len; //步长，即每组元素间的间隔
//分组，对每组元素进行插入排序；
//缩短步长，重新分组，直至步长为1，排序结束
do
{
gap = gap/3 + 1;
for (i = gap;i < len; i++)
{
get = num[i]; //记录取的数
j = i-gap;
while (j >= 0 && (func(num[j], get) > 0))
{
num[j+gap] = num[j]; //不满足条件的元素后移
j -= gap;
}
num[j+gap] = get;} //插入元素
}while (gap > 1);
}
//堆调整
//i 是需要调整的堆结点
void heapify (int num[], int i, int len, cmp func)
{
int left = 2*i + 1; //左结点
int right = 2*i + 2; //右结点
int max = i;
//找元素最大的结点
if (left < len && (func (num[left], num[max]) > 0))
{
max = left;
}
if (right < len && (func (num[right], num[max]) > 0))
{
max = right;
}
//最大结点与其根结点交换
if (max != i)
{
swap (num, max, i);
heapify (num, max, len, func); //调整交换的结点
}
}
//堆排序
void heap_sort (int num[], int len, cmp func)
{
int i;
for (i = (len/2 - 1); i >= 0; i--)
{
heapify (num, i, len, func); //建立堆
}
//根结点与最后一个结点交换，移除最后结点，调整堆
for (i = len - 1;i > 0; i--)
{
swap (num, i, 0);
len --;
heapify (num, 0, len, func);
}
}
//归并
/*
用递归方式将数组分成两部分，排序后合并
tmp 用于存缓存数据
*/
void merge (int num[], int left, int right, int mid, int tmp[], cmp func)
{
int i = left;
int j = mid + 1;
int k = 0;
//合并两个有序的数列
while (i <= mid && j <= right) //左数组边界是mid,右数组边界是right
{
if (func (num[i], num[j]) > 0)
{
tmp[k++] = num[j++];
}
else
{
tmp[k++] = num[i++];
}
}
while (i <= mid)
{
tmp[k++] = num[i++];
}
while (j <= right)
{
tmp[k++] = num[j++];
}
k = 0;
//将参数传给原数组
for (i = left;i <= right; i++)
{
num[i] = tmp[k++];
}
}
//归并排序
void merge_sort (int num[], int left, int right, int tmp[], cmp func)
{
if (left >= right) //递归退出条件
return ;
int mid = (left + right) / 2;
merge_sort (num, left, mid, tmp, func); //递归左数组
merge_sort (num, mid + 1, right, tmp, func); //递归右数组
merge (num, left, right, mid, tmp, func); //合并左右数组
}
//分区
int partition (int num[], int left, int right, cmp func)
{
int pivot = num[right]; //选右边界的元素作为基准值
int index = left;
int i;
for (i = left;i < right; i++)
{
if (func (num[i], pivot) < 0)
{
swap (num, i, index); //将小于基准值的元素移至数组前端
index ++;
}
}
swap (num, index, right); //用基准值分割数组
return index; //返回基准值位置
}
//快速排序
void quick_sort (int num[], int left, int right, cmp func)
{
if (left < right)
{
int pivot = partition (num, left, right, func);
quick_sort (num, left, pivot-1, func); //递归左右数组
quick_sort (num, pivot+1, right, func);
}
}
int main ()
{
int num[10] = {4,7,1,3,5,0,9,2,8,6};
int len = sizeof(num)/sizeof(num[0]);
printf ("排序前 ：");
printA (num, len);
/**/
printf (" 冒泡排序\n");
printf ("升序 ：");
bubble_sort (num, len, cmp_up); //cmp_down()函数当参数传入
printA (num, len);
printf ("降序 ：");
bubble_sort (num, len, cmp_down);
printA (num, len);
/***/
printf (" 鸡尾酒排序\n");
printf ("升序 ：");
cocktail_sort (num, len, cmp_up);
printA (num, len);
printf ("降序 ：");
cocktail_sort (num, len, cmp_down);
printA (num, len);
/**/
printf (" 选择排序\n");
printf ("升序 ：");
select_sort (num, len, cmp_up);
printA (num, len);
printf ("降序 ：");
select_sort (num, len, cmp_down);
printA (num, len);
/**/
printf (" 插入排序\n");
printf ("升序 ：");
insert_sort (num, len, cmp_up);
printA (num, len);
printf ("降序 ：");
insert_sort(num, len, cmp_down);
printA (num, len);
/**/
printf (" 二分法插入排序\n");
printf ("升序 ：");
dic_sort (num, len, cmp_up);
printA (num, len);
printf ("降序 ：");
dic_sort (num, len, cmp_down);
printA (num, len);
printf (" 希尔排序\n");
printf ("升序 ：");
shell_sort (num, len, cmp_up);
printA (num, len);
printf ("降序 ：");
shell_sort(num, len, cmp_down);
printA (num, len);
/**/
printf (" 堆排序\n");
printf ("升序 ：");
heap_sort (num, len, cmp_up);
printA (num, len);
printf ("降序 ：");
heap_sort(num, len, cmp_down);
printA (num, len);
/**/
int tmp[10];
printf (" 归并排序\n");
printf ("升序 ：");
merge_sort (num, 0, len-1, tmp, cmp_up);
printA (num, len);
printf ("降序 ：");
merge_sort (num, 0, len-1, tmp, cmp_down);
printA (num, len);
/**/
printf (" 快速排序\n");
printf ("升序 ：");
quick_sort (num, 0, len-1, cmp_up);
printA (num, len);
printf ("降序 ：");
quick_sort (num, 0, len-1, cmp_down);
printA (num, len);
return 0;
}
谢谢，请多支持！
