排序种
排序类
/**
* 定义数字排序的接口
*
*/
public interface ISortNumber
{
/**
* 对整型数组按升序排序
* @param intArray 待排序的整型数组
* @return 按升序排序后的数组
*/
public int[] sortASC(int[] intArray);
}
/**
*
* 使用选择排序法对整型数组进行排序
*/
public class SelectionSort implements ISortNumber
{
public int[] sortASC(int[] intArray)
{
if(intArray == null)
{
return null;
}
/*
* 因为Java的参数传递是采用引用传值方式，在排序的过程中需要改变
* 数组元素的顺序，也就是改变了参数数组，所以，为了保证输入参数
* 的值不变，这里就采用了数组的clone方法，直接克隆一个数组
*/
int[] srcDatas = (int[])intArray.clone();
int size = srcDatas.length;
//从头遍历数组
for(int i=0;i<size;i++)
{
//遍历下标威i之后的元素
for(int j=i;j<size;j++)
{
//如果数组前面的值比后面的值大，则交换位置
if(srcDatas[i]>srcDatas[j])
{
swap(srcDatas, i, j);
}
}
}
return srcDatas;
}
/**
* 交换数组中下标为src和dest的值
* @param data 数组
* @param src 源下标
* @param dest 目标下标
*/
private void swap(int[] data,int src,int dest)
{
int temp = data[src];
data[src] = data[dest];
data[dest] = temp;
}
}
/**
*
* 冒泡法对整型数组排序
*/
public class BubbleSort implements ISortNumber
{
public int[] sortASC(int[] intArray) {
if(intArray==null)
{
return null;
}
int[] srcDatas = (int[])intArray.clone();
boolean changedPosition = true; //标示是否交换了数组中元素位置
int comparedTimes = 0; //标示比较次数
int maxComparedTimes = srcDatas.length-1; //标示排序过程中最多可能交换的次数
//如果已经发生的比较次数还没有到达最大次数，而且此前交换过元素位置，则继续
while((comparedTimes<maxComparedTimes) && (changedPosition))
{
for(int i=0;i<(maxComparedTimes-comparedTimes);i++)
{
changedPosition=false;
if(srcDatas[i]>srcDatas[i+1])
{
swap(srcDatas, i, i+1);
changedPosition=true;
}
}
comparedTimes++;
}
return srcDatas;
}
/**
* 交换数组中下标为src和dest的值
* @param data 数组
* @param src 源下标
* @param dest 目标下标
*/
private void swap(int[] data,int src,int dest)
{
int temp = data[src];
data[src] = data[dest];
data[dest] = temp;
}
}
/**
* 采用线性插入排序法实现数组排序
*
*/
public class LinearInsertSort implements ISortNumber
{
public LinearInsertSort()
{
}
public int[] sortASC(int[] intArray) {
if(intArray==null)
{
return null;
}
int[] srcDatas = (int[])intArray.clone();
int size = srcDatas.length;
int temp = 0;
int index = 0;
//假定第一个数字已经排好了顺序，所以i是从1开始而不是从0开始
for(int i=1;i<size;i++)
{
temp = srcDatas[i];
index = i;
while((index>0) && (temp<srcDatas[index-1]))
{
//移动index后面的数字
srcDatas[index] = srcDatas[index-1];
index--;
}
srcDatas[index] = temp;
}
return srcDatas;
}
}
/**
* 采用快速排序法实现数组的排序
*
*/
public class QuickSort implements ISortNumber
{
public QuickSort()
{
}
public int[] sortASC(int[] intArray) {
if(intArray ==null)
{
return null;
}
int[] srcDatas = (int[])intArray.clone();
return this.quickSort(srcDatas, 0, srcDatas.length-1);
}
/**
* 采用分治递归的方法实现快速排序法
* @param srcDatas 待排序的数组
* @param first 起始下标
* @param last 终止下标
* @return 排好序的数组
*/
private int[] quickSort(int[] srcDatas,int first,int last)
{
if(first<last)
{
int pos = partition(srcDatas, first, last);
quickSort(srcDatas, first, pos-1);
quickSort(srcDatas, pos+1, last);
}
return srcDatas;
}
/**
* 寻找数组的分治点
* 根据数组的第一个数分治，把比数组第一个数大的往后排，把比数组第一个数小的往前排
* @param srcDatas 待排序的数组
* @param first 起始下标
* @param last 终止下标
* @return 传入数组的第一个数的最终下标
*/
private int partition(int[] srcDatas,int first,int last)
{
int temp = srcDatas[first];
int pos = first;
for(int i=first+1;i<=last;i++)
{
if(srcDatas[i]<temp)
{
pos++;
swap(srcDatas, pos, i);
}
}
swap(srcDatas, first, pos);
return pos;
}
/**
* 交换数组中下标为src和dest的值
* @param data
* @param src
* @param dest
*/
private void swap(int[] data,int src,int dest)
{
int temp = data[src];
data[src] = data[dest];
data[dest] = temp;
}
}
public class SortTest
{
/**
* 打印数组
* @param intArray
*/
public static void printIntArray(int[] intArray)
{
if(intArray==null)
{
return;
}
for(int i=0;i<intArray.length;i++)
{
System.out.print(intArray[i] + " ");
}
System.out.println();
}
public static void main(String[] args)
{
int[] intArray = new int[]{6,3,4,2,7,2,-3,3};
System.out.print("排序前的数组：");
printIntArray(intArray);
ISortNumber test = new SelectionSort();
System.out.print("选择排序法排序结果：");
printIntArray(test.sortASC(intArray));
System.out.print("排序前的数组：");
printIntArray(intArray);
test = new BubbleSort();
System.out.print("冒泡排序法排序结果：");
printIntArray(test.sortASC(intArray));
System.out.print("排序前的数组：");
printIntArray(intArray);
test = new LinearInsertSort();
System.out.print("线性插入排序法排序结果");
printIntArray(test.sortASC(intArray));
System.out.print("排序前的数组：");
printIntArray(intArray);
test = new QuickSort();
System.out.print("快速排序法排序结果");
printIntArray(test.sortASC(intArray));
}
}