首页 > 代码库 > 数据结构——八大排序算法
数据结构——八大排序算法
驱动程序：
public class Main {
public static void main(String[] args) {
int[] array={2,0,3,4,1,9,6,8,7,5};
print(Sort.bubbleSort(array, true));//冒泡
print(Sort.InsertionSort(array, true));//插入
print(Sort.mergeSort(array,true, "recursion"/*circulate*/));//归并
print(Sort.quickSort(array, true));//快速
print(Sort.radixSort(array, true));//基数
print(Sort.selectionSort(array, true));//选择
print(Sort.shellSort(array, true, "Hibbard"/*Sedgewick*/));//希尔
print(Sort.heapSort(array, true));//堆排序
}
private static void print(int[] array) {
for(int i:array){
System.out.print(i+" ");
}
System.out.println();
}
}
实现算法：
import java.util.ArrayList;
public class Sort {
private static void swap(int[] array,int i1,int i2){//交换
int tmp=array[i1];
array[i1]=array[i2];
array[i2]=tmp;
}
//-----------------------冒泡排序---------------------------------------------------------------------
public static int[] bubbleSort(int[] array,boolean sequence){
int[] newArray=array.clone();
for(int i=newArray.length-1;i>=0;i--){
boolean flag = false;
for(int j=0;j<i;j++){
if(sequence^newArray[j]<newArray[j+1]){
swap(newArray,j,j+1);
flag=true;
}
}
if(!flag){
break;
}
}
return newArray;
}
//-----------------------快速排序---------------------------------------------------------------------
public static int[] quickSort(int[] array,boolean sequence){
int[] newArray=array.clone();
quick(newArray,0,newArray.length-1,sequence);
return newArray;
}
private static void quick(int[] array,int left,int right,boolean sequence) {
if(3<=right-left){
int pivot=pivot(array, left, right, sequence);
int i=left;
int j=right-1;
while(i<=j){
for(;sequence^array[i]>pivot;++i){}
for(;sequence^array[j]<pivot;--j){}
if(i<j){
swap(array,i,j);
}
}
int end=sequence^array[i]>pivot?i:j;
swap(array, end, right-1);
quick(array, left, end-1, sequence);
quick(array, end+1, right, sequence);
}else{
InsertionSort(array,left,right,sequence);
}
}
private static int pivot(int[] array,int left,
int right,boolean sequence) {//得到主元
int center=(left+right)/2;
if(sequence^array[right]>array[left]){
swap(array, right, left);
}
if(sequence^array[center]>array[left]){
swap(array, center, left);
}else if(sequence^array[right]>array[center]){
swap(array, right, center);
}
swap(array,center,right-1);
return array[right-1];
}
//-----------------------插入排序---------------------------------------------------------------------
public static int[] InsertionSort(int[] array,boolean sequence){
int[] newArray=array.clone();
InsertionSort(newArray,sequence,1);
return newArray;
}
private static void InsertionSort(int[] array,boolean sequence,
int interval){//interval=间隔
//用在希尔排序的插入排序算法
for(int i=interval;i<array.length;i+=interval){
int tmp=array[i];
for(int j=i;;j-=interval){
if(j==0||sequence^tmp<array[j-interval]){
array[j]=tmp;
break;
}else{
array[j]=array[j-interval];
}
}
}
}
private static void InsertionSort(int[] array,int left,int right,
boolean sequence){
//用在快速排序的插入排序算法
for(int i=left;i<right+1;i++){
int tmp=array[i];
for(int j=i;;j--){
if(j==0||sequence^tmp<array[j-1]){
array[j]=tmp;
break;
}else{
array[j]=array[j-1];
}
}
}
}
//-----------------------选择排序----------------------------------------------------------------------
public static int[] selectionSort(int[] array,boolean sequence){
int[] newArray=array.clone();
for(int i=0;i<newArray.length-1;i++){
int position=i;
for (int j = i+1; j < newArray.length; j++) {
if(sequence^newArray[position]<newArray[j]){
position=j;
}
}
swap(newArray, i, position);
}
return newArray;
}
//-----------------------堆排序----------------------------------------------------------------------
public static int[] heapSort(int[] array,boolean sequence){
int[] heap=array.clone();
biuldHeap(heap,sequence);
int[] newArray=new int[array.length];
for(int i=0;i<heap.length;i++){
newArray[i]=popHeapTop(heap,sequence,heap.length-1-i);
}
return newArray;
}
private static void biuldHeap(int[] array,boolean sequence) {
for(int i=(array.length-1)/2;i>=0;i--){
int j=i;
int tmp;
while(j*2+1<=array.length-1){
tmp=j*2+2>array.length-1||sequence^array[j*2+1]>array[j*2+2]
?j*2+1:j*2+2;
if(sequence^array[j]<array[tmp]){
swap(array, j, tmp);
}
j=tmp;
}
}
}
private static int popHeapTop(int[] array,boolean sequence,int size) {
int top=array[0];
array[0]=array[size];
for(int i=0,tmp;i*2+1<=size-1;i=tmp){
tmp=i*2+2>size-1||sequence^array[i*2+1]>array[i*2+2]
?i*2+1:i*2+2;
if(sequence^array[i]<array[tmp]){
swap(array, i, tmp);
}else{
break;
}
i=tmp;
}
return top;
}
//-----------------------希尔排序----------------------------------------------------------------------
public static int[] shellSort(int[] array,boolean sequence,
String sequenceName){
int[] newArray=array.clone();
ArrayList<Integer> list=new ArrayList<>();//第一种方法
if(sequenceName.equals("Hibbard")){
list=hibbard(newArray);
}else if(sequenceName.equals("Sedgewick")){//第二种方法
list=sedgewick(newArray);
}
for(int i=list.size()-1;i>=0;i--){
InsertionSort(newArray,sequence,list.get(i));
}
return newArray;
}
private static ArrayList<Integer> hibbard(int[] array){//第一种增量算法
int value=http://www.mamicode.com/1;
ArrayList<Integer> hibbard=new ArrayList<>();
for(int i=1;;i++){
value=http://www.mamicode.com/(int)(Math.pow(2, i)-1);
if(value<array.length){
hibbard.add(value);
}else{
break;
}
}
return hibbard;
}
private static ArrayList<Integer> sedgewick(int[] array){//第二种增量算法
int value=http://www.mamicode.com/1;
ArrayList<Integer> sedgewick=new ArrayList<>();
sedgewick.add(value);//公式第一项是-1，我也很无奈啊
for(int i=2;;i++){
value=http://www.mamicode.com/(int) (Math.pow(4,i)-3*Math.pow(2,i)+1);
if(value<array.length){
sedgewick.add(value);
}else {
break;
}
}
return sedgewick;
}
//-----------------------归并排序----------------------------------------------------------------------
public static int[] mergeSort(int[] array,boolean sequence,String way){
int[] newArray=array.clone();
int[] tmpArray=new int[newArray.length];
if(way.equals("recursion")){
merageRecursion(newArray,tmpArray,0,newArray.length-1,sequence);
}else if(way.equals("circulate")){
int cnt=1;
while(cnt<newArray.length){
merageCirulate(newArray, tmpArray, cnt, sequence);
cnt*=2;
merageCirulate(tmpArray, newArray, cnt, sequence);
cnt*=2;
}
}
return tmpArray;
}
private static void merageCirulate(int[] array,int[] tmpArray,
int cnt,boolean sequence) {//循环
int i;
String way="circulate";
for(i=0;i<=array.length-2*cnt;i+=2*cnt){
merage(array, tmpArray, i,i+cnt, i+2*cnt-1, sequence,way);
}
if(i+cnt<array.length){
merage(array, tmpArray, i,i+cnt, array.length-1, sequence,way);
}else{
for(int j=i;j<array.length;j++){
tmpArray[j]=array[j];
}
}
}
private static void merageRecursion(int[] array,int[] tmpArray,int left,
int rightEnd,boolean sequence) {//递归
int center;
String way="recursion";
if(left<rightEnd){
center=(rightEnd+left)/2;
merageRecursion(array, tmpArray, left, center, sequence);
merageRecursion(array, tmpArray, center+1, rightEnd, sequence);
merage(array,tmpArray,left,center+1,rightEnd,sequence,way);
}
}
private static void merage(int[] array,int[] tmpArray,int left,int right,int rightEnd,
boolean sequence,String way) {
int leftEnd=right-1;
int tmp=left;
int start=left;
while(left<=leftEnd&&right<=rightEnd) {
if(sequence^array[left]<array[right]){
tmpArray[tmp++]=array[right++];
}else{
tmpArray[tmp++]=array[left++];
}
}
while (right<=rightEnd) {
tmpArray[tmp++]=array[right++];
}
while (left<=leftEnd) {
tmpArray[tmp++]=array[left++];
}
if(way.equals("recursion")){
for(int i=rightEnd;i>=start;i--){
array[i]=tmpArray[i];
}
}
}
//-----------------------基数排序----------------------------------------------------------------------
public static int[] radixSort(int[] array,boolean sequence){
int ten=10;//十进制
int max=MaxFigure(array);
int[][] buckets=new int[ten][array.length];
int[] cnts =new int[ten];
for(int i=0;i<array.length;i++){
int value=http://www.mamicode.com/array[i];
int row=value%10;
buckets[row][cnts[row]]=value;
cnts[row]++;
}
for(int i=0;i<max+1;i++){
int[][] buffer=new int[ten][array.length];
int[] cntsBuffer=new int[ten];
for(int j=0;j<ten;j++){
for(int k=0;k<cnts[j];k++){
int value=http://www.mamicode.com/buckets[j][k];
int row=value/(int) Math.pow(10,i)%10;
buffer[row][cntsBuffer[row]]=value;//几位上的数字
cntsBuffer[row]++;
}
}
buckets=buffer.clone();
cnts=cntsBuffer.clone();
}
int[] newArray=new int[array.length];
if(sequence){
newArray=buckets[0];
}else {
for(int i=0,j=array.length-1;j>=0;j--,i++){
newArray[i]=buckets[0][j];
}
}
return newArray;
}
private static int MaxFigure(int[] array) {//求数组中最大数的最大位数 个位=1
int maxValue=http://www.mamicode.com/array[0];//最大数
int figure;
for(int i=1;i<array.length;i++){
if(array[i]>maxValue){
maxValue=http://www.mamicode.com/array[i];
}
}
for(figure=1;maxValue>=10;figure++){
maxValue/=10;
}
return figure;
}
}
数据结构——八大排序算法