数据结构之之一： 直接插入排序 && 冒泡排序

最近研究一些算法，主要是C和java版本的算法，以供以后备用。

1，冒泡排序
  在要排序的一组数中，对当前还未排好序的范围内的全部数，自上
 而下对相邻的两个数依次进行比较和调整，让较大的数往下沉，较
 小的往上冒。即：每当两相邻的数比较后发现它们的排序与排序要
 求相反时，就将它们互换。

java 代码：

 

public class BulueTest {
    public BulueTest() {
    }


    public void sort(int[] a, int len )
    {
        for(int i=len-1;i>=0;i--)
        {
            for(int j=0;j<i;j++)
            {
                if(a[j]>a[j+1])
                {
                    int tmp = a[j];
                    a[j] = a[j+1] ;
                    a[j+1] =tmp ;
                }
            }
        }
        print(a) ;
    }

    public void sort1(int a[], int len)
    {
        for(int i=0;i<a.length;i++)
        {
            for(int j=a.length-1;j>i;j--)
            {
                if(a[j-1]>a[j])
                {
                    int tmp = a[j];
                    a[j] = a[j-1] ;
                    a[j-1] =tmp ;

                }
            }
        }
        print(a) ;
    }
    public void print(int a[])
    {
        System.out.println("----------buble----");
        for(int i=0;i<a.length;i++)
        {
            System.out.print("  "+a[i]+"\t");
        }
    }

    public static void main(String[] args) {
        BulueTest buluetest = new BulueTest();
      int[] x = new int[]{33,4,22,5,6,9,8,7,6,2,1};
        buluetest.sort1(x,x.length);
       }

}

 

 

C代码：

 

#include <stdio.h>

void print_f(int* a , int len) ;
void bublesort(int* a, int len) ;

 

int main(int argv,char* args[])
{
 int a[] = {22,33,1,2,3,44,2,33,45,13,12};
 bublesort(a,sizeof(a) / sizeof(a[0])) ;

}

void bublesort(int* a, int len)
{
 int i , j ;

 for(i = len-1;i>0;i--)
 {
  for(j = 0;j<i;j++)
  {
   if(a[j]>a[j+1])
   {
    int tmp = a[j] ;
    a[j] = a[j+1] ;
    a[j+1] =tmp ;
   }
  }
 }
 print_f(a,len) ;
}

void print_f(int* a , int len)
{
 int i ;
 for(i = 0;i<len ;i++)
 {
  printf("  %d \t" , *(a+i));
 }

}

 

 

 

2，直接插入排序
算法思想简单描述：

 在要排序的一组数中，假设前面(n-1) [n>=2] 个数已经是排
 好顺序的，现在要把第n个数插到前面的有序数中，使得这n个数
 也是排好顺序的。如此反复循环，直到全部排好顺序。
java 代码：

public class InsertSort 
{

 public void sort(int a[] , int len)
 {
  
  int key ;
     int j  ;
  for(int i=1;i<len;i++)
  {
   key = a[i];
   for( j=i-1;j>=0 ;j--)
   {
      if(a[j] >key)
       a[j+1] =a[j] ;
      else
      
       break;      // 这里不能用另一个变量来记录j 的下标，当j变到 -1 时，就取不到值
     
     
   }
   
   a[j+1] =key ;

   
  }
  
  print(a) ;
 }
 
 public void print( int a[])
 {
  for(int i=0;i<a.length;i++)
  {
   System.out.print(a[i]+"\t");
  }
  
  
 }
 public static void main(String args[])
 {
  InsertSort is = new InsertSort();
  int a[] =new int[]{3,4,7878,67,5,1,2,33,12,31};
  is.sort(a, a.length) ;
  
 }
 
 
  public static void insertSort(int[] a){   
         int j;   
            
         for(int p = 1; p < a.length; p++){   
                
             int temp = a[p];   
             for(j = p-1; (j >= 0) && (temp < a[j]); j--)
             {   
              
                 a[j+1] = a[j];   
             }   
             a[j+1] = temp;   
         }   
            
     }   
        
//     public static void main(String[] args){   
//         int[] b = {9,8,5,2,1,7,3,4,8888,43,23525,232,12,34,53,75,13,15,17};   
//         insertSort(b);   
//         for(int i = 0; i < b.length; i++)   
//             System.out.print(b[i] + " , ");   
//     }   

}

 

 

C代码：

 

 

InsertSort.h :



#ifndef INSERTSORT_H_
#define INSERTSORT_H_

void printf1(int a[]) ;
void insertSort(int a[] , int len) ;
int  getLength(int a[]) ;

#endif /* INSERTSORT_H_ */

 

 

 

InsertSort.C :

 

/*
 * InsertSort.c
 *
 *  Created on: 2010-11-1
 *      Author: Administrator
 */
#include <stdio.h>

#include "InsertSort.h"

nt main(int argv,char* args[])
{
 printf("this is Insert Sort...\n") ;
 int a[] = {33,22,11,234,45,643,2,3,4,56,32,1};
 printf("a.length ===== %d, \n " , getLength(a)) ;
int len =  sizeof(a) /sizeof(a[0])  ;  // 48 / 4 == 12 ;
insertSort(a,  len) ;
return 0 ;
}

 

int  getLength(int* a)  // 只是传了一个地址的长度，后面暂没传过来
{                      /////  数组作为函数参数，作用类似指针。 函数只传递一个4字节的地址
                          ///  ，而没有其大小信息。

 int len = 0 ;

 //printf(sizeof(a)) ;
 ///printf( sizeof(a[0]) )  ;
 int s =sizeof(a) ;    ///   == 1
 int l = sizeof(*a) ;   ////  == 1 ;
 len =   s / l ;

 return len ;
}

void insertSort(int a[] , int len)
{
 int key ;
 int j ;
 int i ;
 for(i = 1;i<len;i++)
 {
  key = a[i] ;
  for(j = i-1;j>=0;j--)
  {
   if(key <a[j])
    a[j+1]=a[j] ;
   else
    break ;
  }
  a[j+1] = key ;

 }
 printf1(a) ;
}

void printf1(int* a)
{
 int i ;
 for(i = 0 ;i<12;i++)
 {
  printf("%d \t" ,a[i]) ;
 }
}