排序算法，快速排序，折半查找，选择排序，冒泡排序，插入排序

一、插入排序

package com; import java.util.Arrays; /** * 插入排序 * 思路：先默认第一个元素是有序的，然后从第二个元素开始向前比较。 * @title InsertionSort.java */ public class InsertionSort { public static void main(String[] args) { int[] arr = new int[] { 3, 43, 25, 16, 31, 57, 8 }; for (int i = 1; i < arr.length; i++) { for (int j = i; j > 0; j--) { if (arr[j] < arr[j - 1]) { int temp = arr[j - 1]; arr[j - 1] = arr[j]; arr[j] = temp; } else { break; } } } System.out.println(Arrays.toString(arr)); } }

二、冒泡排序

package com; import java.util.Arrays; /** * 冒泡排序 * 思路：数组中两个相邻元素进行两两比较。 * @title BubbleSort.java */ public class BubbleSort { public static void main(String[] args) { int[] arr = {3, 43, 25, 16, 31, 57, 8}; System.out.println("排序前：" + Arrays.toString(arr)); int temp = 0; for(int i=0; i<arr.length - 1; i++) { for(int j=0; j<arr.length-1-i; j++) { if(arr[j] > arr[j+1]) { temp = arr[j]; arr[j] = arr[j+1]; arr[j+1] = temp; } } } System.out.println("排序后：" + Arrays.toString(arr)); } }

三、选择排序

package com; import java.util.Arrays; /** * 选择排序 */ public class SelectSort { public static void main(String[] args) { int[] arr = { 3, 43, 25, 16, 31, 57, 8 }; int size = arr.length; int temp = 0; for (int i = 0; i < size; i++) { int k = i; for (int j = size - 1; j > i; j--) { if (arr[j] < arr[k]) { k = j; } } temp = arr[i]; arr[i] = arr[k]; arr[k] = temp; } System.out.println(Arrays.toString(arr)); } }

四、折半查找

package com; import java.util.Arrays; /** * 折半查找 * @title Search.java */ public class Search { public static void main(String[] args) { int[] arr = new int[] { 3, 43, 25, 16, 31, 57, 8 }; // 第一步：对给定数组进行排序 Arrays.sort(arr); //System.out.println(Arrays.toString(arr)); // 第二步：实现查找 // 定义被查找的值 int num = 4; // 定义一个低位的下标 int low = 0; // 定义一个高位的下标 int height = arr.length - 1; // 定义一个中间位的下标 int middle = (low + height) / 2; boolean flag = false; while(low <= height) { if (num == arr[middle]) { System.out.println("找到了，元素的下标为：" + middle); flag = true; break; } else if (num < arr[middle]) { height = middle - 1; } else { low = middle + 1; } middle = (low + height) / 2; } if(!flag) { System.out.println("没找到。"); } } }

五、快速排序

package com.hpeu; import java.util.Arrays; /** * 快速排序 * * @title QuickSort.java * 格式化代码的快捷键：ctrl+shift+f */ public class QuickSort { public static int partition(int[] array, int lo, int hi) { // 固定的切分方式 int key = array[lo]; while (lo < hi) { // 从后半部分向前扫描 while (array[hi] >= key && hi > lo) { hi--; } array[lo] = array[hi]; // 从前半部分向后扫描 while (array[lo] <= key && hi > lo) { lo++; } array[hi] = array[lo]; } array[hi] = key; return hi; } public static void sort(int[] array, int lo, int hi) { if (lo >= hi) { return; } int index = partition(array, lo, hi); sort(array, lo, index - 1); sort(array, index + 1, hi); } public static void main(String[] args) { int[] arr = { 3, 43, 25, 16, 31, 57, 8 }; //sort(arr, 0, arr.length - 1); Arrays.sort(arr); for (int em : arr) { System.out.print(em + " "); } } }