首先,假设表中元素是按升序排列,将表中间位置记录的关键字与查找关键字比较,如果两者相等,则查找成功;否则利用中间位置记录将表分成前、后两个子表,如果中间位置记录的关键字大于查找关键字,则进一步查找前一子表,否则进一步查找后一子表。重复以上过程,直到找到满足条件的记录,使查找成功,或直到子表不存在为止,此时查找不成功。
package com.example.demo.sf; /** * @Auther: Java小强 * @Date: 2022/1/24 - 16:26 * @Decsription: 二分查找 * @Version: 1.0 */ public class BinarySearch { public static void main(String[] args) { // 数组已经排序 int[] array = {1, 2, 5, 6, 8, 11, 13, 15, 17, 20, 22, 24, 26, 28, 30, 32, 35, 38, 41, 46, 53, 56, 58}; int target = 22; System.out.println(getBinarySearch(array,target)); } public static int getBinarySearch(int[] array, int target) { int l = 0, r = array.length - 1, m; while (l <= r) { // m = (l + r) / 2; // 中间位置 m = (l + r) >>> 1; if (array[m] == target) { return m; // 找到返回 } else if (array[m] > target) { r = m - 1; // 如果中间大于目标说明位置在左边,更改右边界 } else { l = m + 1; // 如果中间小于目标说明位置在右边,更改左边界 } } return -1; } }
算法的原理如下:
比较相邻的元素。如果第一个比第二个大,就交换他们两个。
对每一对相邻元素做同样的工作,从开始第一对到结尾的最后一对。在这一点,最后的元素应该会是最大的数。
针对所有的元素重复以上的步骤,除了最后一个。
持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。
package com.example.demo.sf; import java.util.Arrays; /** * @Auther: Java小强 * @Date: 2022/1/24 - 19:20 * @Decsription: 冒泡排序 * @Version: 1.0 */ public class BubbleSort { public static void main(String[] args) { int[] array = {5, 3, 7, 2, 9, 8, 1, 4}; bubbleSort(array); } public static void bubbleSort(int[] arr) { for (int j = 0; j < arr.length - 1; j++) { boolean swaped = false; // 每排序一次,就成功一个值,此时就减少一次内循环 for (int i = 0; i < arr.length - 1 - j; i++) { if (arr[i] > arr[i + 1]) { swap(arr, i, i + 1); swaped = true; } } // 如果本轮内循环一次交换也没有发生,说明整体排序已经完成 if(!swaped){ break; } System.out.println("冒泡排序第" + j + "轮:" + Arrays.toString(arr)); } } public static void swap(int[] arr, int i, int j) { int t = arr[i]; arr[i] = arr[j]; arr[j] = t; } }
首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置,然后,再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾。以此类推,直到所有元素均排序完毕。
package com.example.demo.sf; import java.util.Arrays; /** * @Auther: Java小强 * @Date: 2022/1/24 - 19:50 * @Decsription: 选择排序 * @Version: 1.0 */ public class SelectionSort { public static void main(String[] args) { int[] array = {5, 3, 7, 2, 9, 8, 1, 4}; selectionSort(array); } public static void selectionSort(int[] arr) { for (int i = 0; i < arr.length; i++) { int s = i; // 最小值的坐标 for (int j = s + 1; j < arr.length; j++) { if (arr[s] > arr[j]) { s = j; } } if (s != i) { swap(arr, s, i); } System.out.println("选择排序第" + i + "轮:" + Arrays.toString(arr)); } } public static void swap(int[] arr, int i, int j) { int t = arr[i]; arr[i] = arr[j]; arr[j] = t; } }
插入排序的工作方式像许多人排序一手扑克牌。开始时,我们的左手为空并且桌子上的牌面向下。然后,我们每次从桌子上拿走一张牌并将它插入左手中正确的位置。为了找到一张牌的正确位置,我们从右到左将它与已在手中的每张牌进行比较。拿在左手上的牌总是排序好的,原来这些牌是桌子上牌堆中顶部的牌 。
插入排序是指在待排序的元素中,假设前面n-1(其中n>=2)个数已经是排好顺序的,现将第n个数插到前面已经排好的序列中,然后找到合适自己的位置,使得插入第n个数的这个序列也是排好顺序的。按照此法对所有元素进行插入,直到整个序列排为有序的过程,称为插入排序 。
package com.example.demo.sf; import org.jetbrains.annotations.NotNull; import java.util.Arrays; /** * @Auther: Java小强 * @Date: 2022/1/24 - 20:03 * @Decsription: 插入排序 * @Version: 1.0 */ public class InsertSort { public static void main(String[] args) { int[] array = {5, 3, 7, 2, 9, 8, 1, 4}; insertSory(array); } public static void insertSory(int @NotNull [] arr) { for (int i = 1; i < arr.length; i++) { int t = arr[i]; // 待插入元素 int j = i - 1; // 代表已排序区域索引 while (j >= 0) { if (t < arr[j]) { arr[j + 1] = arr[j]; } else { break; // 索引 j 之前都是排序好的 } j--; } arr[j + 1] = t; System.out.println("插入排序第" + i + "轮:" + Arrays.toString(arr)); } } }
快速排序算法通过多次比较和交换来实现排序,其排序流程如下:
(1)首先设定一个分界值,通过该分界值将数组分成左右两部分。
(2)将大于或等于分界值的数据集中到数组右边,小于分界值的数据集中到数组的左边。此时,左边部分中各元素都小于或等于分界值,而右边部分中各元素都大于或等于分界值。
(3)然后,左边和右边的数据可以独立排序。对于左侧的数组数据,又可以取一个分界值,将该部分数据分成左右两部分,同样在左边放置较小值,右边放置较大值。右侧的数组数据也可以做类似处理。
(4)重复上述过程,可以看出,这是一个递归定义。通过递归将左侧部分排好序后,再递归排好右侧部分的顺序。当左、右两个部分各数据排序完成后,整个数组的排序也就完成了。
package com.example.demo.sf; import java.util.Arrays; /** * @Auther: Java小强 * @Date: 2022/1/24 - 21:07 * @Decsription: 单边快排 * @Version: 1.0 */ public class QuickSort1 { public static void main(String[] args) { int[] array = {5, 3, 7, 2, 9, 8, 1, 4}; quickSort(array, 0, array.length - 1); } public static void quickSort(int[] arr, int l, int h) { if (l >= h) { return; } int p = partition(arr, l, h); quickSort(arr, l, p - 1); // 左边 quickSort(arr, p + 1, h); // 右边 } public static int partition(int[] arr, int l, int h) { int pv = arr[h]; // 基准点元素 int i = l; for (int j = l; j < h; j++) { if (arr[j] < pv) { if (i != j) { swap(arr, i, j); } i++; } } if (i != h) { swap(arr, h, i); } System.out.println("单边排序:" + Arrays.toString(arr)); return i; } public static void swap(int[] arr, int i, int j) { int t = arr[i]; arr[i] = arr[j]; arr[j] = t; } }
package com.example.demo.sf; import javafx.beans.binding.When; import java.util.Arrays; /** * @Auther: Java小强 * @Date: 2022/1/24 - 21:07 * @Decsription: 双边快排 * @Version: 1.0 */ public class QuickSort2 { public static void main(String[] args) { int[] array = {5, 3, 7, 2, 9, 8, 1, 4}; quickSort(array, 0, array.length - 1); } public static void quickSort(int[] arr, int l, int h) { if (l >= h) { return; } int p = partition(arr, l, h); quickSort(arr, l, p - 1); // 左边 quickSort(arr, p + 1, h); // 右边 } public static int partition(int[] arr, int l, int h) { int pv = arr[l]; // 基准点元素 int i = l; int j = h; while (i < j) { // j 从右找小的 // 内层两个循环都要加i<j,例如数组为[5,1,2,3,6,7,8,9],j会找到3,i会找到6,这时不能交换 // 必须从右开始找,例如[5,3,7,2,9,8,1,4],第一次会相交在8,如果此时外层交换,会将8和5交换 while (i < j && arr[j] > pv) { j--; } // i 从左找大的 // 从左找时如果和基准点相等,那应该取下一个,否则会把基准点换走 while (i < j && arr[i] <= pv) { i++; } swap(arr, i, j); } swap(arr, l, j); // 此时 i j 已经一致 System.out.println("双边排序:" + Arrays.toString(arr)); return j; } public static void swap(int[] arr, int i, int j) { int t = arr[i]; arr[i] = arr[j]; arr[j] = t; } }
Java小强
未曾清贫难成人,不经打击老天真。
自古英雄出炼狱,从来富贵入凡尘。
发表评论: