找回密码
 注册
搜索
热搜: java php web
查看: 3130|回复: 16

几种排序算法

[复制链接]
发表于 2009-1-25 18:06:18 | 显示全部楼层 |阅读模式
归并、冒泡、选择、快速、计数、基数
复制内容到剪贴板
代码:
using   System;
using   System.Collections.Generic;
using   System.Text;
using   System.Collections;

namespace   Sort
{
public   class   MergeSort
{
public   void   Merge(ref   int[]   aa,   int   p,   int   q,   int   r)
{
int   n1   =   q   -   p   +   1;
int   n2   =   r   -   q;
int   k   =   1,   i   =   0,   j   =   0;
int[]   l=new   int   [n1+1];
int[]   R=new   int   [n2+1];
for   (i   =   1;   i   <=   n1;   i++)
{
l   =   aa[p   +   i-1];
}
for   (i   =   1;   i   <=   n2;   i++)
{   
R=aa[q+i];
}
i   =   1;   j   =   1;   k   =   p;
while   (i <=n1   &&   j <=n2)
{
if   (l   <   R[j])   
aa[k++]   =   l[i++];
else
aa[k++]   =   R[j++];
}
if   (i   >   n1)
{
while   (j   <=   n2)
{
aa[k++]   =   R[j++];
}
}
else
{
while   (i   <=   n1)
{
aa[k++]   =   l[i++];
  }
  }
  }
public   void   Sort(ref   int[]   aa,   int   p,   int   r)
  {
if   (p   <   r)
  {
int   q   =   (p   +   r)   /   2;
Sort(ref   aa,p,q);
Sort(ref   aa,q+1,r);
Merge(ref   aa,p,q,r);
                        }
                }
        }

public   class   HeapSort
        {
public   void   MaxHeapify(ref   int[]   a,   int   i,   int   length)
      {
int   l   =   i   *   2;

int   r   =   i   *   2   +   1;
int   largest;
if   (l   <=   length   &&   a[l]   >   a)
largest   =   l;
else
largest   =   i;
if   (r   <=   length   &&   a[r]   >   a[largest])
largest   =   r;
if   (largest   !=   i)
    {
int   temp   =   a;
a   =   a[largest];
a[largest]   =   temp;
MaxHeapify(ref   a,   largest,   length);
           }
           }

public   void   BuildMaxHeap(ref   int[]   a)
           {
for   (int   i   =   a.Length   -   1;   i   > =   1;   i--)
           {
MaxHeapify(ref   a,   i,   a.Length   -   1);
                        }
                }

public   void   Sort(ref   int[]   a)
                {
BuildMaxHeap(ref   a);
for   (int   i   =   a.Length   -   1;   i   >   1;   i--)
     {
int   temp;
temp   =   a[1];
a[1]   =   a;
a   =   temp;
MaxHeapify(ref   a,   1,   i   -   1);
                        }
                }
        }

public   class   BubleSort
        {   
public   void   Sort(ref   int[]   a)
                {
int   n=a.Length-1;
for   (int   i   =   1;   i   <   n;   i++)
     {
for   (int   j   =   1;   j   <=   n   -   i;   j++)
                                {
if   (a[j+1]   >   a[j])
                                        {
int   temp   =   a[j];
a[j]   =   a[j   +   1];
a[j   +   1]   =   temp;
                                        }
                                }
                        }
                }
        }

public   class   SelectSort
        {
public   void   Sort(ref   int[]   a)
                {   
int   n=a.Length-1;
int   max;
int   maxIndex;
for   (int   i   =   1;   i   <   n;   i++)
    {
max   =   a;
maxIndex   =   i;
for   (int   j   =   i+1;   j   <=   n;   j++)
      {
if   (a[j]   >   max)
  {
max   =   a[j];   maxIndex   =   j;
           }
         }
if   (maxIndex   !=   i)
                                {
a[maxIndex]   =   a;
a   =   max;
                                }
                        }
                }
        }

public   class   QuickSort
    {
Random   rd   =   new   Random();
public   delegate   int   Partion(int[]   a,int   p,int   r);
public   void   QSort(ref   int[]   a,int   p,int   r,Partion   partition)
                {
if   (p   <   r)
                        {
int   q   =   partition(a,p,r);
QSort(ref   a,p,q-1,partition);
QSort(ref   a,   q   +   1,   r,partition);
                        }
                }

private   void   QSort(ref   int[]   a,   int   p,   int   p_3)
                {
throw   new   Exception( "The   method   or   operation   is   not   implemented. ");
                }
public   int   PartitionSingle(int[]   a,   int   p,   int   r)
                {
int   i   =   rd.Next(p,   r);
int   temp   =   a;
a   =   a[r];   a[r]   =   temp;
int   x   =   a[r];
i   =   p   -   1;
for   (int   j   =   p;   j   <   r;   j++)
   {
if   (a[j]   <   x)
     {
i++;
temp   =   a;   a   =   a[j];   a[j]   =   temp;
       }
       }
temp   =   a[i   +   1];   a[i   +   1]   =   a[r];   a[r]   =   temp;
return   i   +   1;
                }
public   int   PartitionDouble(int[]   a,   int   p,   int   r)
                {
int   i=rd.Next(p,   r);
int   temp   =   a;
a   =   a[r];   a[r]   =   temp;
int   x   =   a[r];
while   (p   <   r)
    {
while   (p   <   r   &&   a[p]   <=   x)   p++;
if   (p   <   r)
     {
a[r]   =   a[p];   r--;
    }
while   (p   <   r   &&   a[r]   > =   x)   r--;
if   (p   <   r)
{
a[p]   =   a[r];   p++;
     }
     }
a[p]   =   x;
return   p;
    }
public   void   Sort(ref   int[]   a)
    {
Console.Write( "pleale   select   partition   of   method:   1   is   single   and   2   is   double> ");
int   userInput   =   Convert.ToInt32(Console.ReadLine());
if   (userInput   ==   1)
QSort(ref   a,   1,   a.Length   -   1,   PartitionSingle);
else   if   (userInput   ==   2)
QSort(ref   a,   1,   a.Length   -   1,   PartitionDouble);
                }
        }
public   class   CountSort
        {
public   void   Sort(ref   int[]   a)
                {   
int   n=a.Length-1;
int   max   =   a[1];
for   (int   i   =   2;   i   <=   n;   i++)
      {
if   (a   >   max)   max   =   a;
      }
int[]   c   =   new   int[max+1];
for   (int   i   =   1;   i   <=   n;   i++)
      {
c[a]++;
      }
for   (int   i   =   2;   i   <=   max;   i++)
      {
c   =   c   +   c[i   -   1];
      }
int[]   b   =   new   int[n   +   1];
for   (int   i   =   1;   i   <=   n;   i++)
    {
b[c[a]]   =   a;
c[a]--;
     }
for   (int   i   =   1;   i   <=   n;   i++)
   {
a   =   b;
                        }
                }
        }
public   class   BaseSort
        {
int   max=0;
void   MaxLength(int[]   a)
                {   
for(int   i=0;i <a.Length;i++)
                        {
int   n=1;
for   (int   j   =   10;   a   /   j   !=   0;   j   *=   10)
n++;
if   (n   >   max)   max   =   n;
                        }               
                }
int   GetDit(int   x,int   i)
                {
int   n;
n   =   x;
for   (int   m   =   1;   m   <=   i;   m++)
n   /=   10;
n   %=   10;
return   n;
                }
public   void   Sort(ref   int[]   a)
                {
ArrayList[]   digit   =   new   ArrayList[10];
for   (int   i   =   0;   i   <10;   i++)
digit   =   new   ArrayList();

MaxLength(a);
for   (int   i   =   0;   i   <   max;   i++)
     {
for(int   j=0;j <a.Length;j++)
                                {
int   n;
n   =   GetDit(a[j],i);
digit[n].Add(a[j]);
       }
int   k=0;
for   (int   t   =   0;   t   <   10;   t++)
                                {
if   (digit[t].Count   ==   0)   continue;
foreach   (object   obj   in   digit[t])
           {
a[k++]   =   (int)obj;
         }
         }
for   (int   j   =   0;   j   <   digit.Length;   j++)
digit[j].Clear();
              }
  
                }
        }
}
发表于 2009-1-25 19:15:35 | 显示全部楼层
学习学习
回复

使用道具 举报

发表于 2009-1-25 19:11:44 | 显示全部楼层
呵呵,路过,应该学习学习!
回复

使用道具 举报

发表于 2009-1-25 18:37:15 | 显示全部楼层
最好再加上堆排序,呵呵
回复

使用道具 举报

发表于 2009-1-25 19:45:24 | 显示全部楼层
谢谢
回复

使用道具 举报

发表于 2009-1-25 19:41:36 | 显示全部楼层
学习!!学习!!
回复

使用道具 举报

发表于 2009-1-25 19:33:23 | 显示全部楼层
回复

使用道具 举报

发表于 2010-3-18 16:46:03 | 显示全部楼层
学习中 谢谢
回复

使用道具 举报

发表于 2010-5-30 01:50:39 | 显示全部楼层
算法的java实现
回复

使用道具 举报

发表于 2010-6-28 16:10:43 | 显示全部楼层
这好像使用Java语言写 的吧。看到好像不想c++语法
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册

本版积分规则

Archiver|手机版|小黑屋|软晨网(RuanChen.com)

GMT+8, 2024-11-22 18:14

Powered by Discuz! X3.5

Copyright © 2001-2023 Tencent Cloud.

快速回复 返回顶部 返回列表