1.冒泡排序(Bubble Sort)
importjava.util.Arrays;//冒泡排序publicclassBubbleSort_01{publicstaticvoidmain(String[] args){int a[]={3,44,38,5,47,15,36,26,27,2,46,4,19,50,48};//记录比较次数int count=0;//i=0,第一轮比较for(int i=0; i< a.length-1; i++){//第一轮，两两比较for(int j=0; j< a.length-1-i; j++){if(a[j]>a[j+1]){int temp=a[j];
a[j]=a[j+1];
a[j+1]=temp;}
count++;}}System.out.println(Arrays.toString(a));//[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]System.out.println("一共比较了："+count+"次");//一共比较了：105次}}冒泡排序的优化1:
importjava.util.Arrays;publicclassBubbleSort1_01{publicstaticvoidmain(String[] args){int a[]={3,44,38,5,47,15,36,26,27,2,46,4,19,50,48};int count=0;for(int i=0; i< a.length-1; i++){boolean flag=true;for(int j=0; j< a.length-1-i; j++){if(a[j]>a[j+1]){int temp=a[j];
a[j]=a[j+1];
a[j+1]=temp;
flag=false;}
count++;}if(flag){break;}}System.out.println(Arrays.toString(a));// [2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]System.out.println("一共比较了："+count+"次");//一共比较了：95次}}2.选择排序(Select Sort)
importjava.util.Arrays;//选择排序:先定义一个记录最小元素的下标，然后循环一次后面的，找到最小的元素，最后将他放到前面排序好的序列。publicclassSelectSort_02{publicstaticvoidmain(String[] args){int a[]={3,44,38,5,47,15,36,26,27,2,46,4,19,50,48};for(int i=0; i< a.length-1; i++){int index=i;//标记第一个为待比较的数for(int j= i+1; j< a.length; j++){//然后从后面遍历与第一个数比较if(a[j]<a[index]){//如果小,就交换最小值
index=j;//保存最小元素的下标}}//找到最小值后，将最小的值放到第一的位置，进行下一遍循环int temp=a[index];
a[index]=a[i];
a[i]=temp;}System.out.println(Arrays.toString(a));//[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]}}3.插入排序(Insert Sort)
importjava.util.Arrays;//插入排序:定义一个待插入的数，再定义一个待插入数的前一个数的下标，然后拿待插入数与前面的数组一一比较，最后交换。publicclassInsertSort_03{publicstaticvoidmain(String[] args){int a[]={3,44,38,5,47,15,36,26,27,2,46,4,19,50,48};for(int i=0; i< a.length; i++){//长度不减1，是因为要留多一个位置方便插入数//定义待插入的数int insertValue=a[i];//找到待插入数的前一个数的下标int insertIndex=i-1;while(insertIndex>=0&& insertValue<a[insertIndex]){//拿a[i]与a[i-1]的前面数组比较
a[insertIndex+1]=a[insertIndex];
insertIndex--;}
a[insertIndex+1]=insertValue;}System.out.println(Arrays.toString(a));//[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]}}4.希尔排序(Shell Sort)
importjava.util.Arrays;//希尔排序：插入排序的升级publicclassShellSort_04{publicstaticvoidmain(String[] args){int a[]={3,44,38,5,47,15,36,26,27,2,46,4,19,50,48};int count=0;//比较次数for(int gap=a.length/2; gap>0; gap= gap/2){//将整个数组分为若干个子数组for(int i= gap; i< a.length; i++){//遍历各组的元素for(int j= i- gap; j>=0; j=j-gap){//交换元素if(a[j]>a[j+gap]){int temp=a[j];
a[j]=a[j+gap];
a[j+gap]=temp;
count++;}}}}System.out.println(count);//16System.out.println(Arrays.toString(a));//[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]}}5.快速排序(Quick Sort)
importjava.util.Arrays;//快速排序：冒泡排序的升华版publicclassQuickSort_05{publicstaticvoidmain(String[] args){//int a[]={50,1,12,2};int a[]={3,44,38,5,47,15,36,26,27,2,46,4,19,50,48};quicksort(a,0,a.length-1);System.out.println(Arrays.toString(a));}privatestaticvoidquicksort(int[] a,int low,int high){int i,j;if(low>high){return;}
i=low;
j=high;int temp=a[low];//基准位,low=length时，会报异常，java.lang.ArrayIndexOutOfBoundsException: 4 ，所以必须在if判断后面,就跳出方法。while(i<j){//先从右边开始往左递减，找到比temp小的值才停止while( temp<=a[j]&& i<j){
j--;}//再看左边开始往右递增，找到比temp大的值才停止while( temp>=a[i]&& i<j){
i++;}//满足 i<j 就交换,继续循环while(i<j)if(i<j){int t=a[i];
a[i]=a[j];
a[j]=t;}}//最后将基准位跟 a[i]与a[j]相等的位置，进行交换,此时i=j
a[low]=a[i];
a[i]=temp;//左递归quicksort(a, low, j-1);//右递归quicksort(a, j+1, high);}}6.归并排序(Merge Sort)
importjava.util.Arrays;//归并排序publicclassMergeSort_06{publicstaticvoidmain(String[] args){int a[]={3,44,38,5,47,15,36,26,27,2,46,4,19,50,48};//int a[]={5,2,4,7,1,3,2,2};int temp[]=newint[a.length];mergesort(a,0,a.length-1,temp);System.out.println(Arrays.toString(a));}privatestaticvoidmergesort(int[] a,int left,int right,int[] temp){//分解if(left<right){int mid=(left+right)/2;//向左递归进行分解mergesort(a, left, mid, temp);//向右递归进行分解mergesort(a, mid+1, right, temp);//每分解一次便合并一次merge(a,left,right,mid,temp);}}/**
*
* @param a 待排序的数组
* @param left 左边有序序列的初始索引
* @param right 右边有序序列的初始索引
* @param mid 中间索引
* @param temp 做中转的数组
*/privatestaticvoidmerge(int[] a,int left,int right,int mid,int[] temp){int i=left;//初始i，左边有序序列的初始索引int j=mid+1;//初始化j，右边有序序列的初始索引（右边有序序列的初始位置即中间位置的后一位置）int t=0;//指向temp数组的当前索引，初始为0//先把左右两边的数据（已经有序）按规则填充到temp数组//直到左右两边的有序序列，有一边处理完成为止while(i<=mid&& j<=right){//如果左边有序序列的当前元素小于或等于右边的有序序列的当前元素，就将左边的元素填充到temp数组中if(a[i]<=a[j]){
temp[t]=a[i];
t++;//索引向后移
i++;//i后移}else{//反之，将右边有序序列的当前元素填充到temp数组中
temp[t]=a[j];
t++;//索引向后移
j++;//j后移}}//把剩余数据的一边的元素填充到temp中while(i<=mid){//此时说明左边序列还有剩余元素//全部填充到temp数组
temp[t]=a[i];
t++;
i++;}while(j<=right){//此时说明左边序列还有剩余元素//全部填充到temp数组
temp[t]=a[j];
t++;
j++;}//将temp数组的元素复制到原数组
t=0;int tempLeft=left;while(tempLeft<=right){
a[tempLeft]=temp[t];
t++;
tempLeft++;}}}7.堆排序(Heap Sort)
堆排序
第一步：构建初始堆buildHeap， 使用sink(arr,i, length)调整堆顶的值;
第二步：将堆顶元素下沉 目的是将最大的元素浮到堆顶来，然后使用sink(arr, 0,length)调整;
堆排序图解：链接
publicclassHeap_Sort_07{publicstaticvoidmain(String[] args){int a[]={3,44,38,5,47,15,36,26,27,2,46,4,19,50,48};sort(a);System.out.println(Arrays.toString(a));}publicstaticvoidsort(int[] arr){int length= arr.length;//构建堆buildHeap(arr,length);for(int i= length-1; i>0; i--){//将堆顶元素与末位元素调换int temp= arr[0];
arr[0]= arr[i];
arr[i]= temp;//数组长度-1 隐藏堆尾元素
length--;//将堆顶元素下沉 目的是将最大的元素浮到堆顶来sink(arr,0,length);}}privatestaticvoidbuildHeap(int[] arr,int length){for(int i= length/2; i>=0; i--){sink(arr,i, length);}}privatestaticvoidsink(int[] arr,int index,int length){int leftChild=2* index+1;//左子节点下标int rightChild=2* index+2;//右子节点下标int present= index