数组中的常见算法

 1 package package1_Array;
 2 /**
 3  * 二分查找
 4  * 前提：有序数组
 5  * 时间复杂度：O(log(n))
 6  */
 7 public class array_exe8 {
 8     public static void main(String[] args) {
 9         int[] arr = new int[]{-99,-54,-2,0,2,33,43,256,999};////arr必须有序
10         System.out.println(BinarySearch(arr,-2));
11 
12     }
13     public static int BinarySearch(int[] arr,int num){//在有序数组中查找num的索引
14         boolean Flag = false;
15         int low = 0,high = arr.length-1;
16         while(low <= high){
17             int mid = (high + low)/2;
18             if(arr[mid] < num){
19                 low = mid+1;
20             }else if(arr[mid] > num){
21                 high = mid-1;
22             }else{
23                 return mid;
24             }
25         }
26         return -1;//找不到指定的元素则返回-1
27     }
28 }

 1 package package1_Array.array_Sort;
 2 import java.util.Arrays;
 3 
 4 //快速排序
 5 //思想：分而治之
 6 //假设我们现在需要对数组做增序排序
 7 public class QuickSort {
 8     public static void main(String[] args) {
 9         int arr[]=new int[]{3,1,-9,12,54,78,0,100,-10};
10         QS(arr,0,arr.length-1);
11         System.out.println(Arrays.toString(arr));//[-10, -9, 0, 1, 3, 12, 54, 78, 100]
12     }
13 
14     public static void QS(int[] arr,int s,int t){
15         if(s<t){//类似树的前序遍历
16             int i=Partition(arr,s,t);
17             QS(arr,s,i-1);
18             QS(arr,i+1,t);
19         }
20     }
21 
22     public  static int Partition(int arr[],int low,int high){
23         int temp = arr[low];//每次选择下标为low的元素作为划分的基准
24         while(low < high){
25             while(low < high && arr[high] > temp){//先移动high,从右往左找比temp小的数组元素的下标
26                 high--;
27             }
28             if(low < high){
29                 arr[low] = arr[high];//如果没有越界，则做填充，换low移动
30                 low++;
31             }
32             while(low < high && arr[low] < temp){//移动low,从左往右找比temp大的数组元素的下标
33                 low++;
34             }
35             if(low < high){//如果没有越界，则做填充，换high移动
36                 arr[high] = arr[low];
37                 high--;
38             }
39         }
40         arr[low] = temp;//把temp填充到此次划分的位置
41         return low;//返回划分的位置下标
42     }
43 }