java常见的两种算法
< 返回列表时间: 2020-06-07来源:OSCHINA
1:冒泡算法
思路:相邻两个数字依次比较, /** * @param arr 待排序数组 * @brief 冒泡排序 */ protected static void maoPao(int[] arr) { //外层循环控制需要比较的次数,需要比较的次数,需要减去自身,自己不用跟自己比较了 for (int i = 0; i < arr.length - 1; i++) { //内层循环控制每两个相邻的数需要比较的次数,外层循环一次,就会得到一个最大的数,内层就需要减少一次 for (int i1 = 0; i1 < arr.length - 1 - i; i1++) { int temp; if (arr[i1] >= arr[i1 + 1]) {//假如左边的数比右边的数大 //交换两数的位置 temp = arr[i1]; arr[i1] = arr[i1 + 1]; arr[i1 + 1] = temp; } } } }
2:快速排序,
思路:两边同时像中间靠拢,二分思想 /** * @param arr 待排序数组 * @param left 数组最小索引 * @param right 数组最大索引 * @brief 快速排序(二分思想) */ protected static void fastSort(int[] arr, int left, int right) { //定义左右哨兵位和中间数以及临时变量 int l = left, r = right, temp, t; if (l >= r) {//递归出口 return; } //假设最左边的为中间数,可以随机指定 temp = arr[left]; /** * 从最右边的开始走,一直走到当前位置的数比中间数小的时候,此时右边的开始走,当右边的有比中间数大的时候,左右交换位置,然后第一次交换结束 * 右边开始的继续走,当碰到比中间数小的时候,重复第一次的情况, * 所以可以使用递归加while来解决 * */ //当左哨兵位l小于右边r哨兵位时,说明一次都没有遍历完,因为当l=r时,说明大的已经全部交换到右边,小的全部交换到左边了,除了这种情况以外,都是需要继续遍历,直到l=r while (l < r) { //只要满足右边遍历的数都大于中间数,并且l<r时,一直保持向左移动 while (arr[r] >= temp && l < r) { r--;//r下标一直递减,模拟依次向左遍历 } //只要满足从最左边开始遍历的数都小于中间数,并且l<r时,一直保持向右移动 while (arr[l] <= temp && l < r) { l++;//l下标一直递增,模拟依次向右遍历 } if (l < r) {//只要左边小于右边 t = arr[l];//大于中间数的 arr[l] = arr[r];//右边小于中间数的值赋给小于中间数的左半数组 arr[r] = t;//把大于中间数的值赋给大于中间数的右边数组 } } //当上边的while循环完毕的时候,此时l=r时循环停止,应当把中间数赋给中间下标的值 arr[left] = arr[l]; arr[l] = temp; /** * 第一次循环完毕之后,中间数在中间,左边是小于中间数的无序数组, * 右边是大于中间数的无序数组,故需要递归直到左右两边的数组有序 * */ //递归循环左边数组,条件为最小索引到中间索引-1,因为中间数不需要参与比较,它的位置是已经确定好的了 fastSort(arr, left, l - 1); //递归循环右边数组,条件为中间索引+1,到最大索引,因为中间数已经确定,不需要参数循环 fastSort(arr, l + 1, right); }
 其他算法,以后再更新
热门排行