JavaSE——【算法】实现对数组的普通快速排序、随机快速排序、二分法查找及冒泡排序

要求
实现上述两个算法
统计算法的运行时间
分析性能差异，作出总结
一：普通快速排序

public class QuickSort1 {
    public static void QuickSort(int []A,int l,int r){
    int temp;int i = l;int j = r;if(l<r){
    temp = A[i];while(i != j){
    while(i<j && A[j] >= temp){
    --j;}A[i] = A[j];while(i<j && A[i] <= temp){
    ++i;}A[j] = A[i];}A[i] = temp;QuickSort(A, l, i-1);QuickSort(A, i+1, r);}}

二：随机快速排序

public static void exchange(int[] array,int a,int b){
    int temp = 0;temp = array[a];array[a] = array[b];array[b] = temp;}public static int random_patition(int[] A,int left,int right){
    int temp = 0;int i = left-1;Random random = new Random();int k = left + random.nextInt(right - left);exchange(A,k,right);temp = A[right];//找到所有比temp小的数，放在temp左边for(int j = left ; j<right ; j++){
    if(A[j] <= temp){
    i++;exchange(A,i,j);}}//将枢轴放回原位exchange(A,i+1, right);return i+1;}public static void QuickSort(int[] A,int l,int r){
    if(l<r){
    int dot = random_patition(A, l, r);QuickSort(A, l, dot-1);QuickSort(A, dot+1, r);}}

三：冒泡排序

public class BubbleSort {
    public static void main(String[] args) {
    //冒泡排序算法int[] numbers=new int[]{
    1,5,8,2,3,9,4};//需进行length-1次冒泡for(int i=0;i<numbers.length-1;i++){
    for(int j=0;j<numbers.length-1-i;j++){
    if(numbers[j]>numbers[j+1]){
    int temp=numbers[j];numbers[j]=numbers[j+1];numbers[j+1]=temp;}}}System.out.println("从小到大排序后的结果是:");for(int i=0;i<numbers.length;i++){
    System.out.print(numbers[i]+" ");}
}

四：比较普通排序和随机排序的时间差的main函数

public static void main(String[] args){
    int[] A = new int[20000];int[] A_copy = new int[20000];//生成两个随机数组
// System.out.println("排序之前的20000个数是：");
// Random random = new Random();
// for(int i = 0; i<A.length;i++){
    
// A[i] = (int)random.nextInt(100000);
// A_copy[i] = A[i];
// System.out.print(A[i]+" ");
// if(i%10 == 0&&i!=0){
    
// System.out.print("\n");
// }
// }//生成两个1-20000的有序数组，目的：比较当数组有序时哪个排序速度快for(int i = 0;i<A.length;i++){
    A[i] = i;A_copy[i] = i;}//普通快速排序算法Date before1 = new Date();long before1_QuickSort = before1.getTime();QuickSort(A,0,1999);Date after1 = new Date();long after1_QuickSort = after1.getTime();long time1 = after1_QuickSort - before1_QuickSort;//随机快速排序算法Date before2 = new Date();long before2_QuickSort = before2.getTime();QuickSort2.QuickSort(A_copy, 0, 1999);Date after2 = new Date();long after2_QuickSort = after2.getTime();long time2 = after2_QuickSort - before2_QuickSort;System.out.println("\n普通快速排序之后的20000个数是:");for(int k = 0;k<A.length;k++){
    System.out.print(A[k]+" ");if(k%10 == 0&&k!=0){
    System.out.print("\n");}}System.out.println("\n普通快速排序算法运行时间："+time1);System.out.println("随机快速排序算法运行时间："+time2);System.out.println("相差"+(time1-time2));}

二分查找代码实现

普通查找和二分查找

普通查找

原理：遍历数组，获取每一个元素，然后判断当前遍历的元素是否和要查找的元素相同，如果相同就返回该元素的索引。如果没有找到，就返回一个负数作为标识(一般是-1)

二分查找

原理: 每一次都去获取数组的中间索引所对应的元素，然后和要查找的元素进行比对，如果相同就返回索引；

如果不相同，就比较中间元素和要查找的元素的值；

如果中间元素的值大于要查找的元素，说明要查找的元素在左侧，那么就从左侧按照上述思想继续查询(忽略右侧数据)；

如果中间元素的值小于要查找的元素，说明要查找的元素在右侧，那么就从右侧按照上述思想继续查询(忽略左侧数据)；

二分查找对数组是有要求的,数组必须已经排好序

public static void main(String[] args) {
    int[] arr = {
    10, 14, 21, 38, 45, 47, 53, 81, 87, 99};int index = binarySerach(arr, 38);System.out.println(index);
}
/*** 二分查找方法* @param arr 查找的目标数组* @param number 查找的目标值* @return 找到的索引,如果没有找到返回-1*/
public static int binarySerach(int[] arr, int number) {
    int start = 0;int end = arr.length - 1;while (start <= end) {
    int mid = (start + end) / 2;if (number == arr[mid]) {
    return mid + 1;} else if (number < arr[mid]) {
    end = mid - 1;} else if (number > arr[mid]) {
    start = mid + 1;}}return -1;  //如果数组中有这个元素，则返回
}