交换排序
1、冒泡排序
2、快速排序【可多种方式优化】
交换排序
1、冒泡排序
afsaf
package sort; public class BubbleSort { //普通冒泡排序 public static void sortA(int[] arr,int n){ int tmp;//临时变量 int compare=0;//比较趟数 int count=0;//比较次数 int change=0;//交换位置次数 for(int i=0;i<n-1;i++){ compare++; for(int j=n-1;j>i;j--){//冒泡排序，从后往前 count++; if(arr[j-1]>arr[j]){ change++; tmp=arr[j-1]; arr[j-1]=arr[j]; arr[j]=tmp; } } } System.out.println("比较趟数"+compare); System.out.println("比较次数"+count); System.out.println("交换位置次数"+change); } //改进后的冒泡排序 public static void sortMore(int[] arr,int n){ int tmp;//临时变量 int compare=0;//比较趟数 int count=0;//比较次数 int change=0;//交换位置次数 boolean flag=true; for(int i=0;i<n-1;i++){ compare++; flag=false; for(int j=n-1;j>i;j--){//冒泡排序，从后往前 count++; if(arr[j-1]>arr[j]){ change++; tmp=arr[j-1]; arr[j-1]=arr[j]; arr[j]=tmp; flag=true;//某一趟中存在元素的交换，说明未排好序 } } //判断是否还存在比较的情况 if(!flag){//某一趟中不存在元素的交换，说明已经排好序了 break;//结束for循环 } // if(flag==false){ // break;//结束for循环 // } // System.out.println("比较ing.."); } System.out.println("比较趟数"+compare); System.out.println("比较次数"+count); System.out.println("交换位置次数"+change); } public static void main(String[] args) { //普通冒泡排序 int arr[]={4,5,6,3,1,9,0,8,7,2}; sortA(arr,arr.length); System.out.println("排序后："); for(int i=0;i<arr.length;i++){ System.out.print(arr[i]+" "); } System.out.println("\n------------------------------------------"); //改进后的冒泡排序 int arr2[]={4,5,6,3,1,9,0,8,7,2}; sortMore(arr2,arr2.length); System.out.println("排序后："); for(int i=0;i<arr2.length;i++){ System.out.print(arr2[i]+" "); } } }2、快速排序【优化】
package sort; //快速排序 public class QuickSort { //交换两个元素的值 public static void swap(int[] arr,int low,int high){ int temp=arr[low]; arr[low]=arr[high]; arr[high]=temp; } //确立基本点+排序 public static int partition(int[] arr,int low,int high){ int point=low;//基本点的值 //目标 基本点 ，左边的值，都比arr[point]小； 右边的值，都比arr[point]大 while(low<high){ //右边扫描，小的值，交换操作 while(low<high && arr[point]<arr[high]){ high--;//从右边开始扫描，过滤比arr[point]大的值，知道遇到比arr[point]小的值 } swap(arr,point,high);//交换元素位置 point=high;//大值位置【point记录--交换后的位置】 //左边扫描，打的值，交换操作 while(low<high && arr[point]>arr[low]){ low++; } swap(arr,low,point);//交换元素位置 point=low;//小值位置【point记录--交换后的位置】 } return point;//【point记录--交换后的位置】 } public static void sort(int[] arr,int low,int high){ if(low<high){//循环终止条件 //确立基本点，进行排序【小于基本点的，放左边，大于基本点的，放右边】 int point=partition(arr,low,high); sort(arr,low,point-1);//左边遍历 // sort(arr,low,point);//左边遍历 sort(arr,point+1,high);//右边遍历 } } public static void main(String[] args) { int i; int a[] = { 5, 2, 6, 0, 3, 9, 1, 7, 4, 8 }; sort(a, 0,a.length-1); System.out.println("快速排序--排序后的结果是:"); for (i = 0; i < 10; i++) { System.out.print(a[i] + " "); } System.out.println("\n"); } }
