java之排序算法

1、冒泡排序

理解：从头开始比较，每次比较两个相邻的数据，若顺序错误，则交换位置；若顺序正确，则进行下两个数据的比较。一轮比较之后，最大值或最小值就会“浮”到数组的最后面，整个过程中，该值就像泡泡一样咕嘟咕嘟冒出来。

public static void main(String[] args) {int arr[] = new int[]{12,56,1,59,88,30,59,200,10,9};//将数组从大到小排列/*** 外循环：一共要执行几轮比较。* 数组共10个数字，比较9轮即可。* -1是为了防止索引越界，因为i从0开始。*/for(int i = 0;i < arr.length-1;i++){//内循环：-i是为了提高比较效率，已经比较出来的数字可以不再进行比较for(int j = 0;j<arr.length-1-i;j++){if(arr[j] < arr[j+1]){int temp;temp = arr[j];arr[j] = arr[j+1];arr[j+1] = temp;}}}System.out.println(Arrays.toString(arr));}

2、选择排序

理解：从数组的第一个数开始，将这个数依次跟后面的所有数进行比较。若碰到顺序错误的，交换位置；若顺序正确，继续比较。

public static void main(String[] args) {int arr[] = new int[]{12, 56, 1, 59, 88, 30, 59, 200, 10, 9};//将数组从大到小排列//外循环：代表这一轮中，拿着哪个位置上的数字跟后面的比较。for (int i = 0; i < arr.length - 1; i++) {//内循环：表示后面被比较的数字for (int j = i + 1; j < arr.length; j++) {if (arr[i] < arr[j]) {int temp;temp = arr[i];arr[i] = arr[j];arr[j] = temp;}}}System.out.println(Arrays.toString(arr));}

3、插入排序

理解：将数组分为有序序列（索引：0——x）和无序序列（索引：x+1——数组结尾），遍历无序序列中的所有数据，依次将数据插入有序序列。

因此插入排序分两个步骤：1、找到有序序列的结尾位置 2、遍历无序序列，将无序序列中的值插入有序序列。

public static void main(String[] args) {int arr[] = new int[]{12, 56, 1, 59, 88, 30, 59, 200, 10, 9};//将数组从大到小排列//查找有序序列的结尾位置int startIndex = -1;for (int i = 0; i < arr.length - 1; i++) {if (arr[i] > arr[i + 1])startIndex = i + 1;break;}//插入排序//外循环：遍历无序序列中的所有数据for (int j = startIndex; j < arr.length; j++) {/***  内循环：遍历有序序列，将无序序列中的值插入到合适的位置*  将无序序列中的值与有序序列比较，若顺序错误则交换位置。*/for (int i = 0; i < j; i++) {if (arr[j] > arr[i]) {int temp;temp = arr[i];arr[i] = arr[j];arr[j] = temp;}}}System.out.println(Arrays.toString(arr));}

4、快速排序

核心思细：基准数归位。

理解：一般找数组的第一个数为基准数，创建两个指针，一个从前往后走（start），一个从后往前走（end）。start找到第一个比基准数大的数，end找比第一个基准数小的数，交换位置，然后继续寻找并交换位置，直到start和end位于同一位置，该位置就是基准数的位置。

把基准数左边看做一个序列，把基准数右边看做一个序列，按照刚刚的规则递归排序。

第一轮排序：

public static void main(String[] args) {int arr[] = new int[]{12, 56, 1, 59, 88, 30, 59, 200, 10, 9};//将数组从小到大排列//第一轮//创建指针int start = 1;int end = arr.length - 1;//第一轮开始查找while (start != end) {//利用end从后往前找,找比基准数小的值while (true) {if (end <= start || arr[end] < arr[0]) {break;}end--;}//利用start从前往后找，找比基准数大的值while (true) {if (end <= start || arr[start] > arr[0]) {break;}start++;}//把end和start指向的数字交换int temp;temp = arr[end];arr[end] = arr[start];arr[start] = temp;}//基准数归位int temp;temp = arr[start];arr[start] = arr[0];arr[0] = temp;System.out.println(Arrays.toString(arr));}

第一轮排序之后，12左边的数都比12小，右边的都比12大

完整代码：

public class Demo2 {public static void main(String[] args) {int arr[] = new int[]{12, 56, 1, 59, 88, 30, 59, 200, 10, 9};quickSort(arr,0,arr.length-1);System.out.println(Arrays.toString(arr));}/**** @param arr 要进行排序的数组* @param i 要排序数组的起始索引，一般是0* @param j 要排序数组的结束索引，一般是arr.length-1*/public static void quickSort(int[] arr,int i,int j){//创建索引int start = i;int end = j;//递归的出口if(start > end){return;}//基准数为a[i]while (start != end) {//利用end从后往前找,找比基准数小的值。while (true) {if (end <= start || arr[end] < arr[i]) {break;}end--;}//利用start从前往后找，找比基准数大的值while (true) {if (end <= start || arr[start] > arr[i]) {break;}start++;}//把end和start指向的数字交换int temp;temp = arr[end];arr[end] = arr[start];arr[start] = temp;}//基准数归位int temp;temp = arr[start];arr[start] = arr[i];arr[i] = temp;//确定基准数归位后，左边的范围quickSort(arr,i,start - 1);//确定基准数归位后，左边的范围quickSort(arr,start + 1,j);}
}