Java基础（冒泡排序、选择排序，二分法查找）

文章目录

冒泡排序选择排序直接插入排序希尔排序快速排序二分法查找 排序方法有许多，在这里主要介绍冒泡排序，选择排序，插入排序，快速排序和希尔排序。

冒泡排序

比较相邻的元素。如果第一个比第二个大，就交换它们两个； 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数； 针对所有的元素重复以上的步骤，除了最后一个；

代码实现：

public class MyTest { public static void main(String[] args) { int[] arr = {24, 69, 80, 57, 13, 20, -1, 0}; for (int j = 0; j < arr.length - 1; j++) { for (int i = 0; i < arr.length - 1 - j; i++) { if (arr[i] > arr[i + 1]) { int t = arr[i]; arr[i] = arr[i + 1]; arr[i + 1] = t; } } } System.out.println(Arrays.toString(arr)); }

选择排序

每次拿一个元素和后面所有得元素挨个比较，小得往前放，经过一轮比交换，最小得元素会出现在最前面，如此往复，整个数组就排好序了。

代码实现：

public class MyTest2 { public static void main(String[] args) { int[] arr = {24, 69, 80, 57, 13,20,50,200,0,-1}; for (int index = 0; index < arr.length-1; index++) { for (int i = 1 + index; i < arr.length; i++) { if (arr[index] > arr[i]) { int t = arr[index]; arr[index] = arr[i]; arr[i] = t; } } } System.out.println(Arrays.toString(arr)); }

直接插入排序

直接插入排序：每次将后面一个元素，插入到之前得一个有序序列中，使之仍保持有序

代码实现：

public class MyTest3 { public static void main(String[] args) //直接插入排序：每次将后面一个元素，插入到之前得一个有序序列中，使之仍保持有序 int[] arr = {49，38，65，97，76，13，27}; for (int i = 1; i < arr.length; i++) { int j=i; while (j>0&&arr[j]<arr[j-1]){ int t=arr[j]; arr[j]=arr[j-1]; arr[j-1]=t; j--; } System.out.println(Arrays.toString(arr)); }

希尔排序

希尔(Shell)排序又称为缩小增量排序，它是一种插入排序。它是直接插入排序算法的一种威力加强版。

该方法因DL．Shell于1959年提出而得名。

希尔排序的基本思想是：

把记录按步长 gap 分组，对每组记录采用直接插入排序方法进行排序。 随着步长逐渐减小，所分成的组包含的记录越来越多，当步长的值减小到 1时，整个数据合成为一组，构成一组有序记录，则完成排序。

我们来通过演示图，更深入的理解一下这个过程。 代码实现：

public void Test4(int[] list) { int gap = list.length / 2; while (1 <= gap) { // 把距离为 gap 的元素编为一个组，扫描所有组 for (int i = gap; i < list.length; i++) { int j = 0; int temp = list[i]; // 对距离为 gap 的元素组进行排序 for (j = i - gap; j >= 0 && temp < list[j]; j = j - gap) { list[j + gap] = list[j]; } list[j + gap] = temp; } System.out.format("gap = %d:\t", gap); printAll(list); gap = gap / 2; // 减小增量 } }

快速排序

从数列中挑出一个元素，称为 “基准”（pivot）； 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。

代码实现：

public class QuickSort { public 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); } } private int getIndex(int[] arr, int start, int end) { int i = start; int j = end; int x = arr[i]; //循环 while (i < j) { //从右往左比较 while (i < j && arr[j] >= x) { j--; } //从右往左找到比基准数小的数了后，填坑 if (i < j) { //把这个数填到上一个坑位 arr[i] = arr[j]; //让 i++; i++; }//从左往右找 while (i < j && arr[i] < x) { i++; } // 找比基准数大的数，找到后填坑 if (i < j) { arr[j] = arr[i]; j--; } } //当上面的循环结束后把基准数填到最后一个坑位，也就一基准数为界，分成了左右两部分 arr[i] = x; //把基准数填进去 return i; //返回基准数所在位置的索引 } }

二分法查找

代码实现：

public class MyTest2 { public static void main(String[] args) { //查找思想：前提条件：数组元素必须有序，二分查找：每次查找一半 int[] arr = {10, 20, 30, 50, 90, 100, 101, 300, 400}; int index = getIndex(arr, 90); System.out.println("索引是" + index); } private static int getIndex(int[] arr, int ele) { int minIndex = 0; int maxIndex = arr.length - 1; int centerIndex = (minIndex + maxIndex) / 2; while (minIndex <= maxIndex) { if (ele == arr[centerIndex]) { return centerIndex; } else if (ele > arr[centerIndex]) { minIndex = centerIndex + 1; } else if (ele < arr[centerIndex]) { maxIndex = centerIndex - 1; } centerIndex = (minIndex + maxIndex) / 2; } return -1; } }