学步园

对于n < 20,插入排序是比快速,堆,归并更快的排序算法.

对于整数数组排序,示例程序如下:

#include <stdio.h>

void sort(int *array, int n)
{
 //下标
 int i, j;

 //暂存待排序元素
 int tmp;

 for(i = 1; i < n; i++)
 {
  tmp = array[i];
  j = i - 1;
  //寻找插入位置
  while(j >= 0 && array[j] > tmp)
  {
   array[j + 1] = array[j];
   j--;
  }
  array[j + 1] = tmp;
 }
}

//打印数组元素
void print(int *array, int n)
{
 for(int i = 0; i < n; i++)
 {
  printf("%d/t", array[i]);
 }
}

void main()
{
 int a[] = {1, 3, 5, 8, 9, 4, 6, 7, 2};
 sort(a, sizeof(a) / sizeof(int));
 print(a, sizeof(a) / sizeof(int));
}

如何对任意类型的数组排序?

系统提供了qsort函数,原型如下:

_CRTIMP void   __cdecl qsort(void *, size_t, size_t, int (__cdecl *)
        (const void *, const void *));

代码略.

 今天老师讲了一下，这里把代码贴一贴。
#include <stdio.h>
#include <memory.h>
#include <stdlib.h>
#include <malloc.h>
#include <string.h>

void sort_general(void *array, int n, int w, int (*c)(void *, void *))
{
//下标
int i, j;

char *x;
x = (char *)malloc(w);

for(i = 1; i < n; i++)
{
memmove(x, (char *)array + i * w, w);

j = i - 1;
//寻找插入位置
while(j >= 0 && (*c)((char *)array + j * w, x))
{
memmove((char *)array + (j + 1) * w, (char *)array + j * w, w);
j--;
}
memmove((char *)array + (j +1) * w, x, w);
}
}

int greater(void *p, void *q)
{
int *pp, *qq;
pp = (int *)p;
qq = (int *)q;
return (*pp) > (*qq);
}

//打印数组元素
void print(int *array, int n)
{
int i = 0;
for( i = 0; i < n; i++)
{
printf("%d/t", array[i]);
}
}

/*
* 指针数组:一个数组,每个元素都是指针
*/
int buildeDic(char *dic, char *pointer[])
{
printf("please input words, space by tab, ends with #./n");

int num = 0;
pointer[0] = dic;

while(1)
{
*dic = getchar();
if('a' <= *dic && 'z' >= *dic)
{
dic++;
continue;
}
if(*dic == ' ')
{
*dic ++ = '/0';
num++;
pointer[num] = dic;
}else{
*dic = '/0';
num++;
return num;
}
}
}

int greater_str(void *p, void *q)
{
char **pp = (char **)p;
char **qq = (char **)q;
return strcmp(*pp, *qq) > 0;
}

void main()
{
int a[] = {1, 3, 5, 8, 9, 4, 6, 7, 2};
sort_general(a, sizeof(a) / sizeof(int), sizeof(int), greater);
print(a, sizeof(a) / sizeof(int));
printf("/n");

/*
* 指针数组
*/
char dic[1000];
char *dic_pointer[100];
int num = buildeDic(dic, dic_pointer);

sort_general(dic_pointer, num, sizeof(char *), greater_str);
for(int j = 0; j < num; j++)
printf("%s/t", dic_pointer[j]);

}