C语言排序与查找笔记-|两个,位置,思想,数组,版本|【编程】编程圣殿|工大后院

powerwind 发表于 2006-9-15 00:14

C语言排序与查找笔记

一，选择排序。
选择排序的思想是每次都取一个最大（小）的放在第（i）个位置，第一次是放在第一个位置，第二次就放在第二个位置。。。。。。N个要排序就排序N-1次。
#include<stdio.h>

/*
*选择排序
*/

void choose_sort(int *a,int n)
{
int j=0,k=0,m=0;
int temp;
for (j=0;j<n-1;j++)
{
m=j;
for (k=j+1;k<n;k++)
if (a>a)
{
m=k;
}
if (m!=j)
{
temp=a;
a=a;
a=temp;
}
}
}

int main()
{
srand(time(NULL));

int j=0;
int a;
printf("排序前:\n");
for (j=0;j<10;j++)
{
a=rand();
printf("%d,",a);
}
choose_sort(a,10);
printf("\n排序后:\n");
for(j=0;j<10;j++)
printf("%d,",a);
system("pause");
return 0;
}

另一版本.

#include<stdio.h>

typedef int Type;
typedef enum boolean{false,true}boolean;

/*
* 交换两个位置元素的值
*/
void swap(Type*a,int pos1,int pos2)
{
Type temp=a;
a=a;
a=temp;
}
/** a<b则返回真 **/
boolean compare_lower(Type a,Type b)
{
if(a<b)return true;
return false;
}
/*
* 选择排序
* 参数:数组a,其长度len
*/
void select_sort(Type*a,int len)
{
int j,k,m;
for (j=0;j<len-1;j++)
{
m=j;
for (k=j+1;k<len;k++)
if(compare_lower(a,a))m=k;
if(m!=j)
swap(a,m,j);

}

}
其实两个版本是完全一样的思想,只是第二种写法,我觉得比较好.

[ 本帖最后由 powerwind 于 2006-9-16 19:08 编辑 ]

powerwind 发表于 2006-9-16 19:25

二、插入排序

一般的插入排序算法

#include<stdio.h>
#define DEBUG 0
/*为了看排序的过程,定义print输出数组*/
void print(int a[],int n)
{
int j;
printf("\n");
for(j=0;j<n;j++)printf("%d-",a);

}
typedef int Type;
typedef enum boolean{false,true}boolean;

/*
*一般的插入排序算法
*/

/*
*思想:往一个有序的序列按顺序插入一个元素,结果仍是一个有序的序列.
*
**/

/** a<=b则返回真 **/
boolean compare_lower(Type a,Type b)
{
if(a<=b)return true;
return false;
}
/** a>=b则返回真 **/
boolean compare_larger(Type a,Type b)
{
if(a>=b)return true;
return false;
}
void insert_sort(Type*a,int len)
{
int j=0,k=0,m=0;
Type temp;
for (j=1;j<len;j++)
{
temp=a;
for (k=j-1;k>=0;k--)
{
               /*直到找出比temp(大)小的元素,然后要把temp插到该元素前面*/
if(compare_lower(a,temp))break;
            /*向后移动*/
a=a;
if(DEBUG)print(a,len);
}
if(temp!=a)a=temp;
if(DEBUG)print(a,len);

}
}

int main()
{
srand(time(NULL));

int j=0;
int a;
printf("排序前:\n");
for (j=0;j<10;j++)
{
a=rand();
printf("%d,",a);
}
insert_sort(a,10);
printf("\n排序后:\n");
for(j=0;j<10;j++)
printf("%d,",a);
system("pause");
return 0;
}

在链表中实现一般插入排序

#include<stdio.h>

typedef int Type;

/*
*
*一般的插入排序算法--链表实现
*
*/

typedef struct myList{
Type elem;
struct myList *pre;
struct myList *next;
}m_List,*List;

const int LEN=sizeof(m_List);

/*
*
* 给定长度初始化链表,并返回表头指针
*
**/

List init(int len)
{
if(len<1)return NULL;
int j=0;

List head=malloc(LEN);
List temp=malloc(LEN);
head->next=temp;
temp->pre=head;
temp->next=NULL;
srand(time(NULL));
temp->elem=rand();
for (j=1;j<len;j++)
{
temp->next=malloc(LEN);
temp->next->elem=rand();
temp->next->pre=temp;
temp=temp->next;
}
temp->next=NULL;
return head;
}
/* 插入排序 */
void insert_sort(List head)
{
if(head->next==NULL)return;
List unsort_head=head->next;
List current;
List temp;
for (;unsort_head!=NULL;unsort_head=unsort_head->next)
{
current=unsort_head;
temp=head->next;
/*从左开始至当前(current)元素,找出比current大的元素,然后插到该元素前面*/

while (temp->elem<current->elem&&temp!=current) /*比current小,移动下一个*/
{
/*向后移动*/
temp=temp->next;
}
if (temp!=current)
{
/*先拆开*/
current->pre->next=current->next;
if (current->next!=NULL)current->next->pre=current->pre;
/*插入到合适位置*/
temp->pre->next=current;
current->pre=temp->pre;
current->next=temp;
temp->pre=current;
}
}
}

在实现折半插入排序之前,要先看看折半查找的实现.

int bin_search(int*a,int len,int e)
{
int low,mid,high;
low=0;
high=len;
while (low<=high)
{
      mid=(low+high)/2;
      if(a==e)return 1;
      else if(e>a)low=mid+1;
      else high=mid-1;
}
return 0;
}

折半插入排序

/*
*
* 二分折半查找
*
**/
void bin_insert_sort(int*a,int len)
{
int low,mid,high,j,k;
int temp;
for (j=1;j<len;j++)
{
temp=a;
low=0;
high=j-1;
/*在low与high之间,查找合适位置*/
while (low<=high)
{
mid=(low+high)/2;
/*如果要插入的元素比较大,则到右边找*/
if(temp>a)low=mid+1;
/*否则在左边找*/
else high=mid-1;
}
/*移动元素到后面*/
for (k=j-1;k>=low;k--)
{
a=a;
}
a=temp;
}
}

希尔排序
http://student.zjzk.cn/course_ware/data_structure/web/flash/px/1.swf

/*
* 希尔排序
* 原理:一种分组插入排序方法.先取定一个小于序列长度n的整数m作为第一个增量,
* 把表的全部记录分成?个组
* 所有距离为m的倍数的记录放在同一个组中,在各组内进行直接插入排序(插入交换);
* 然后取第二个增量m/2,重复到所有记录放在同一组.
*/

void shell_sort(int *a,int len)
{
int j,k,m;
int temp;
/* m:表示相隔m为一组 */
m=len/2;
/* 分组数不为1,则继续循环 */
while (m>0)
{
      /* j: */
      for (j=m;j<len;j++)
      {
            temp=a;
         /* k>=0且a大于temp,则移动元素 */
         for (k=j-m;k>=0&&a>temp;k-=m)
            {
               a=a;
            }
         /* 插入到合适位置 */
            a=temp;
      }
      m/=2;
}
}
据说 m=3*m+1 的增量效率不错.

void shell_sort(int *a,int len)
{
int j,k,m,n;
int temp;
int increaments;
/* 先把增量存放在数组中 */
for (j=0,m=1;m<len;j++)
{
      increaments=m;
      m=3*m+1;
}
/* j 确定了增量数组个数 */
for (j--;j>=0;j--)
{
      m=increaments;
      for (k=m;k<len;k++)
      {
            temp=a;
            /* n>=0且a大于temp,移动元素 */
            for (n=k-m;n>=0&&a>temp;n-=m)
            {
               a=a;
            }
            a=temp;
      }
}
}

[ 本帖最后由 powerwind 于 2006-9-19 13:21 编辑 ]

powerwind 发表于 2006-9-18 17:16

三,交换排序

1,简单经典的冒泡排序

void bubble_sort(int *a,int len)
{
int j,k;
int temp;
int change=1;
for (j=0;(j<len-1)&&change;j++)
{
      change=0;
      for (k=j+1;k<len;k++)
      {
         if (a>a)
         {
            change=1;
            temp=a;
            a=a;
            a=temp;
         }
      }
}
}

[ 本帖最后由 powerwind 于 2006-10-28 18:09 编辑 ]

页: [1]

工大后院's Archiver

C语言排序与查找笔记

二、插入排序