内排序算法总结
package com.SoerAlgorithm;
import java.util.Arrays;
public class SelectSort {
/**
* @param args
*/
public static void main(String[] args) { // TODO Auto-generated method stub DataWrap []data={
new DataWrap(21,""), new DataWrap(49,""), new DataWrap(30,"*"), new DataWrap(16,""), new DataWrap(30,""), new DataWrap(9,"")
};
int [] data2={1100,192,221,12,13}; System.out.println("排序之
前:"+java.util.Arrays.toString(data2)); radixSort(data2,10,4);
System.out.println("\n");
System.out.println("排序之
后:"+java.util.Arrays.toString(data2));
}
/*
* 直接选择排序
*/
public static void selectSort(DataWrap[] data){ System.out.println("开始排序:"); int len=data.length;
DataWrap temp;
for(int i=0;i<len-1;i++){
for(int j=i+1;j<len;j++){
if(data[i].compareTo(data[j])>0){ temp=data[i];
data[i]=data[j];
data[j]=temp;
}
}
1
System.out.println(java.util.Arrays.toString(data));
}
}
/*
* 直接排序的改进算法
*/
public static void selectSort2(DataWrap[] data){
System.out.println("开始排序:");
int len=data.length;
DataWrap temp;
for(int i=0;i<len-1;i++){
int minindex=i;
for(int j=i+1;j<len;j++){
if(data[i].compareTo(data[j])>0){
if(data[minindex].compareTo(data[j])>0){ minindex=j;
}
}
if(minindex!=i){
temp=data[i];
data[i]=data[minindex];
data[minindex]=temp;
}
}
System.out.println(java.util.Arrays.toString(data));
}
}
/*
* 冒泡排序
*/
public static void bubbleSort(DataWrap[] data){
System.out.println("开始排序:");
int len=data.length;
for(int i=0;i<len-1;i++){
boolean flag=false;
for(int j=0;j<len-i-1;j++){
if(data[j].compareTo(data[j+1])>0){
// DataWrap temp=data[j+1];
// data[j+1]=data[j];
// data[j]=temp;
Swap(data,j+1,j);
flag=true;
}
}
System.out.println(java.util.Arrays.toString(data)); if(!flag){
break;
}
}
2
} /* * 交换元素 */ public static void Swap(DataWrap[] data,int i,int j){ DataWrap temp=data[i]; data[i]=data[j]; data[j]=temp; } /* * 快速排序 */ public static void QuickSort(DataWrap[] data){ SubqucikSort(data,0,data.length-1); } public static void SubqucikSort(DataWrap[] data,int start,int end){ //需要排序 if(start<end){ //以第一个元素作为分界值 DataWrap base=data[start]; int i=start; //从i的左边开始搜索 int j=end+1; //从j的右边开始搜索 while(true){ while(i<end && data[++i].compareTo(base)<=0); while(j>start && data[--j].compareTo(base)>=0); if(i<j){ Swap(data,i,j); } else{ break; } } Swap(data,start,j); //递归左子序列 SubqucikSort(data,start,j-1); //递归右子序列 SubqucikSort(data,j+1,end); } else{ throw new RuntimeException("越界"); } } /* * 插入排序 */ public static void InsertSort(DataWrap[] data){ 3
4 System.out.println("开始排序：\n"); int arrayLength = data.length; for (int i = 1 ; i < arrayLength ; i++ ) { //当整体后移时，保证data[i]的值不会丢失 DataWrap tmp = data[i]; //i索引处的值已经比前面所有值都大，表明已经有序，无需插入 //（i-1索引之前的数据已经有序的，i-1索引处元素的值就是最大值） if (data[i].compareTo(data[i - 1]) < 0) { int j = i - 1; //整体后移一格 for ( ; j >= 0 && data[j].compareTo(tmp) > 0 ; j--) { data[j + 1] = data[j]; } //最后将tmp的值插入合适位置 data[j + 1] = tmp; } System.out.println(java.util.Arrays.toString(data)); } } /* * 二分排序,也叫折半排序 */ public static void binSort(DataWrap[] data){ System.out.println("开始排序：\n"); int arrayLength = data.length; for(int i=0;i<arrayLength;i++){ DataWrap temp=data[i]; int low=0; int high=i-1; while(low<=high){ int mid=(low+high)/2; if(temp.compareTo(data[mid])<0){ high=mid-1; } else{ low=mid+1; } } for(int j=i;j>low;j--){ data[j]=data[j-1]; } data[low]=temp; System.out.println(java.util.Arrays.toString(data)); } } /*
5 * 堆排序 */ public static void HeapSort(DataWrap[] data){ System.out.println("开始排序:"); int len=data.length; for(int i=0;i<len-1;i++){ BuildMaxHeap(data,len-1-i); Swap(data,0,len-1-i); System.out.println(java.util.Arrays.toString(data)); } } public static void BuildMaxHeap(DataWrap[] data,int lastIndex){ for(int i=(lastIndex-1)/2;i>=0;i--){ //保存当前正在判断的节点 int k=i; while(k*2+1<=lastIndex){ int biggerIndex=2*k+1; if(biggerIndex<lastIndex){ if(data[biggerIndex].compareTo(data[biggerIndex+1])<0){ biggerIndex++; } } if(data[k].compareTo(data[biggerIndex])<0){ //交换 Swap(data,k,biggerIndex); k=biggerIndex; } else{ break; } } } } /* * Shell排序 * Shell排序是以h为增量的排序算法，直接插入排序算法可以看做是h=1的Shell排序 * */ public static void shellSort(DataWrap []data){ System.out.println("开始排序:"); int len=data.length; int h=1; while(h<len/3){ h=3*h+1; } while(h>0){ System.out.println("============h的为:"+h+"============="); for(int i=h;i<len;i++){
DataWrap temp=data[i];
if(data[i].compareTo(data[i-h])<0){
int j=i-h;
//整体后移h
for(;j>=0&&data[j].compareTo(temp)>0;j-=h){ data[j+h]=data[j];
}
data[j+h]=temp;
}
System.out.println(java.util.Arrays.toString(data)); }
h=(h-1)/3;
}
}
/*
* 归并排序
*/
public static void mergrSort(DataWrap []data){
sort(data,0,data.length-1);
}
public static void sort(DataWrap []data,int left,int right){ if(left<right){
int center=(left+right)/2;
//递归排序左边
sort(data,left,center);
//递归排序右边
sort(data,center+1,right);
merge(data,left,center,right);
}
}
public static void merge(DataWrap []data,int left,int center,int right){
DataWrap []temp=new DataWrap[data.length];
int mid=center+1;
int third=left;
int tep=left;
while(left<=center && mid<=right){
//从两个数组中取出小的放入中间数组
if(data[left].compareTo(data[mid])<=0){
temp[third++]=data[left++];
}
else{
temp[third++]=data[mid++];
}
}
//将剩余部分放入中间数组
while(mid<=right){
temp[third++]=data[mid++];
}
while(left<=center){
6
temp[third++]=data[left++]; } //将中间数组的数组复制到原数组 while(tep<=right){ data[tep]=temp[tep++]; } } /* *桶式排序(哈希排序) */ public static void BucketSort(DataWrap []data,int min,int max){ System.out.println("开始排序:"); int len=data.length; DataWrap []temp=new DataWrap[len]; //Buchet桶相当于定义了max-min个桶 int bucket[]=new int[max-min]; for(int i=0;i<len;i++){ bucket[data[i].data-min]++; } System.out.println(Arrays.toString(bucket)); //计算“落入”各桶内的元素所在序列中的位置 for(int i=1;i<max-min;i++){ bucket[i]=bucket[i]+bucket[i-1]; } System.out.println(Arrays.toString(bucket)); //将data数组中的数据完全复制到temp数组·中缓存起来 System.arraycopy(data, 0, temp, 0, len); //根据bucket数组中的信息将待排序的各个元素放入相应的位置 for(int k=len-1;k>=0;k--){ data[--bucket[temp[k].data-min]]=temp[k]; } } /* * 基数排序，此种排序算法要借助其他稳定的排序算法，最好是借助桶排序 */ public static void radixSort(int []data,int radix,int d){ System.out.println("开始排序:"); int len=data.length; int []temp=new int[len]; int []bucket=new int[radix]; for(int i=0,rate=1;i<d;i++){ Arrays.fill(bucket, 0); System.arraycopy(data, 0, temp, 0, len); //计算每个待排序数据的关键字 for(int j=0;j<len;j++){ int subKey=(temp[j]/rate)%radix; bucket[subKey]++; } for(int j=1;j<radix;j++){ bucket[j]=bucket[j]+bucket[j-1]; 7
}
for(int m=len-1;m>=0;m--){
int subKey=(temp[m]/rate)%radix;
data[--bucket[subKey]]=temp[m];
}
System.out.println("对"+rate+"位上的子关键字进行排序:"+java.util.Arrays.toString(data));
rate*=radix;
}
}
}
8