package file;
import java.util.Arrays;
/**
*堆排序 冒泡排序法 选择排序法 快速排序法 插入排序法 折半插入排序法 希尔排序法 归并排序法
* 排序方法比较
* 排序方法 平均时间 最坏时间 辅助存储
* 直接插入排序 O(N2) O(N2) O(1)
* 起泡排序 O(N2) O(N2) O(1)
* 快速排序 O(Nlog2N) O(N2) O(Nlog2N)
* 简单选择排序 O(N2) O(N2) O(1)
* 堆排序 O(Nlog2N) O(Nlog2N) O(1)
* 归并排序 O(Nlog2N) O(Nlog2N) O(n)
* 基数排序 O(d(n+radix)) O(d(n+radix)) O(radix)
* @param <T>
*/
public class MySort<T extends Comparable<T>> {
/**排序交换次数，作为效率的一个参考而已，不一定准确，还和测试数据的大小，有序等因素有关 */
private int number=0;
//交换索引i和索引j的值
private void swap(T[] data,int i,int j){
number++;//交换计数器加一
T tmp;
tmp = data[i];
data[i] = data[j];
data[j] = tmp;
}
public int getNumber() {
return number;
}
public void setNumber(int number) {
this.number = number;
}
/**-----堆排序 时间复杂度O(nlogn)-----*/
public void heapSort(T[] data) {
int arrayLength = data.length;
// 循环建堆
for (int i = 0; i < arrayLength - 1; i++) {
// 建堆
builMaxdHeap(data, arrayLength - 1 - i);
// 交换堆顶和最后一个元素
swap(data, 0, arrayLength - 1 - i);
//System.out.println(java.util.Arrays.toString(data));
}
}
// 对data数组从0到lastIndex建大顶堆
private void builMaxdHeap(T[] data, int lastIndex) {
// 从lastIndex处节点（最后一个节点）的父节点开始
for (int i = (lastIndex - 1) / 2; i >= 0; i--) {
// k保存当前正在判断的节点
int k = i;
// 如果当前k节点的子节点存在
while (k * 2 + 1 <= lastIndex) {
// k节点的左子节点的索引
int biggerIndex = 2 * k + 1;
// 如果biggerIndex小于lastIndex，即biggerIndex + 1
// 代表的k节点的右子节点存在
if (biggerIndex < lastIndex) {
// 如果右子节点的值较大
if (data[biggerIndex].compareTo(data[biggerIndex + 1]) < 0) {
// biggerIndex总是记录较大子节点的索引
biggerIndex++;
}
}
// 如果k节点的值小于其较大子节点的值
if (data[k].compareTo(data[biggerIndex]) < 0) {
// 交换它们
swap(data, k, biggerIndex);
// 将biggerIndex赋给k，开始while循环的下一次循环，
// 重新保证k节点的值大于其左、右子节点的值。
k = biggerIndex;
} else {
break;
}
}
}
}
/**-----冒泡排序法 时间复杂度O(n^2) 平方-----*/
public void bubbleSort(T[] data){
int i,j;
for(i=0;i<data.length-1;i++){
for(j=0;j<data.length-i-1;j++){
//排序之前[9, -16*, 21, 23, -30, -49, 21*, 30, 30]
//排序之后[-49, -30, -16*, 9, 21, 21*, 23, 30, 30]
if(data[j].compareTo(data[j+1]) > 0){
swap(data,j+1,j);
}
}
}
}
/**-----选择排序法 时间复杂度O(n^2)-----*/
public void selectSort(T[] data){
int i,j;
for(i=0;i<data.length-1;i++){
for(j=i+1;j<data.length;j++){
//排序之前[9, -16*, 21, 23, -30, -49, 21*, 30, 30]
//排序之后[-49, -30, -16*, 9, 21, 21*, 23, 30, 30]
if (data[i].compareTo(data[j]) > 0){
swap(data,i,j);
}
}
}
}
/**-----快速排序法 时间复杂度为O(log2n)-----*/
public void quickSort(T[] data){
subQuickSort(data,0,data.length-1);
}
private void subQuickSort(T[] data,int start,int end){
if( start < end ){
//以第一个元素作为分界值
T base = data[start];
//i从左边开始搜索大于分界值元素的索引
int i = start;
//j从右边开始搜索小于分界值元素的索引
int j = end + 1;
//排序之前[9, -16*, 21, 23, -30, -49, 21*, 30, 30]
//排序之后[-30, -16*, -49, 9, 21*, 21, 23, 30, 30]
while(true){
//左边跳过比base小的元素
while(i < end && data[++i].compareTo(base) <= 0);
//右边跳过比base大的元素
while(j > start && data[--j].compareTo(base) >= 0);
if(j > i){
swap(data,i,j);
}else{
break;
}
}
//将分界值还原
swap(data,start,j);
//递归左边序列
subQuickSort(data,start,j-1);
//递归右边序列
subQuickSort(data,j+1,end);
// System.out.println( Arrays.toString(data) );
}
}
/**-----插入排序法 时间复杂度O(n^2)-----*/
public void insertSort(T[] data){
int arrayLength = data.length;
for(int i=1;i<arrayLength;i++){
//当整体后移时保证data[i]的值不会丢失
T tmp = data[i];
//i索引处的值已经比前面所有值都大,表明已经有序,无需插入
//i-1处索引之前的数值已经有序,i-1处索引处元素的值也是最大值
if(data[i].compareTo(data[i-1]) < 0){
int j = i-1;
//整体后移一个
while(j>=0 && data[j].compareTo(tmp) > 0){
number++;
data[j+1] = data[j];
j--;
}
data[j+1] = tmp;
// System.out.println( Arrays.toString(data) );
}
}
}
/**-----折半插入排序法 时间复杂度-----*/
public void binaryInsertSort(T[] data) {
int arrayLength = data.length;
for (int i = 1; i < arrayLength; i++) {
if (data[i - 1].compareTo(data[i]) > 0) {
// 缓存i处的元素值
T tmp = data[i];
// 记录搜索范围的左边界
int low = 0;
// 记录搜索范围的右边界
int high = i - 1;
while (high >= low) {
number++;
// 记录中间位置
int mid = (high + low) / 2;
// 比较中间位置数据和i处数据大小，以缩小搜索范围
if (tmp.compareTo(data[mid]) > 0) {
low = mid + 1;
} else {
high = mid - 1;
}
}
// 将low~i处数据整体向后移动1位
for (int j = i; j > low; j--) {
data[j] = data[j - 1];
}
data[low] = tmp;
}
//System.out.println( Arrays.toString(data) );
}
}
/**-----希尔排序法 时间复杂度O(nlogn)O(n^2)具体看h的值-----*/
public void shellSort(T[] data){
int arrayLength = data.length;
//h保存可变增量
int h = 1;
while(h<=arrayLength/3){
h = h * 3 + 1;
//System.out.println("h="+h);
}
while(h > 0){
//System.out.println(Arrays.toString( data )+"h="+h);
for(int i=h;i<arrayLength;i++){
//当整体后移时,保证data[i]的值不丢失
T tmp = data[i];
//i索引处的值已经比前面所有的值大
//(i-1索引之前的值已经有序的,i-1索引处元素的值就是最大值)
if(data[i].compareTo(data[i-h]) < 0){
int j = i-h;
//整体后移一格
while(j>=0 && data[j].compareTo(tmp) > 0){
number++;
data[j+h] = data[j];
j-=h;
}
//最后将tmp值插入合适的位置
data[j+h] = tmp;
}
}
h = (h-1)/3;
}
}
/**-----归并排序法 时间复杂度为O(nlog2n)-----*/
public void mergeSort(T[] data){
subMergeSort(data,0,data.length-1);
}
private void subMergeSort(T[] data,int left,int right){
if(right > left){
//找出中间索引
//System.out.println( Arrays.toString(data) );
int center = (left + right)/2;
//对左边数组进行递归
subMergeSort(data,left,center);
//对右边数组进行递归
subMergeSort(data,center+1,right);
//合并
merge(data,left,center,right);
}
}
@SuppressWarnings("unchecked")
private void merge(T[] data, int left, int center, int right) {
Object[] tmpArr = new Object[data.length];
int mid = center + 1;
// third记录中间处索引
int third = left;
int tmp = left;
while (left <= center && mid <= right) {
// 从两个数组中取出最小的放入中间数组
if (data[left].compareTo(data[mid]) <= 0) {
tmpArr[third++] = data[left++];
} else {
tmpArr[third++] = data[mid++];
}
}
// 剩余部分依次放入中间数组
while (mid <= right) {
tmpArr[third++] = data[mid++];
}
while (left <= center) {
tmpArr[third++] = data[left++];
}
// 将中间数组的内容复制拷回原数组
// (原left~right范围内德内容被复制回原数组)
while (tmp <= right) {
data[tmp] = (T) tmpArr[tmp++];
}
number++;
}
public static void main(String[] args){
DataWarp[] dataWarp = {
new DataWarp(9,""),
new DataWarp(-16,"*"),
new DataWarp(21,""),
new DataWarp(23,""),
new DataWarp(-30,""),
new DataWarp(-49,""),
new DataWarp(21,"*"),
new DataWarp(30,""),
new DataWarp(56,""),
new DataWarp(40,""),
new DataWarp(430,""),
new DataWarp(-67,""),
new DataWarp(56,""),
new DataWarp(-87,""),
new DataWarp(26,""),
new DataWarp(92,""),
new DataWarp(30,"")
};
DataWarp[] dataWarp2 = {
new DataWarp(9,""),
new DataWarp(-16,"*"),
new DataWarp(21,""),
new DataWarp(23,""),
new DataWarp(-30,""),
new DataWarp(-49,""),
new DataWarp(21,"*"),
new DataWarp(30,""),
new DataWarp(56,""),
new DataWarp(40,""),
new DataWarp(430,""),
new DataWarp(-67,""),
new DataWarp(56,""),
new DataWarp(-87,""),
new DataWarp(26,""),
new DataWarp(92,""),
new DataWarp(30,"")
};
DataWarp[] dataWarp3=new DataWarp[dataWarp.length];
System.arraycopy(dataWarp, 0, dataWarp3, 0, dataWarp3.length);
DataWarp[] dataWarp4=new DataWarp[dataWarp.length];
System.arraycopy(dataWarp, 0, dataWarp4, 0, dataWarp4.length);
DataWarp[] dataWarp5=new DataWarp[dataWarp.length];
System.arraycopy(dataWarp, 0, dataWarp5, 0, dataWarp5.length);
DataWarp[] dataWarp6=new DataWarp[dataWarp.length];
System.arraycopy(dataWarp, 0, dataWarp6, 0, dataWarp6.length);
DataWarp[] dataWarp7=new DataWarp[dataWarp.length];
System.arraycopy(dataWarp, 0, dataWarp7, 0, dataWarp7.length);
DataWarp[] dataWarp8=new DataWarp[dataWarp.length];
System.arraycopy(dataWarp, 0, dataWarp8, 0, dataWarp8.length);
System.out.println( "排序之前" + Arrays.toString(dataWarp) );
MySort<DataWarp> sort = new MySort<DataWarp>();
sort.setNumber(0);
sort.mergeSort(dataWarp);
System.out.println( "归并排序之后,number=" +sort.getNumber() +","+Arrays.toString(dataWarp) );
sort.setNumber(0);
sort.shellSort(dataWarp2);
System.out.println( "希尔排序之后,number=" +sort.getNumber() +","+Arrays.toString(dataWarp2) );
sort.setNumber(0);
sort.heapSort(dataWarp3);
System.out.println( "堆排序之后,number=" +sort.getNumber() +","+Arrays.toString(dataWarp3) );
sort.setNumber(0);
sort.bubbleSort(dataWarp4);
System.out.println( "冒泡排序之后,number=" +sort.getNumber() +","+Arrays.toString(dataWarp4) );
sort.setNumber(0);
sort.selectSort(dataWarp5);
System.out.println( "选择排序之后,number=" +sort.getNumber() +","+Arrays.toString(dataWarp5) );
sort.setNumber(0);
sort.quickSort(dataWarp6);
System.out.println( "快速排序之后,number=" +sort.getNumber() +","+Arrays.toString(dataWarp6) );
sort.setNumber(0);
sort.insertSort(dataWarp7);
System.out.println( "插入排序之后,number=" +sort.getNumber() +","+Arrays.toString(dataWarp7) );
sort.setNumber(0);
sort.binaryInsertSort(dataWarp8);
System.out.println( "折半插入排序之后,number=" +sort.getNumber() +","+Arrays.toString(dataWarp8) );
}
}
package file;public class DataWarp implements Comparable<DataWarp>{private Integer data;private String name;public DataWarp(Integer data, String name) {super();this.data = data;this.name = name;}@Overridepublic int compareTo(DataWarp o) {return o.data-data;}@Overridepublic String toString() {//return "DataWarp [data=" + data + ", name=" + name + "]";return String.valueOf(data);}}
http://www.open-open.com/lib/view/open1345733835985.html