基本排序算法

如果遇到相等的值不进行交换，那这种排序方式是稳定的排序方式

1.冒泡排序

比较两个相邻的元素，将值大的元素交换到右边

public static void sort1(int[] arr){ int t; for (int i = 0; i <arr.length-1 ; i++) { for(int j=0;j<arr.length-i-1;j++){ if(arr[j]>arr[j+1]){ t=arr[j+1]; arr[j+1]=arr[j]; arr[j]=t; } } } System.out.println(arr.length); for (int i = 0; i < arr.length; i++) { System.out.print(arr[i]); } }

2.选择排序

从头至尾扫描序列，找出最小的一个元素，和第一个元素交换，接着从剩下的元素中继续这种选择和交换方式，最终得到一个有序序列

public static void sort2(int[] arr){ int t; for(int i=0;i<arr.length-1;i++){ for(int j=i+1;j<arr.length;j++){ if (arr[i] > arr[j]) { t=arr[i]; arr[i]=arr[j]; arr[j]=t; } } } for (int i = 0; i < arr.length; i++) { System.out.print(arr[i]); } }

3.二分查找

public static void sort3(int[] arr,int value){ int start=0,end=arr.length-1; int count=0; int mid=(start+end)/2; while(arr[mid]!=value){ if(arr[mid]>value){ end=mid; count++; }else if(arr[mid]<value){ start=mid; count++; } mid=(start+end)/2; if(start>end){ return ; } } System.out.println("查询次数:"+count+"位置:"+mid); }

4.快速排序

快速排序之所比较快，每次交换是跳跃式的每次排序的时候设置一个基准点，将小于等于基准点的数全部放到基准点的左边，将大于等于基准点的数全部放到基准点的右边

public static void sort4(int[] arr,int low,int high){ int i,j,temp,t; if(low>high){ return; } i=low; j=high; //基准位 temp=arr[low]; while(i<j){ //先右边往左边递减 while(arr[j]>=temp&&i<j){ j--; } //再左边往右边递增 while(arr[i]<=temp&&i<j){ i++; } //满足条件则交换 if(i<j){ t=arr[i]; arr[i]=arr[j]; arr[j]=t; } } //i=j,交换基准位 arr[low]=arr[i]; arr[i]=temp; //递归基准位左边的数组 sort4(arr,low,j-1); //i递归基准位右边的数组 sort4(arr,j+1,high); }

5.测试Test

public class test { public static void main(String[] args) { int[] arr={5,1,3,2,4}; int[] arr1={1,2,3,4,5,6,7,8,9,10}; sort1(arr);//冒泡 System.out.println(); sort2(arr);//选择 System.out.println(); sort3(arr1,6);//二分查找 System.out.println(); sort4(arr,0,arr.length-1);//快速排序 for (int i : arr) { System.out.print(i+","); } }

6.堆排序

堆排序的基本思想是：将待排序序列构造成一个大顶堆，此时，整个序列的最大值就是堆顶的根节点。将其与末尾元素进行交换，此时末尾就为最大值。然后将剩余n-1个元素重新构造成一个堆，这样会得到n个元素的次小值。如此反复执行，便能得到一个有序序列了