本文共 2517 字，大约阅读时间需要 8 分钟。

冒泡排序：

效率低，实现简单，稳定，平均时间复杂度：O(n^2)，最好情况：O(n),最坏情况：O(n^2)

思想：相邻两个元素之间进行排序，排序第一次，最大的元素排在最后一位，排序第二次，第二大元素排在倒数第二位，以此类推。第一次排序的次数为数组的最大索引值，第二次为最大索引值-1，依次类推

package com.stu;import java.util.Arrays;import java.util.Scanner;public class 冒泡排序 {	public static void main(String[] args) {		int[] arr = new int[10];		Scanner sc = new Scanner(System.in);		System.out.println("请输入需要进行比较的数组：");		for (int i = 0; i < arr.length; i++) {			arr[i] = sc.nextInt();		}		sortArray(arr);	}	public static void sortArray(int[] arr) {		// 外层循环控制循环次数		for (int i = 0; i < arr.length; i++) {			// 内层循环进行比较			for (int j = 0; j < arr.length - 1 - i; j++) {				if (arr[j] > arr[j + 1]) {					int temp = arr[j + 1];					arr[j + 1] = arr[j];					arr[j] = temp;				}			}		}		// 循环结束后将数组输出		System.out.println(Arrays.toString(arr));	}}

插入排序：

效率低，容易实现，稳定，平均时间复杂度：O(n^2)，最好情况：O(n),最坏情况：O(n^2)

思想：将数组分为两部分，将后部分元素与前部分元素进行比较，比其小的插入到前面去。在这里，数组的第一个索引为第一部分，后面的为第二部分。

package com.stu;import java.util.Arrays;import java.util.Scanner;public class 插入排序 {	public static void main(String[] args) {		Scanner sc = new Scanner(System.in);		int[] arr = new int[10];		System.out.println("请输入需要排序的数组：");		for (int i = 0; i < arr.length; i++) {			arr[i] = sc.nextInt();		}		sortArray(arr);	}	public static void sortArray(int[] arr) {		// 定义出需要进行比较的索引，以及需要插入的数组temp		int i, j, temp;		// 假设第一个元素被放在了正确的位子上，那么只需要从第二个元素开始进行比较		for (i = 1; i < arr.length; i++) {			temp = arr[i];			j = i;			while (j > 0 && temp < arr[j - 1]) {				arr[j] = arr[j - 1];				arr[j - 1] = temp;				j--;			}			arr[j] = temp;		}		System.out.println(Arrays.toString(arr));	}}

快速排序

效率高，不稳定，平均时间复杂度：O(nlogn)，最好情况：O(nlogn),最坏情况：O(n^2)

思想：其思想来自冒泡排序，冒泡排序是通过相邻元素的比较和交换把最小的元素冒泡到最顶端，而快速排序是比较和交换小数和大数，不仅把小数冒泡到最前面，也把大数沉到最后面。如下图的例子：

package com.stu;import java.util.Arrays;public class 快速排序 {	public static void main(String[] args) {		int arr[]={2,76,45,4,323,545,34,23,36,6,5};		quickSort(arr);		System.out.println(Arrays.toString(arr));	}	public static void sort(int[] arr, int low, int hight) {		int i, j, index;		if (low > hight) {			return;		}		i = low;		j = hight;		// 在这里，用数组的第一个记录作为基准数		index = arr[i];		// 进行扫描		while (i < j) {			while (i < j && arr[j] >= index)				j--;			if (i < j)				// 用比基准小的记录替换低位记录// arr[i]=arr[j];i++				arr[i++] = arr[j];			while (i < j && arr[i] < index)				i++;			if (i < j)				// 用比基准大的记录替换高位记录				arr[j--] = arr[i];		}		arr[i] = index;// 将基准数值替换回arr[i]		sort(arr, low, i - 1);		sort(arr, i+1, hight);	}	public static void quickSort(int[] arr) {		sort(arr, 0, arr.length - 1);	}}