首页 > 编程语言 > 详细

排序算法

时间:2015-05-16 13:13:29      阅读:289      评论:0      收藏:0      [点我收藏+]

因为排序算法中常需要交换数组中的元素,这里定义方法swap(int a,int b,int[] A),其中a,b为要交换的数组元素下标。

public void swap(int a,int b,int[] A){
  int temp = A[a];
  A[a] = A[b];
  A[b] = temp;
}

1 简单选择排序

public void selectSort(int[] A)
{
  int small;
  for(int i =0;i<A.length-1;i++)
  {   

     small = i;
     for(int j =i+1;j<A.length;j++)
    {
      if(A[small]>A[j]) small = j;
    }
    swap(small,i,A);
  }
}

2 插入排序

public void insertSort(int[] A)
{
  for(int i =1;i<A.length;i++)
  {
    int j = i;
    int temp =A[i];
    while(j>0&&temp<A[j-1]){
    A[j] = A[j-1];j--;
    }
    A[j] = temp;
  }
}

3 冒泡排序

public void bubbleSort(int[] A)
{
  int last,i = A.length-1,j;
  while(i>0)
  {
    last = 0;
    for(j =0;j<i;j++)
    {
      if(A[j+1]<A[j]){
      swap(j,j+1,A);
      }
      last = j;
    }
    i = last;
  }
}

4 快速排序

public void quickSort(int[] A){

     /*Random r = new Random();
            int a = r.nextInt(3);
            swap(0,a,A);

         */
  quick(0,A.length-1,A);
}
public void quick(int low,int high,int[] A){
  if(low>=high) return;
  int i = low+1;int j = high;
  while(i<j){
    while(A[i]<A[low]) i++;
    while(A[j]>A[low]) j--;
    if(i<j) swap(i,j,A);
    }
  swap(j,low,A);
  quick(low,j-1,A);
  quick(j+1,high,A);
}

5 两路合并排序

public void Merge(int[] A,int low1,int low2,int high2)
{
  int[] temp = new int[high2-low1+1];
  int i = low1,j = low2,k=0;
  while(i<=low2-1&&j<=high2)
  {
    if(A[i]<=A[j]) temp[k++] = A[i++];
    else temp[k++] = A[j++];
  }
  while(i<=low2-1) temp[k++] = A[i++];
  while(j<=high2) temp[k++] = A[j++];
  for(i=0;i<k;i++) A[low1++] = temp[i];
}
public void MergeSort(int[] A)
{
  int low1,low2,high2;
  int size = 1, len = A.length;
  while(size<len)
  {
    low1 = 0;
    while(low1+size<len)
    {
      low2 = low1 + size;
      if(low2+size>len)
      high2 = len-1;
      else high2 = low2+size-1;
      Merge(A,low1,low2,high2);
      low1 = high2+1;
    }
    size*=2;
  }
}

6  堆排序

public void adjustDown(int[] A,int start,int end)
{
  int child = 2*start + 1;int temp = A[start];
  while(child<=end)
  {
    if((child<end)&&(A[child]<A[child+1])) child++;
    if(temp>=A[child]) break;
    else{
      A[(child-1)/2] = A[child];
      child = child*2+1;
    }
  }
  A[(child-1)/2] = temp;
}
public void headSort(int[] A)
{

   int len = A.length;
  for(int i = (len-2)/2;i>-1;i--) adjustDown(A,i,len-1);
  for(int i = len-1;i>0;i--)
  {
    swap(0,i,A);
    adjustDown(A,0,i-1);
  }
}

public static void main(String[] args) {
// TODO Auto-generated method stub
  sort s = new sort();
  int[] A = new int[]{48,36,68,1,12,48,02};
  s.headSort(A);
  for(int a:A) System.out.print(a+" ");
}

时间复杂度:    最好           最坏         平均           稳定性           空间复杂度

简单选择排序   O(n2)         O(n2)      O(n2)          不稳定             O(1)

插入排序        O(n)           O(n2)      O(n2)           稳定               O(1)

冒泡排序        O(n)           O(n2)      O(n2)           稳定               O(1)

快速排序        O(nlg2n)     O(n2)      O(lg2n)         不稳定            O(lg2n) (最坏情况下为O(n))

两路合并排序   O(nlg2n)    O(nlg2n)   O(nlg2n)       稳定              O(n)

堆排序           O(nlg2n)     O(nlg2n)   O(nlg2n)       不稳定           O(1)

注:快速排序时为了预防最坏情况,即数组有序,可以采用随机选择主元的方法。注释部分即为随机选择主元。

 

排序算法

原文:http://www.cnblogs.com/moxia1234/p/4507634.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!