常用的各种排序算法的JAVA实现

 

铭铭

<!---->

2005-10-12 03:36

[转贴]常用的各种排序算法的JAVA实现

[align=center]常用的各种排序算法的JAVA实现
作者：Linyco  
[/align]  
用JAVA把《Data Structure and Algoritm Analysis in C》里面的排序算法实现了。整个结构我使用的是Strategy模式。由Sort类扮演环境角色，SortStrategy扮演抽象策略角色。具体策略角 色有六个，分别是InsertSort、BubbleSort、ChooseSort、ShellSort、MergeSort、QuickSort。分 别是插入排序、冒泡排序、选择排序、希尔排序、归并排序和快速排序。
因为代码量比较大，所以分为几次贴出，这次只贴出Sort和SortStrategy的代码。

SortStratey接口：
package Utils.Sort;
/**
*排序算法的接口
*/
interface SortStrategy
{
       /**
       *利用各种算法对实现了Comparable接口的数组进行升序排列
       */
       public void sort(Comparable[] obj);
}
Sort类：
package Utils.Sort;
/**
*排序类，通过此类的sort()可以对实现了Comparable接口的数组进行升序排序
*/
public class Sort
{
       private SortStrategy strategy;

       /**
       *构造方法，由type决定由什么算法进行排序，排序方法的单词守字母要大字，如对于快速排序应该是
uickSort
       *@param type 排序算法的类型
       */
       public Sort(String type)
       {  try
              {    type = "Utils.Sort." + type.trim();
                     Class c = Class.forName(type);
                     strategy = (SortStrategy)c.newInstance();
              }
              catch (Exception e)
              {  e.printStackTrace();
              }            
       }
      
       /**
       *排序方法，要求待排序的数组必须实现Comparable接口
       */
       public void sort(Comparable[] obj)
       {
              strategy.sort(obj);
       }}


[b]插入排序算法的JAVA实现[/b]

package Utils.Sort;
/**
*插入排序，要求待排序的数组必须实现Comparable接口
*/
public class InsertSort implements SortStrategy
{    /**
       *利用插入排序算法对obj进行排序
       */
       public void sort(Comparable []obj)
       {  if (obj == null)
              {  throw new NullPointerException("The argument can not be null!");
              }
              /*
              *对数组中的第i个元素，认为它前面的i - 1个已经排序好，然后将它插入到前面的i - 1个元素中
              */
              int size = 1;
              while (size
              {  insert(obj, size++, obj[size - 1]);
              }        }
       /**
       *在已经排序好的数组中插入一个元素，使插入后的数组仍然有序
       *@param obj 已经排序好的数组
       *@param size 已经排序好的数组的大小
       *@param c 待插入的元素
       */
       private void insert(Comparable []obj, int size, Comparable c)
       { for (int i = 0 ;i
              {  if (c.compareTo(obj[i])
                     { System.out.println(obj[i]);
                            //如果待插入的元素小于当前元素，则把当前元素后面的元素依次后移一位
                            for (int j = size ;j > i ;j-- )
                            { obj[j] = obj[j - 1];
                            }
                            obj[i] = c;
                            break;
                     }               }        } }

（待续2）
来源：[url=http://blog.csdn.net/Linyco/]http://blog.csdn.net/Linyco/[/url]

[[i] 本帖最后由 铭铭 于 2005-10-13 09:01 AM 编辑 [/i]]

铭铭

<!---->

2005-10-13 01:04

快速排序算法和冒泡排序算法的JAVA实现

[b]快速排序算法的JAVA实现[/b]

package Utils.Sort;
/**
*快速排序，要求待排序的数组必须实现Comparable接口
*/
public class QuickSort implements SortStrategy
{    private static final int CUTOFF = 3;             //当元素数大于此值时采用快速排序
       /**
       *利用快速排序算法对数组obj进行排序，要求待排序的数组必须实现了Comparable接口
       */
       public void sort(Comparable[] obj)
       {   if (obj == null)
              {  throw new NullPointerException("The argument can not be null!");
              }
              quickSort(obj, 0, obj.length - 1);
       }
       /**
       *对数组obj快速排序
       *@param obj　待排序的数组
       *@param left 数组的下界
       *@param right 数组的上界
       */
       private void quickSort(Comparable[] obj, int left, int right)
       {    if (left + CUTOFF > right)
              {     SortStrategy ss = new ChooseSort();
                     ss.sort(obj);
              }  else
              {   //找出枢轴点，并将它放在数组最后面的位置
                     pivot(obj, left, right);
                     int i = left, j = right - 1;
                     Comparable tmp = null;
                     while (true)
                     {    //将i, j分别移到大于/小于枢纽值的位置
                            //因为数组的第一个和倒数第二个元素分别小于和大于枢纽元，所以不会发生数组越界
                            while (obj[++i].compareTo(obj[right - 1])     {}
                            while (obj[--j].compareTo(obj[right - 1]) > 0)      {}
                           //交换
                            if (i
                            {  tmp = obj[i];
                                   obj[i] = obj[j];
                                   obj[j] = tmp;
                            }
                            else    break;
                     }
                     //将枢纽值与i指向的值交换
                     tmp = obj[i];
                     obj[i] = obj[right - 1];
                     obj[right - 1] = tmp;
                     //对枢纽值左侧和右侧数组继续进行快速排序
                     quickSort(obj, left, i - 1);
                     quickSort(obj, i + 1, right); }
       }
       /**
       *在数组obj中选取枢纽元，选取方法为取数组第一个、中间一个、最后一个元素中中间的一个。将枢纽元置于倒数第二个位置，三个中最大的放在数组最后一个位置，最小的放在第一个位置
       *@param obj 要选择枢纽元的数组
       *@param left 数组的下界
       *@param right 数组的上界
       */
       private void pivot(Comparable[] obj, int left, int right)
       {  int center = (left + right) / 2;
              Comparable tmp = null;
              if (obj[left].compareTo(obj[center]) > 0)
              {  tmp = obj[left];
                     obj[left] = obj[center];
                     obj[center] = tmp;
              }
              if (obj[left].compareTo(obj[right]) > 0)
              {  tmp = obj[left];
                     obj[left] = obj[right];
                     obj[right] = tmp;
              }
              if (obj[center].compareTo(obj[right]) > 0)
              { tmp = obj[center];
                     obj[center] = obj[right];
                     obj[center] = tmp;
              }
              //将枢纽元置于数组的倒数第二个
                tmp = obj[center];
              obj[center] = obj[right - 1];
              obj[right - 1] = tmp;
       } }
[b]冒泡排序算法的JAVA实现[/b]

package Utils.Sort;
/**
*@author Linyco
*利用冒泡排序法对数组排序，数组中元素必须实现了Comparable接口。
*/
public class BubbleSort implements SortStrategy
{
  /**
       *对数组obj中的元素以冒泡排序算法进行排序
       */
       public void sort(Comparable[] obj)
       {     if (obj == null)
              {    throw new NullPointerException("The argument can not be null!");
              }
              Comparable tmp;
              for (int i = 0 ;i
              {    //切记，每次都要从第一个开始比。最后的不用再比。
                     for (int j = 0 ;j
                     {   //对邻接的元素进行比较，如果后面的小，就交换
                            if (obj[j].compareTo(obj[j + 1]) > 0)
                            {  tmp = obj[j];
                                   obj[j] = obj[j + 1];
                                   obj[j + 1] = tmp;
                            }   }
              }  }
}

作者：Linyco
来源：
[url=http://blog.csdn.net/Linyco/]
[color=#003366]http://blog.csdn.net/Linyco/[/color]
[/url]

铭铭

<!---->

2005-10-13 01:08

选择排序、归并排序和希尔排序算法的JAVA实现

[b]归并排序算法的JAVA实现[/b]

package Utils.Sort;
/**
*归并排序，要求待排序的数组必须实现Comparable接口
*/
public class MergeSort implements SortStrategy
{  private Comparable[] bridge;
       /**
       *利用归并排序算法对数组obj进行排序
       */
       public void sort(Comparable[] obj)
       {   if (obj == null)
              {    throw new NullPointerException("The param can not be null!");
              }
              bridge = new Comparable[obj.length];                //初始化中间数组
              mergeSort(obj, 0, obj.length - 1);                       //归并排序
              bridge = null;
       }
       /**
       *将下标从left到right的数组进行归并排序
       *@param obj　要排序的数组的句柄
       *@param left 要排序的数组的第一个元素下标
       *@param right 要排序的数组的最后一个元素的下标
       */
       private void mergeSort(Comparable[] obj, int left, int right)
       {    if (left
              {     int center = (left + right)/2;
                     mergeSort(obj, left, center);
                     mergeSort(obj, center + 1, right);
                     merge(obj, left, center, right);
              }
       }
       /**
       *将两个对象数组进行归并，并使归并后为升序。归并前两个数组分别有序
       *@param obj 对象数组的句柄
       *@param left 左数组的第一个元素的下标
       *@param center 左数组的最后一个元素的下标
       *@param right 右数组的最后一个元素的下标
       */
       private void merge(Comparable[] obj, int left, int center, int right)
       {   int mid = center + 1;
              int third = left;
              int tmp = left;
              while (left
              {     //从两个数组中取出小的放入中间数组
                     if (obj[left].compareTo(obj[mid])
                     {      bridge[third++] = obj[left++];
                     }    else
                            bridge[third++] = obj[mid++];
              }
              //剩余部分依次置入中间数组
              while (mid
              {  bridge[third++] = obj[mid++];
              }
              while (left
              {    bridge[third++] = obj[left++];
              }
              //将中间数组的内容拷贝回原数组
              copy(obj, tmp, right);
       }
       /**
       *将中间数组bridge中的内容拷贝到原数组中
       *@param obj 原数组的句柄
       *@param left 要拷贝的第一个元素的下标
       *@param right 要拷贝的最后一个元素的下标
       */
       private void copy(Comparable[] obj, int left, int right)
       {   while (left
              {   obj[left] = bridge[left];
                     left++;
              } }
}

[b]选择排序算法的JAVA实现[/b]

package Utils.Sort;
/**
*@author Linyco
*利用选择排序法对数组排序，数组中元素必须实现了Comparable接口。
*/
public class ChooseSort implements SortStrategy
{    /**
       *对数组obj中的元素以选择排序算法进行排序
       */
       public void sort(Comparable[] obj)
       {  if (obj == null)
              {    throw new NullPointerException("The argument can not be null!");
              }
              Comparable tmp = null;
              int index = 0;
              for (int i = 0 ;i
              {    index = i;
                     tmp = obj[i];
                     for (int j = i + 1 ;j
                     {  //对邻接的元素进行比较，如果后面的小，就记下它的位置
                            if (tmp.compareTo(obj[j]) > 0)
                            {    tmp = obj[j];   //要每次比较都记录下当前小的这个值!
                                   index = j;
                            }
                     }
                     //将最小的元素交换到前面
                     tmp = obj[i];
                     obj[i] = obj[index];
                     obj[index] = tmp;
              }        } }

[b]希尔排序算法的JAVA实现[/b]

package Utils.Sort;
/**
*希尔排序，要求待排序的数组必须实现Comparable接口
*/
public class ShellSort implements SortStrategy
{ private int[] increment;
/**
*利用希尔排序算法对数组obj进行排序
*/
public void sort(Comparable[] obj)
{ if (obj == null)
{ throw new NullPointerException("The argument can not be null!");
}
//初始化步长
initGap(obj);
//步长依次变化（递减）
for (int i = increment.length - 1 ;i >= 0 ;i-- )
{ int step = increment[i];
//由步长位置开始
for (int j = step ;j
{ Comparable tmp;
//如果后面的小于前面的（相隔step），则与前面的交换
for (int m = j ;m >= step ;m = m - step )
{ if (obj[m].compareTo(obj[m - step])
{ tmp = obj[m - step];
obj[m - step] = obj[m];
obj[m] = tmp;
}
//因为之前的位置必定已经比较过，所以这里直接退出循环
else
{ break;
} } } }
}
/**
*根据数组的长度确定求增量的公式的最大指数,公式为pow(4, i) - 3 * pow(2, i) + 1和9 * pow(4, i) - 9 * pow(2, i) + 1
*@return int[] 两个公式的最大指数
*@param length 数组的长度
*/
private int[] initExponent(int length)
{ int[] exp = new int[2];
exp[0] = 1;
exp[1] = -1;
int[] gap = new int[2];
gap[0] = gap[1] = 0;
//确定两个公式的最大指数
while (gap[0]
{ exp[0]++;
gap[0] = (int)(Math.pow(4, exp[0]) - 3 * Math.pow(2, exp[0]) + 1);
}
exp[0]--;
while (gap[1]
{
exp[1]++;
gap[1] = (int)(9 * Math.pow(4, exp[1]) - 9 * Math.pow(2, exp[1]) + 1);
}
exp[1]--;
return exp;
}
private void initGap(Comparable[] obj)
{ //利用公式初始化增量序列
int exp[] = initExponent(obj.length);
int[] gap = new int[2];
increment = new int[exp[0] + exp[1]];
//将增量数组由大到小赋值
for (int i = exp[0] + exp[1] - 1 ;i >= 0 ;i-- )
{ gap[0] = (int)(Math.pow(4, exp[0]) - 3 * Math.pow(2, exp[0]) + 1);
gap[1] = (int)(9 * Math.pow(4, exp[1]) - 9 * Math.pow(2, exp[1]) + 1);
//将大的增量先放入增量数组，这里实际上是一个归并排序
//不需要考虑gap[0] == gap[1]的情况，因为不可能出现相等。
if (gap[0] > gap[1])
{ increment[i] = gap[0];
exp[0]--;
} else
{ increment[i] = gap[1];
exp[1]--;
} } } }

作者：Linyco
来源：
[url=http://blog.csdn.net/Linyco/]
[color=#003366]http://blog.csdn.net/Linyco/[/color]
[/url]