算法之简单排序

一。直接插入排序
1。直接插入排序：直接插入排序是一种简单的排序方法，它的基本思想是将待排序的记录按照其值的大小插入到已排好序的有序表的适当位置，直到全部插入完为止。举个整型的排序例子
2。直接插入排序的伪代码：

insertionsort(data[])
   for i=1 to data.length-1
       tmp=data[i];
       将所有大于tmp的元素data[j]向后移动一位;
       将tmp放在正确的位置上;

3.简单例子，以整型为例。
A）ruby语言实现：
 

def insertion_sort(a)
  i=1
  while i<a.length
    tmp=a[i]
    j=i
    while j>0
      break if tmp>a[j-1]
      a[j]=a[j-1]
      j-=1
    end
    a[j]=tmp
    i+=1
  end
end       
a=[10,2,3]
insertion_sort(a)
a.each{|i | print i.to_s+" "}

B）java语言实现：

package com.sohu.blog.denns_zane.sort;

public class InsertSort{
    public static void main(String args[]){
        int []data={12,2,3,56,90};
        insertsort(data);
        for(int i=0;i<data.length;i++){
            System.out.print(data[i]+" ");
        }
    }
    public static void insertsort(int []data){
        for(int i=1,j;i<data.length;i++){
            int tmp=data[i];
            for(j=i;j>0&&tmp<data[j-1];j--)
               data[j]=data[j-1];
            data[j]=tmp;   
        }
    }
}

5。算法复杂度：
最好情况：进行n-1次比较和2(n-1)次移动，尽管他们其实都是多余的，复杂度O(n)
最坏情况：具体计算略，O(n*n)
平均情况：O(n*n)，也就是接近最坏情况，在平均情况下，数组大小翻倍，它的排序工作将是原来的4倍。

二。选择排序
1。算法描述：选择算法试图先查找一个放错位置的元素并将它放到最终位置上，以此来局部化数组元素的交换。选择值最小的元素并将它和第一个位置上的元素交换。在第i步中，查找data[i],...,data[n-1]中的最小元素，并将它和data[i]进行交换。重复此过程，直到所有的元素都放入正确的位置为止。

2。伪代码描述：

selectionsort(data[])
     for i=0 to data.length-2
        从data[i],,data[n-1]中选取最小的元素
        将它和data[i]交换

 
3。实现，以整型数组为例：
1)ruby语言实现：

def selection_sort(a)
  least=0
  for i in (0..(a.length-2))
    j=i+1
    least=i
    while j<a.length
      if a[j]<a[least]
        least=j
      end
      j+=1  
    end
    a[least],a[i]=a[i],a[least] unless least==i #交换
  end
end
a=[12,4,34,23,45,35]
selection_sort(a)
a.each{|i| print i.to_s+" "}

代码很好理解，不做解释。

2）java语言实现：

package com.sohu.blog.denns_zane.sort;

public class SelectionSort{
    public static int[] selection_sort(int [] data){
        int i,j,least=0;
        for(i=0;i<data.length-1;i++){
        
          for(j=i+1,least=i;j<data.length;j++)
            if (data[j]<=data[least])
                    least=j;
          if (least!=i)
            swap(data,least,i);  //½»»»data[i]ºÍ×îСԪËØ
        }    
        return data;   
    }
    public static void swap(int[]data,int least,int i){
        int tmp=data[least];
        data[least]=data[i];
        data[i]=tmp;
    }
    public static void main(String args[]){
        int[] t={10,29,12,23,56};
        selection_sort(t);
        for(int i:t){
            System.out.print(i+" ");
        } 
    }
}

4.算法效率：
任何情况下，都需要进行n*(n-1)/2次比较，也就是O(n*n)的复杂度
最好情况：数组已经排序，不需要交换任何元素
最坏情况：最大元素在第一个位置而其他元素有序时，需要进行3*(n-1)次交换，即O(n)，也是很好的结果

三。冒泡排序
1。算法伪代码描述：

bubblesort(data[])
  for i=0 to data.length-2
     for j=data.length-1 downto i+1
         如果顺序错误，就交换j和j-1位置上的元素

2。实现：
1)ruby语言实现：

def bubble_sort(data)
  for i in (0..(data.length-2))
     j=data.length-1
     while j>i
        if data[j]<data[j-1]
           data[j],data[j-1]=data[j-1],data[j]   #交换
        end
        j-=1
     end
  end
end
a=[12,3,56,7,89,87]
bubble_sort(a)
a.each{|i| print i.to_s+" "}

2）java语言实现：

package com.sohu.blog.denns_zane.sort;

public class BubbleSort{
    public static void bubble_sort(int [] data){
        for(int i=0;i<data.length-1;i++)
            for(int j=data.length-1;j>i;j--)
              if(data[j]<data[j-1])
                swap(data,j,j-1);
        
    }
    public static void swap(int[]data,int least,int i){
        int tmp=data[least];
        data[least]=data[i];
        data[i]=tmp;
    }
    public static void main(String args[]){
        int[] t={10,29,12,23,56};
        bubble_sort(t);
        for(int i:t){
            System.out.print(i+" ");
        } 
    }
}

3。算法效率：
冒泡排序的比较次数近似是插入排序的两倍，和选择排序相同；移动次数和插入排序相同，是选择排序的n倍。可以说，插入排序比冒泡排序快两倍。