排序算法大总结

排序算法

冒泡排序快速排序插入排序希尔排序选择排序归并排序基数排序基数排序之队列实现堆排序

1.排序算法之冒泡排序

package demo01; import java.util.Arrays; //排序算法之冒泡排序 public class BubbleSort { public static void main(String[] args) { // TODO Auto-generated method stub int[] arr=new int[] {5,7,3,8,0,8,3,6,4,2}; bubbleSort(arr); System.out.println(Arrays.toString(arr)); } public static void bubbleSort(int[] arr) { for(int i=0;i<arr.length-1;i++) { for(int j=0;j<arr.length-1-i;j++) { if(arr[j]>arr[j+1]) { int tem=arr[j]; arr[j]=arr[j+1]; arr[j+1]=tem; } } } } }

2.排序算法之快速排序

package demo01; import java.util.Arrays; //排序算法之快速排序 public class QuickSort { public static void main(String[] args) { // TODO Auto-generated method stub int[] arr=new int[] {3,4,6,7,2,7,2,8,0}; quickSort(arr,0,arr.length-1); System.out.println(Arrays.toString(arr)); } public static void quickSort(int[] arr,int start,int end) { if(start<end) { int stand=arr[start]; int low=start; int high=end; while(low<high) { while(low<high && stand<=arr[high]) { high--; } arr[low]=arr[high]; while(low<high && arr[low]<=stand) { low++; } arr[high]=arr[low]; } arr[low]=stand; quickSort(arr,start,low); quickSort(arr,low+1,end); } } }

3.排序算法之插入排序

package demo01; import java.util.Arrays; //排序算法之插入排序 public class InserSort { public static void main(String[] args) { // TODO Auto-generated method stub int[] arr=new int[] {4,6,5,9,2,3,5,2}; inserSort(arr); System.out.println(Arrays.toString(arr)); } public static void inserSort(int[] arr) { for(int i=1;i<arr.length;i++) { if(arr[i]<arr[i-1]) { int temp=arr[i]; int j; for(j=i-1;j>=0&&arr[j]>temp;j--) { arr[j+1]=arr[j]; } arr[j+1]=temp; } } } }

4.排序算法之希尔排序

package demo01; import java.util.Arrays; //排序算法之希尔排序 public class ShellSort { public static void main(String[] args) { // TODO Auto-generated method stub int[] arr=new int[] {4,7,9,5,7,4,2,7,2,0,1}; shellSort(arr); System.out.println(Arrays.toString(arr)); } public static void shellSort(int[] arr) { for(int d=arr.length/2;d>0;d/=2) { for(int i=d;i<arr.length;i++) { for(int j=i-d;j>=0;j-=d) { if(arr[j]>arr[j+d]) { int temp=arr[j]; arr[j]=arr[j+d]; arr[j+d]=temp; } } } } } }

5.排序算法之选择排序

package demo01; import java.util.Arrays; //排序算法之选择排序 public class SelectSort { public static void main(String[] args) { // TODO Auto-generated method stub int[] arr=new int[] {2,7,4,2,8,5,9,0}; selectSort(arr); System.out.println(Arrays.toString(arr)); } public static void selectSort(int[] arr) { for(int i=0;i<arr.length;i++) { int min=i; for(int j=i+1;j<arr.length;j++) { if(arr[min]>arr[j]) { min=j; } } if(i!=min) { int temp=arr[i]; arr[i]=arr[min]; arr[min]=temp; } } } }

6.排序算法之归并排序

package demo01; import java.util.Arrays; //排序算法之归并排序 public class MergeSort { public static void main(String[] args) { // TODO Auto-generated method stub int[] arr=new int[] {1,3,5,2,4,6,8,10}; mergeSort(arr,0,arr.length-1); System.out.println(Arrays.toString(arr)); } public static void mergeSort(int[] arr,int low,int high) { int middle=(low+high)/2; if(low<high) { mergeSort(arr,low,middle); mergeSort(arr,middle+1,high); merge(arr,low,middle,high); } } public static void merge(int[] arr,int low,int middle,int high) { int[] temp=new int[high-low+1]; int i=low; int j=middle+1; int index=0; while(i<=middle && j<=high) { if(arr[i]<=arr[j]) { temp[index]=arr[i]; i++; }else { temp[index]=arr[j]; j++; } index++; } while(i<=middle) { temp[index]=arr[i]; i++; index++; } while(j<=high) { temp[index]=arr[j]; j++; index++; } for(int k=0;k<temp.length;k++) { arr[k+low]=temp[k]; } } }

7.排序算法之基数排序

package demo01; import java.util.Arrays; //排序算法之基数排序 public class RadixSort { public static void main(String[] args) { // TODO Auto-generated method stub int[] arr=new int[] {23,56,45,32,897,125,735,34,54,892}; radixSort(arr); System.out.println(Arrays.toString(arr)); } public static void radixSort(int[] arr) { int max=Integer.MIN_VALUE; //找出数组中最大的数字 for(int i=0;i<arr.length;i++) { if(arr[i]>max) { max=arr[i]; } } //获取最大数字的长度 int maxLength=(max+"").length(); int[][] temp=new int[10][arr.length]; int[] counts=new int[10]; for(int i=0,n=1;i<maxLength;i++,n*=10) { for(int j=0;j<arr.length;j++) { int ys=arr[j]/n%10; temp[ys][counts[ys]]=arr[j]; counts[ys]++; } int index=0; for(int k=0;k<counts.length;k++) { if(counts[k]!=0) { for(int h=0;h<counts[k];h++) { arr[index]=temp[k][h]; index++; } counts[k]=0; } } } } }

8.基数排序之队列实现

package demo01; import java.util.Arrays; //基数排序之队列实现 class MyQueue { int[] elements; public MyQueue() { elements=new int[0]; } public void add(int element) { int[] newArr=new int[elements.length+1]; for(int i=0;i<elements.length;i++) { newArr[i]=elements[i]; } newArr[elements.length]=element; elements=newArr; } public int poll() { int element=elements[0]; int[] newArr=new int[elements.length-1]; for(int i=0;i<newArr.length;i++) { newArr[i]=elements[i+1]; } elements=newArr; return element; } public boolean isEmpty() { return elements.length==0; } } public class RadixQueueSort { public static void main(String[] args) { // TODO Auto-generated method stub int[] arr=new int[] {23,56,45,32,897,125,735,34,54,892}; radixSort(arr); System.out.println(Arrays.toString(arr)); } public static void radixSort(int[] arr) { int max=Integer.MIN_VALUE; //找出数组中最大的数字 for(int i=0;i<arr.length;i++) { if(arr[i]>max) { max=arr[i]; } } //获取最大数字的长度 int maxLength=(max+"").length(); MyQueue[] temp=new MyQueue[10]; for(int i=0;i<temp.length;i++) { temp[i]=new MyQueue(); } for(int i=0,n=1;i<maxLength;i++,n*=10) { for(int j=0;j<arr.length;j++) { int ys=arr[j]/n%10; temp[ys].add(arr[j]); } int index=0; for(int k=0;k<temp.length;k++) { while(!temp[k].isEmpty()) { arr[index]=temp[k].poll(); index++; } } } } }

9.排序算法之堆排序

package demo01; import java.util.Arrays; //排序算法之堆排序 public class HeapSport { public static void main(String[] args) { // TODO Auto-generated method stub int[] arr=new int[] {9,6,8,7,0,1,10,4,2}; heapSort(arr); System.out.println(Arrays.toString(arr)); } public static void heapSort(int[] arr) { //开始位置是最后一个非叶子节点，即最后一个节点的父节点 int start=(arr.length-1)/2; for(int i=start;i>=0;i--) { maxHeap(arr,arr.length,i); } for(int i=arr.length-1;i>0;i--) { int temp=arr[0]; arr[0]=arr[i]; arr[i]=temp; maxHeap(arr,i,0); } } public static void maxHeap(int[] arr,int size,int index) { int leftNode=2*index+1; //左子节点 int rightNode=2*index+2; //右子节点 int max=index; //和两个子节点分别对比找出最大的节点 if(leftNode<size&&arr[leftNode]>arr[max]) { max=leftNode; } if(rightNode<size&&arr[rightNode]>arr[max]) { max=rightNode; } //交换位置 if(max!=index) { int temp=arr[index]; arr[index]=arr[max]; arr[max]=temp; //交换位置以后可能会破坏之前排好的堆所以重新调整 maxHeap(arr,size,max); } } }