C语言排序与查找笔记

powerwind

一，选择排序。
选择排序的思想是每次都取一个最大（小）的放在第（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[m]>a[k])
                        {
                                m=k;
                        }
                        if (m!=j)
                        {
                                temp=a[j];
                                a[j]=a[m];
                                a[m]=temp;
                        }
        }
}

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

        int j=0;
        int a[10];
        printf("排序前:\n");
        for (j=0;j<10;j++)
        {
                a[j]=rand();
                printf("%d,",a[j]);
        }
        choose_sort(a,10);
        printf("\n排序后:\n");
        for(j=0;j<10;j++)
                printf("%d,",a[j]);
        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[pos1];
        a[pos1]=a[pos2];
        a[pos2]=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[k],a[m]))m=k;
                if(m!=j)
                        swap(a,m,j);

        }

}

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

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

powerwind

一般的插入排序算法

#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[j]);

}
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[j];
                for (k=j-1;k>=0;k--)
                {
                      /*直到找出比temp(大)小的元素,然后要把temp插到该元素前面*/
                        if(compare_lower(a[k],temp))break;
                     /*向后移动*/
                        a[k+1]=a[k];
                        if(DEBUG)print(a,len);
                }
                if(temp!=a[k+1])a[k+1]=temp;
                if(DEBUG)print(a,len);

        }
}

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

        int j=0;
        int a[10];
        printf("排序前:\n");
        for (j=0;j<10;j++)
        {
                a[j]=rand();
                printf("%d,",a[j]);
        }
        insert_sort(a,10);
        printf("\n排序后:\n");
        for(j=0;j<10;j++)
                printf("%d,",a[j]);
        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[mid]==e)return 1;
         else if(e>a[mid])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[j];
                low=0;
                high=j-1;
                /*在low与high之间,查找合适位置*/
                while (low<=high)
                {
                        mid=(low+high)/2;
                        /*如果要插入的元素比较大,则到右边找*/
                        if(temp>a[mid])low=mid+1;
                        /*否则在左边找*/
                        else high=mid-1;
                }
                /*移动元素到后面*/
                for (k=j-1;k>=low;k--)
                {
                        a[k+1]=a[k];
                }
                a[low]=temp;
        }
}

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

/*
* 希尔排序
* 原理:一种分组插入排序方法.先取定一个小于序列长度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[j];
               /* k>=0且a[k]大于temp,则移动元素 */
              for (k=j-m;k>=0&&a[k]>temp;k-=m)
               {
                    a[k+m]=a[k];
               }
               /* 插入到合适位置 */
               a[k+m]=temp;
          }
           m/=2;
     }
}

据说 m=3*m+1 的增量效率不错.

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

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

powerwind

三,交换排序

1,简单经典的冒泡排序

1. void bubble_sort(int *a,int len)
   
2. {
   
3.      int j,k;
   
4.      int temp;
   
5.      int change=1;
   
6.      for (j=0;(j<len-1)&&change;j++)
   
7.      {
   
8.          change=0;
   
9.          for (k=j+1;k<len;k++)
   
10.          {
    
11.              if (a[k-1]>a[k])
    
12.              {
    
13.                 change=1;
    
14.                 temp=a[k-1];
    
15.                 a[k-1]=a[k];
    
16.                 a[k]=temp;
    
17.              }
    
18.          }
    
19.      }
    
20. }

复制代码

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