/**
* Copytright (c) blueantelope, 2008 All rigths reserved.
* 算法研究之用
*/
package org.blueantelope.mysrc.Arithmetic;
/**
* 排序算法
* @author blueantelope
* @version 0.1
* @since 2008-05-13
*/
public class SortClass {
private static final int[] unSort = {4, 6, 8, 2, 3, 1, 5, 7, 9, 12, 11}; // 未排序内容
/**
* 复制未排序的数组而得到新的数组
* @return 未排序的数组
*/
private static int[] getArray() {
int[] sort = new int[unSort.length];
System.arraycopy(unSort, 0, sort, 0, sort.length);
return sort;
}
/**
* 交换两个数组元素的位置
* @param array 需要排序的数组
* @param m,n 交换的数组下标
*/
private static void swap(int[] array, int m, int n) {
int temp = array[m];
array[m] = array[n];
array[n] = temp;
}
/**
* 冒泡排序
* @return 排序结果
*/
public static int[] BubbleSort() {
int[] sort = getArray();
int length = sort.length;
int count = 0;
for (int m=0; m<length; m++) {
for (int n=(length-1); n>m; n--) {
if (sort[n] < sort[n-1]) {
swap(sort, n, n-1);
count++;
}
}
}
System.out.print("执行了" + count + "次");
return sort;
}
/**
* 插入排序
* @return 排序结果
*/
public static int[] InsertSort() {
int[] sort = getArray();
int length = sort.length;
int count = 0;
for (int m=1; m<length; m++) {
for (int n=m; (n>0)&&(sort[n]<sort[n-1]); n--) {
swap(sort, n, n-1);
count ++;
}
}
System.out.print("执行了" + count + "次");
return sort;
}
/**
* 选择排序
* @return 排序结果
*/
public static int[] SelectSort() {
int[] sort = getArray();
int length = sort.length;
int count =0;
for (int m=0; m<length; m++) {
int index = m;
for (int n=(length-1); n>m; n--) {
if (sort[n] < sort[index]) {
index = n;
}
}
count++;
swap(sort, m, index);
}
System.out.print("执行了" + count + "次");
return sort;
}
/**
* 快速排序, 主程序
* @return 排序结果
*/
public static int[] mainQuickSort() {
int[] sort = getArray();
int length = sort.length;
QuickSort(sort, 0, length-1);
return sort;
}
/**
* 快速排序, 定义pivot中枢为开始位置
* 分两个区域递归排序, 小于中枢和大于中枢
* @param sort 排序数组
* @param first 排序区起始位置
* @param last 排序区终止位置
*/
private static void QuickSort(int[] sort, int first, int last) {
int pivot = 0; // 中枢的位置,可以处定义
if (first < last) {
pivot = partition(sort, first, last);
QuickSort(sort, first, pivot-1);
QuickSort(sort, pivot+1, last);
}
}
/**
* 快速排序, 定义分区
* @param sort 排序数组
* @param first 排序区起始位置
* @param last 排序区终止位置
* @return 中枢位置
*/
private static int partition(int[] sort, int first, int last) {
int pivotValue = sort[first];
int last1 = first;
for (int m=(first+1); m<=last; m++) {
if (sort[m] < pivotValue) {
++last1;
swap(sort, m, last1);
}
}
swap(sort, last1, first); //改变中枢位置
return last1;
}
/**
* 归并排序, 主程序
* @return 排序结果
*/
public static int[] mainMergeSort() {
int[] sort = getArray();
int length = sort.length;
MergeSort(sort, 0, length-1);
return sort;
}
/**
* 归并排序, 两个区域递归找中值后合并两个区域
* @param sort 排序数组
* @param frist 排序区起始位置
* @param last 排序区终止位置
*/
private static void MergeSort(int[] sort, int first, int last) {
if (first < last) {
int mid = (first+last) / 2;
MergeSort(sort, first, mid);
MergeSort(sort, mid+1, last);
Merge(sort, mid, first, last);
}
}
/**
* 归并排序, 合并两个区域, 需增加一个同样大小的临时数组
* @param sort 排序数组
* @param mid 排序中间位置
* @param first 排序区起始位置
* @param last 排序区终止位置
*/
private static void Merge(int[] sort, int mid, int first, int last) {
int[] temp = new int[sort.length];
int first1 = first;
int last1 = mid;
int first2 = mid + 1;
int last2 = last;
int index = first1;
/**
* 将数值小的区域放入临时数组前半部份
*/
while ( (first1 <= last1) && (first2 <= last2) ) {
if ( sort[first1] < sort[first2] ) {
temp[index] = sort[first1];
first1++;
} else {
temp[index] = sort[first2];
first2++;
}
index++;
}
/**
* 将数值大的区域放入临时数组前半部份
*/
while ( first1 <= last1 ) {
temp[index] = sort[first1];
first1++;
index++;
}
while( first2 <= last2 ) {
temp[index] = sort[first2];
first2++;
index++;
}
/**
* 将临时数组写回数组中
*/
for (index=first; index<=last; index++) {
sort[index] = temp[index];
}
}
/**
* 控制台显示数组元素
* @param sort 需输出的数组
*/
public void OutputArray(int[] sort) {
for (int n=0; n<sort.length; n++) {
System.out.printf("%3d", sort[n]);
}
System.out.println("");
}
public static void main(String[] args) {
System.out.print("冒泡排序: ");
new SortClass().OutputArray(SortClass.BubbleSort());
System.out.print("插入排序: ");
new SortClass().OutputArray(SortClass.InsertSort());
System.out.print("选择排序: ");
new SortClass().OutputArray(SortClass.SelectSort());
System.out.print("快速排序: ");
new SortClass().OutputArray(SortClass.mainQuickSort());
System.out.print("归并排序: ");
new SortClass().OutputArray(SortClass.mainMergeSort());
}
}
|
