我把冒泡和选择,折半都写了,你对比着看一下- import java.util.Arrays;
- import java.util.Random;
- public class Sort {
- //写冒泡排序的时候,想到还有其他的排序方法,就顺道写了选择排序,折半查找
-
- public static void main(String [] args){
- Sort s = new Sort();
- int [] arr = s.randomArray();
- // //冒泡排序,降序打印
- // s.bubbleSortASC(arr);
- // //冒泡排序,升序打印
- // s.bubbleSortDESC(arr);
- //选择排序,升序打印
- // s.selectSortAEC(arr);
- //优化后的选择排序,降序打印
- // s.selectSortOptDESC(arr);
-
-
- // int [] arr2 = {1, 3, 5, 7, 9, 11, 13, 15, 17, 19};
- // int key = 12;
- //自己写的折半查找
- // int find = s.halfOfSearch(arr2, key);
- //调用API的折半查找
- // int find2 = Arrays.binarySearch(arr2, key);
- // System.out.println("find: " + find);
- // System.out.println("find: " + find2);
-
- }
- //打印排序后
- public static void sortPrint(int []arr){
- System.out.println("sortPrint:");
- for(int i : arr){
- System.out.print( " " + i + " ");
- }
- System.out.println("");
- }
- //打印排序前
- public static void beforePrint(int []arr){
- System.out.println("beforePrint:");
- for(int i : arr){
- System.out.print( " " + i + " ");
- }
- System.out.println("");
- }
-
- //随机取值
- public int[] randomArray(){
- Random r = new Random();
- int arrayLength = 10;
- int [] arr = new int[arrayLength];
- for(int i = 0; i < arrayLength; i++){
- arr[i] = r.nextInt(100);
- }
- beforePrint(arr);
- return arr;
- }
- //交换位置
- public static void swap(int a, int b, int []arr){
- arr[a] ^= arr[b];
- arr[b] ^= arr[a];
- arr[a] ^= arr[b];
- }
- //冒泡排序,升序打印
- public void bubbleSortASC(int []arr){
-
- for(int i = 0, len = arr.length; i < len - 1; i++){
- for(int j = 0; j < len - i - 1; j++){
- if(arr[j] < arr[j + 1]){
- swap(j, j + 1, arr);
- }
- }
- }
- sortPrint(arr);
- }
- //冒泡排序,降序打印
- public void bubbleSortDESC(int []arr){
- for(int i = 0, len = arr.length; i < len - 1; i++){
- for(int j = 0; j < len - i - 1; j++){
- if(arr[j] > arr[j + 1]){
- swap(j, j + 1, arr);
- }
- }
- }
- sortPrint(arr);
- }
- //选择排序,升序打印
- public void selectSortAEC(int []arr){
- for(int i = 0; i < arr.length - 1; i++){
- for(int j = i; j < arr.length - 1; j++){
- if(arr[i] > arr[j + 1]){
- swap(i, j + 1, arr);
- }
- }
- }
- sortPrint(arr);
- }
- //选择排序,降序打印
- public void selectSortDESC(int []arr){
- for(int i = 0; i < arr.length - 1; i++){
- for(int j = i; j < arr.length - 1; j++){
- if(arr[i] < arr[j + 1]){
- swap(i, j + 1, arr);
- }
- }
- }
- sortPrint(arr);
- }
- //优化后的选择排序,降序打印
- public void selectSortOptDESC(int []arr){
- for(int i = 0; i < arr.length - 1; i++){
- int num = arr[i];
- int index = i;
- for(int j = i + 1; j < arr.length; j++){
- if(num < arr[j]){
- num = arr[j];
- index = j;
- }
- }
- if(index != i){
- swap(i, index, arr);
- }
- }
- sortPrint(arr);
- }
- //折半查找
- public int halfOfSearch(int [] arr2,int key){
- int min = 0;
- int max = arr2.length - 1;
- int mid;
- while(min <= max){
- mid = (min + max) >> 1;
- if(arr2[mid] < key){
- min = mid + 1;
- }else if(arr2[mid] > key){
- max = mid - 1;
- }else{
- return arr2[mid];
- }
- }
- return - min - 1;
- }
- }
复制代码 |