排序方法

排序方法

冒泡排序的应用

//数组 int score[] = {67, 69, 75, 88,124,1445,34}; //第一种方法 /*for(int i =0;i < score.length - 1;i++){ for(int j = 0;j < score.length - 1-i;j++) {// j开始等于0， if(score[j] < score[j+1]){ int temp = score[j]; score[j] = score[j+1]; score[j+1] = temp; } } } */ //第二种方法 for(int i =0;i < score.length - 1;i++){ for(int j = (score.length - 2);j >= i;j--) { if(score[j] < score[j+1]) { int temp = score[j]; score[j] = score[j+1]; score[j+1] = temp; } } } for (int x =0; x<score.length ; x++) { System.out.println(score[x]); } }

运行结果：

选择排序

int [] arr = {3,1,5,2,4,9,6,8,7}; System.out.print("原始数组是："); for(int a :arr) { System.out.print(a+","); } selectSort(arr); System.out.println(); System.out.print("排序之后的数组是："); for(int i = 0;i<arr.length;i++) { System.out.print(arr[i]+","); } } public static void selectSort(int [] x) { if(x.length!=0) { int temp = 0; for(int i = 0;i<x.length;i++) { int min = i; for(int j = i;j<x.length;j++) { if(x[j] <= x[min]) { min = j; } } temp = x[min]; x[min] = x[i]; x[i] = temp; } } }

运行结果： 二分搜索法

非递归方法

public static int search(int key,int[] arr){ int start=0; int end=arr.length-1; while(start<=end){ int mid=start+(end-start)/2; if(key<arr[mid]){ end=mid-1; }else if(key>arr[mid]){ start=mid+1; }else{ return mid; } } return -1; }

递归方法

public static int search2(int key,int[] arr,int start,int end){ if(start >end){ return -1; } int mid=start+(end-start)/2; if(key<arr[mid]){ return search2(key,arr,start,mid-1); }else if(key>arr[mid]){ return search2(key,arr,mid+1,end); }else{ return mid; } }

主方法运行结构

public static void main(String[] args) { int arr[]={0,1,3,5,6,7,8,8,9}; int resultPosition=search1(3,arr); int result=search2(3,arr,0,arr.length-1); System.out.println("3这个所在位置："+resultPosition); System.out.println("3这个所在位置："+result); }

运行结果：

3这个所在位置：2 3这个所在位置：2

希尔排序 对于这个排序方法还是没有特别理解，就找到一下原理内容如下：

（1）希尔排序（shell sort）这个排序方法又称为缩小增量排序，是1959年D·L·Shell提出来的。该方法的基本思想是：设待排序元素序列有n个元素，首先取一个整数increment（小于n）作为间隔将全部元素分为increment个子序列，所有距离为increment的元素放在同一个子序列中，在每一个子序列中分别实行直接插入排序。然后缩小间隔increment，重复上述子序列划分和排序工作。直到最后取increment=1，将所有元素放在同一个子序列中排序为止。 （2）由于开始时，increment的取值较大，每个子序列中的元素较少，排序速度较快，到排序后期increment取值逐渐变小，子序列中元素个数逐渐增多，但由于前面工作的基础，大多数元素已经基本有序，所以排序速度仍然很快。