建分类信息网站,wordpress增加英文,苏州保洁公司收费价格表,电工培训1. 排序算法代码实现 /*** ascending sort* 外层循环边界条件#xff1a;总共需要冒泡的轮数--每一轮都将最大或最小的数冒泡到最后* 内层循环边界条件#xff1a;冒泡数字移动的边界--最终数字需冒泡到此处* 时间复杂度#xff1a;O(n^2)* param arr*/
public static vo…1. 排序算法代码实现 /*** ascending sort* 外层循环边界条件总共需要冒泡的轮数--每一轮都将最大或最小的数冒泡到最后* 内层循环边界条件冒泡数字移动的边界--最终数字需冒泡到此处* 时间复杂度O(n^2)* param arr*/
public static void bubbleSort(int[] arr) {if (arr null) {throw new RuntimeException(Input arr is null!);}for(int i 0; i arr.length - 1; i) {for(int j 0; j arr.length - 1 - i; j) { //冒泡相邻两数比较大的向后冒if(arr[j] arr[j1]) {int temp arr[j];arr[j] arr[j1];arr[j1] temp;}}}
}/*** 每次都将未排序数组中的最大或最小元素找出来和第一个元素交换位置* 时间复杂度O(n^2)* param arr*/
public static void selectSort(int[] arr) {if (arr null) {throw new RuntimeException(Input arr is null!);}for(int i 0; i arr.length - 1; i) {//寻找最小元素的下标避免频繁交换数组int min i;for(int j i 1; j arr.length; j) {if (arr[j] arr[min]) {min j;}}//将最小的元素交换到未排序数组的最前面int temp arr[i];arr[i] arr[min];arr[min] temp;}
}/*** 插入排序顺次从数组中选择一个数插入到前面已排序的数组中* 时间复杂度O(n)~O(n^2)* param arr*/
public static void insertSort(int[] arr) {if (arr null) {throw new RuntimeException(Input arr is null!);}for(int i 1; i arr.length; i) {int value arr[i];//插入的位置int j 0;//循环i前面的数若值比插入的值大则顺次向后移动for (j i - 1; j 0; j--) {if(arr[j] value) {arr[j1] arr[j];} else {break;}}arr[j1]value;}
}/*** 希尔排序插入排序的改进版也称缩小增量排序** param arr*/
public static void shellSort(int[] arr) {if (arr null) {throw new RuntimeException(Input arr is null!);}int length arr.length;//区间int gap 1;while(gap length) {gap gap * 3 1;}while(gap 0) {for(int i gap; i length; i) {int tmp arr[i];int j i -gap;//跨区间排序while(j 0 arr[j] tmp) {arr[jgap] arr[j];j - gap;}arr[j gap] tmp;}gap gap / 3;}
}/*** 归并排序--核心为分治法* 时间复杂度O(nlogn)* param arr*/
public static void mergeSort(int[] arr) {if (arr null) {throw new RuntimeException(Input arr is null!);}int[] tmpArr new int[arr.length];mSort(arr,tmpArr, 0, arr.length - 1);
}private static void mSort(int[] arr, int[] tmpArr, int startIndex, int endIndex) {//边界条件数组已不可再拆if (endIndex startIndex) {return;}//将数组对拆为前后两个数组int middleIndex startIndex (endIndex - startIndex)/2;mSort(arr, tmpArr, startIndex, middleIndex);mSort(arr, tmpArr, middleIndex 1, endIndex);merge(arr, tmpArr, startIndex, middleIndex, endIndex);
}private static void merge(int[] arr, int[] tmpArr, int startIndex, int middleIndex, int endIndex) {//将要合并的数组复制到临时数组for (int i startIndex; i endIndex; i) {tmpArr[i] arr[i];}//左边数组起始下标int left startIndex;//右边数组起始下标int right middleIndex 1;for(int k startIndex; k endIndex; k) { if (left middleIndex) {arr[k] tmpArr[right];} else if (right endIndex) {arr[k] tmpArr[left];} else if (tmpArr[left] tmpArr[right]) {arr[k] tmpArr[left];} else {arr[k] tmpArr[right];} }
}/*** 快速排序随机选取一个参考值将比参考值小的数移到数组前段大的值移到后段* 以参考值为临界点递归拆分数组直至数组不能拆分此时数组本身已排好序* 快速排序时间复杂度为O(nlogn)对于逆序数组复杂度退化为O(n^2)为了避免极端情况可随机选取参考值* param arr*/
public static void quickSort(int[] arr) {if (arr null) {throw new RuntimeException(Input arr is null!);}qSort(arr , 0, arr.length - 1);
}private static void qSort(int[] arr, int startIndex, int endIndex) {// 设置边界条件if (endIndex startIndex) {return;}// 将数组按参考值整理成比参考值小的前段和比参考值大的后段返回参考值的位置int refIndex partition(arr, startIndex, endIndex);// 参考值已确定排序后的位置不参与数组拆分if (refIndex startIndex) {qSort(arr, startIndex, refIndex - 1);}if (endIndex refIndex) {qSort(arr, refIndex 1, endIndex);}
}
private static int partition(int[] arr, int startIndex, int endIndex) {// 将数组中refValue的值与最后一个数交换随机选取参考值可避免时间复杂度退化为O(n^2)int refIndex startIndex new Random().nextInt(endIndex - startIndex 1);// 深坑当两个数指向同一个时会影响异或结果if (refIndex ! endIndex) {arr[endIndex] arr[endIndex] ^ arr[refIndex];arr[refIndex] arr[endIndex] ^ arr[refIndex];arr[endIndex] arr[endIndex] ^ arr[refIndex];}// 分组下标int partitionIndex startIndex - 1;// 数组最后一个值为参考值不参与循环for (int dataIndex startIndex; dataIndex endIndex; dataIndex) {// 与参考值进行比较若比参考值小则移动到数组前面if ((arr[dataIndex] arr[endIndex]) ) {// 始终指向最后一个确定比参考值小的值partitionIndex;// 如果当前数据的位置与参考下标不一致将此值与参考下标指向的值交换保证小的值交换到前面if (partitionIndex ! dataIndex) {arr[dataIndex] arr[dataIndex] ^ arr[partitionIndex] ;arr[partitionIndex] arr[dataIndex] ^ arr[partitionIndex];arr[dataIndex] arr[dataIndex] ^ arr[partitionIndex];} }}// 将参考值交换到指定位置partitionIndex;if (partitionIndex ! endIndex) {arr[endIndex] arr[endIndex] ^ arr[partitionIndex] ;arr[partitionIndex] arr[endIndex] ^ arr[partitionIndex];arr[endIndex] arr[endIndex] ^ arr[partitionIndex];}return partitionIndex;
}/*** 堆排序--最大堆实现* 时间复杂度O(nlogn)* param arr*/
public static void heapSort(int[] arr) {if (arr null) {throw new RuntimeException(Input arr is null!);}int length arr.length;//构建堆buildHeap(arr, length);for (int i length - 1; i 0; i--) {//将堆元素与末位元素调换int temp arr[0];arr[0] arr[i];arr[i] temp;//数组长度-1 隐藏堆尾元素length--;//将堆顶元素下沉目的是将最大的元素浮到堆顶来sink(arr, 0, length);}
}
private static void buildHeap(int[] arr, int length) {for (int i length / 2; i 0; i--) {sink(arr, i , length);}
}private static void sink(int[] arr, int index, int length) {//左子节点下标int leftChild 2 * index 1;//右子节点下标int rigthChild 2 * index 2;//要调整的节点下标int present index;//下沉左边if (leftChild length arr[leftChild] arr[present]) {present leftChild;}//下沉右边if (rigthChild length arr[rigthChild] arr[present]) {present rigthChild;}//如果下标不相等证明调换过了if (present ! index) {//交换值int temp arr[index];arr[index] arr[present];arr[present] temp;//继续下沉sink(arr, present, length);}
}/*** 计数排序--时间复杂度为O(nm)空间大小取决于数组值时间复杂度为O(n)* 问题点数组中不能有负数否则会抛出越界异常* param arr*/
public static void countSort(int[] arr) {if (arr null) {throw new RuntimeException(Input arr is null!);}//找出数组中的最大值int max arr[0];for(int i 1; i arr.length; i) {if (arr[i] 0) {throw new RuntimeException(Cannot use countsort! Array contains negative number.);}if (max arr[i]) {max arr[i];}}//利用最大值构建一个数组用空间换时间int[] countArr new int[max 1];//计数for (int i 0; i arr.length; i) {countArr[arr[i]];}int index 0;for (int i 0; i countArr.length; i) {while (countArr[i] 0) {arr[index] i;countArr[i]--;}}
}/*** 桶排序--类似于Hash分桶策略* 良好的分桶策略可实现O(n)时间复杂度* param arr*/
public static void bucketSort(int[] arr) {if (arr null) {throw new RuntimeException(Input arr is null!);}//最大最小值int max arr[0];int min arr[0];int length arr.length;for (int i 1; i length; i) {if (arr[i] max) {max arr[i];} else if (arr[i] min) {min arr[i];}}//最大值与最小值的差int diff max - min;//桶列表ArrayListArrayListInteger bucketList new ArrayList();for (int i 0; i length; i) {bucketList.add(new ArrayList());}//每个桶的存数区间float section (float)diff / (float)(length -1);//数据入桶for (int i 0; i length; i) {//当前数除以区间得出存放桶的位置 减1后得出桶的下标int num (int) (arr[i] / section) - 1;if (num 0) {num 0;}bucketList.get(num).add(arr[i]);}//桶内排序for (int i 0; i bucketList.size(); i) {Collections.sort(bucketList.get(i));}//写入数据int index 0;for (ArrayListInteger arrayList: bucketList) {for (int value : arrayList) {arr[index] value;index;}}
}/*** 基数排序* param arr*/
public static void radixSort(int[] arr) {if (arr null) {throw new RuntimeException(Input arr is null!);}int length arr.length;//最大值int max arr[0];for(int i 0;i length;i){if(arr[i] max){max arr[i];}}//当前排序位置int location 1;//桶列表ArrayListArrayListInteger bucketList new ArrayList();//长度为10 装入余数0-9的数据for(int i 0; i 10; i){bucketList.add(new ArrayList());}while(true){//判断是否排完int dd (int)Math.pow(10, (location - 1));if(max dd){break;}//数据入桶for(int i 0; i length; i){//计算余数 放入相应的桶int number ((arr[i] / dd) % 10);bucketList.get(number).add(arr[i]);}//写回数组int nn 0;for (int i0;i10;i){int size bucketList.get(i).size();for(int ii 0;ii size;ii ){arr[nn] bucketList.get(i).get(ii);}bucketList.get(i).clear();}location;}
}2. 查询算法代码实现 /*** 顺序查找即为遍历数组时间复杂度为O(n)* param arr* param value* return*/
public static int sequentialSearch(int[] arr, int value) {if (arr null) {throw new RuntimeException(Input arr is null!);}for (int i 0; i arr.length; i) {if (arr[i] value) {return i;}}return -1;
}/*** 二分查找针对以升序排列的数组进行每次取数组的中间值进行查找* 时间复杂度为O(logn)* param arr* param value* return*/
public static int binarySearch(int[] arr, int value) {if (arr null) {throw new RuntimeException(Input arr is null!);}int low 0;int high arr.length - 1;int mid 0;while (low high) {mid (low high)/2;if (arr[mid] value) {return mid;} else if (arr[mid] value) {high mid -1;} else {low mid 1;}}return -1;
}/*** 二分查找--递归实现* param arr 待查询数组* param value 查找目标值* param low 数组起始下标* param high 数组结束下标* return 目标值的下标*/
public static int binarySearchByRecursion(int[] arr, int value, int low, int high) {if (arr null) {throw new RuntimeException(Input arr is null!);}int mid low (high -low)/2;if (low high arr[mid] ! value) {return -1;}if (arr[mid] value) {return mid;} else if (arr[mid] value) {return binarySearchByRecursion(arr, value, low, mid - 1);} else {return binarySearchByRecursion(arr, value, mid 1, high);}
}/*** 插值查找--递归实现原理与二分查找类似按目标值的大小计算在数组中的权重适用于均有有序的数组* param arr 待查询数组* param value 查找目标值* param low 数组起始下标* param high 数组结束下标* return 目标值的下标*/
public static int insertionSearch(int[] arr, int value, int low, int high) {if (arr null) {throw new RuntimeException(Input arr is null!);}// 按目标值与最小值的差估算插值下标的位置int mid low ((value - arr[low]) / (arr[high] - arr[low])) * (high -low);if (low high arr[mid] ! value) {return -1;}if (arr[mid] value) {return mid;} else if (arr[mid] value) {return binarySearchByRecursion(arr, value, low, mid - 1);} else {return binarySearchByRecursion(arr, value, mid 1, high);}
} 转载于:https://www.cnblogs.com/beichenroot/p/11122212.html
