Java基础（12）-排序和查找

目录

一、冒泡排序

思想

代码实现

实例

二、选择排序

排序思想

代码实现

实例：对数组{21,54,21,2,4,87,24,82,4,5}进行排序

三、快速排序

排序思想

代码实现

实例,对数组{21,54,21,2,4,87,24,82,4,5}进行快速排序

四、二分查找

算法思想

代码实现

示例：在数组{2, 2, 2, 4, 5, 21, 24, 54, 82, 87}中使用二分查找算法查找 5 这个元素。

五、基本查找

算法思想

代码实现

示例：在数组{2, 2, 2, 4, 5, 21, 24, 54, 82, 87}中使用基本查找对 54 这个元素进行查找

---

---

一、冒泡排序

思想

冒泡排序的思想是循环遍历数组，相邻元素两两比较，大的元素后移，所以第一趟循环就确定了最大索引处的元素（为最大值），第二趟确定倒数第二个元素，以此类推。

经过观察，发现完成冒泡排序需要 数组长度-1 趟，而每一趟需要比较 趟数-1 次。

代码实现

package utils.sort;​public class BubbleSortUtils {   public static void bubbleSort(int[] arr) {       for (int i = 0; i < arr.length; i++) {           for (int j = 1; j < arr.length - i; j++) {               if (arr[j-1]>arr[j]){                   int t=arr[j-1];                   arr[j-1]=arr[j];                   arr[j]=t;               }           }       }   }}

实例

对整型数组{21，54，65，21，8，93，2，32，20，58，92}进行冒泡排序。

import utils.sort.BubbleSortUtils;​import java.util.Arrays;​public class Test {   public static void main(String[] args) {       int[] arr={21,54,65,21,8,93,2,32,20,58,92};       BubbleSortUtils.bubbleSort(arr);       System.out.println(Arrays.toString(arr));   }}

二、选择排序

排序思想

1、从0索引开始，依次和后面的元素进行比较，小的元素往前放，第一次排序完成以后，最小值出现在了最小索引处；2、第一次比较的时候是从0索引处开始比较了 数组长度-1次 ，第二次排序的时候是从1索引开始，比较了数组长度-2次，第三次排序的时候是从2索引开始，比较了数组长度-3次，以此类推，直到排序完成。3、总共比较了数组长度-1次。

代码实现

package org.util;​public class SelectSortUtils {   public static void SelectSort(int[] arr){       for (int i = 0; i < arr.length; i++) {           int a=i;           for (int j = i; j < arr.length; j++) {               if(arr[a]>arr[j]){                   a=j;               }           }           int t=arr[a];           arr[a]=arr[i];           arr[i]=t;       }   }}

实例：对数组{21,54,21,2,4,87,24,82,4,5}进行排序

import org.util.SelectSortUtils;​import java.util.Arrays;​public class Test {   public static void main(String[] args) {       int[] arr={21,54,21,2,4,87,24,82,4,5};       SelectSortUtils.SelectSort(arr);       System.out.println(Arrays.toString(arr));   }}

三、快速排序 排序思想

挖坑填数法

1、将基准数挖出形成第一个坑；2、由后向前找比他小的数，找到后挖出此数填到前一个坑中；3、由前向后找比他大或者等于他的数，找到后也挖出此数填到前一个坑中；重复执行2、3步骤。

代码实现

package org.util;​public class QuickSortUtils {   public static void quickSort(int[] arr, int start, int end) {       if (start < end) {           int index = getIndex(arr, start, end);           quickSort(arr, start, index - 1);           quickSort(arr, index + 1, end);       }   }   public static int getIndex(int[] arr, int start, int end) {       int i = start;       int j = end;       int x = arr[i];       if (i < j) {           while (i < j) {               while (i < j && arr[j] >= x)                   j--;               if (arr[j] < x) {                   arr[i] = arr[j];                   i++;               }               while (i < j && arr[i] < x)                   i++;               if (arr[i] > x) {                   arr[j] = arr[i];                   j--;               }           }       }       arr[i] = x;       return i;   }}

实例,对数组{21,54,21,2,4,87,24,82,4,5}进行快速排序

import org.util.QuickSortUtils;​import java.util.Arrays;​public class Test {   public static void main(String[] args) {       int[] arr={21,54,21,2,4,87,24,82,4,5};       QuickSortUtils.quickSort(arr,0,arr.length-1);       System.out.println(Arrays.toString(arr));   }}

四、二分查找

算法思想

前提是数组元素必须是有序的。

算法的思想：每次一都查找中间索引的那个元素，比较大小就能减少一半的元素。

代码实现

package org.locate;public class BinaryLocate { public static int locate(int[] arr, int x) { return binaryLocate(arr, 0, arr.length - 1, x); } public static int binaryLocate(int[] arr, int start, int end, int x) { int centerIndex = (start + end) / 2; while (start<=end) { if (arr[centerIndex] == x) { return centerIndex; } else if (arr[centerIndex] > x) { end=centerIndex-1; } else { start=centerIndex+1; } centerIndex=(start+end)/2; } return -1; }}

示例：在数组{2, 2, 2, 4, 5, 21, 24, 54, 82, 87}中使用二分查找算法查找 5 这个元素。

import org.locate.BinaryLocate;public class Test2 { public static void main(String[] args) { int[] arr={2, 2, 2, 4, 5, 21, 24, 54, 82, 87}; System.out.println(BinaryLocate.locate(arr, 21)); }}

五、基本查找 算法思想

使用循环对数组进行遍历，用数组元素的每一项和所查元素进行比较，找到需要查找的元素。

代码实现

package org.locate;public class PrimaryLocate { public static int primaryLocate(int[] arr,int ele){ for (int i = 0; i < arr.length - 1; i++) { if(ele==arr[i]){ return i; } } return -1; }}

示例：在数组{2, 2, 2, 4, 5, 21, 24, 54, 82, 87}中使用基本查找对 54 这个元素进行查找

import org.locate.BinaryLocate;import org.locate.PrimaryLocate;public class Test2 { public static void main(String[] args) { int[] arr={2, 2, 2, 4, 5, 21, 24, 54, 82, 87}; System.out.println(PrimaryLocate.primaryLocate(arr,54)); }}