Java七种排序

一，第一种：冒泡排序

冒泡排序的原理：数组两两比较,进行位置交换，经过一轮排序后，最大（小）的元素，放置在最后面 代码实现：

int[] arr = {24, 69, 80, 57, 13}; 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));

二，第二种：选择排序

选择排序原理：从0索引处开始，拿着这个元素，跟后面的元素挨个比较，小的往前放，经过一轮比较后，最小元素，就会放在最前面 代码实现：

int[] arr = {24, 69, 80, 57, 13,1,20,10,30}; 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));

三，第三种：插入排序

直接插入排序,是一种最简单的排序方法.他的基本操作是将一个记录插入到一个长度为m 的有序表中,使之仍保持有序,从而得到一个新的长度为m+1的有序列表.假设有一组元素{k1,k2…,kn},排序开始就认为k1是一个有序序列,让k2插入上述表长为1的有序序列,使之成为一个表长为2的有序序列,然后让k3插入上述表长为2的有序序列,使之成为一个表长为3的有序序列,以此类推,最后让kn插入表长为n-1的有序序列,得到一个表长为n的有序序列. 代码实现：

int[] arr={10,-1,1,1,3,5,6,9,0,100,3,-9,1000}; //外层循环定义轮次 //[10] for (int i =1; i < arr.length; i++) { int j=i; //往之前的有序列表中插入元素，插入完之后，使之仍保持有序 while (j>0&&arr[j]<arr[j-1]){//当前元素arr[i] 跟我前面一个元素去比 arr[i-1] int t=arr[j]; arr[j]=arr[j-1]; arr[j-1]=t; j--; } } System.out.println(Arrays.toString(arr));

四，第四种：快速排序

快速排序算法思想：分治法：比大小，再分区 1.从数组中取出一个数，作为基准数。 2.分区：将比这个数大或等于的数全放到他的右边，小于他的数 全放到他的左边。 3.再对左右区间重复第二步，直到各区间只有一个数。 实现思路： 1.将基准数挖出形成第一个坑。 2.由后向前找比他小的数，找到后挖出此数填到前一个坑中。 3.由前向后找比他大或等于的数，找到后也挖出此数填到前一个坑中。 4.再重复执行2，3两步骤。 代码实现：

public class 快速排序 { public static void main(String[] args) { int[] arr={8,6,3,5,7,4,2}; QuickSortUtils.quickSort(arr,0,arr.length-1); System.out.println(Arrays.toString(arr)); } } 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);//对右半边，进行递归 } } //挖坑填数 private static int getIndex(int[] arr, int start, int end) { //定义三个变量 int i = start; int j = end; //定义一个基准数 int x = arr[i]; //将基准数挖出形成第一个坑。 //由后向前找比他小的数，找到后挖出此数填到前一个坑中。 //由前向后找比他大或等于的数，找到后也挖出此数填到前一个坑中。 //再重复执行2，3两步骤。 while (i < j) { //2 由后向前找比他小的数，找到后挖出此数填到前一个坑中。 while (i < j && arr[j] > x) { j--; //比他的大的，继续向前退 } if (i < j) { arr[i] = arr[j]; i++; //顺便让i递增一下 } //3.由前向后找比他大或等于的数，找到后也挖出此数填到前一个坑中。 while (i < j && arr[i] <= x) { i++; //后面的数，比他小 i继续往后找 } if (i < j) { arr[j] = arr[i]; j--; //顺便让j递减一下 } } arr[i] = x; return i; } }

五，第五种：归并排序

归并排序算法思想：归并排序是利用归并的思想实现的排序方法，该算法采用经典的分治策略（分治法将问题分成一些小的问题然后递归求解，而治的阶段则将分的阶段得到的各答案"修补"在一起，即分而治之)。 代码实现：

public class 归并排序 { public static void main(String[] args) { //治理：将两个有序子序列，合并成一个有序序列 int[] arr = {1, 4,6,0,-1,4,9,20,35,98, 9, 2, 4, 6, 8, 10,-4,1000,800}; chaiFen(arr,0,arr.length-1); System.out.println(Arrays.toString(arr)); } private static void chaiFen(int[] arr, int startIndext, int endIndex) { //计算中间索引 int centerIndex=(startIndext+endIndex)/2; if(startIndext<endIndex){ //递归拆左边 chaiFen(arr, startIndext, centerIndex); //递归拆右边 chaiFen(arr, centerIndex + 1, endIndex); mergeSort(arr, startIndext, centerIndex, endIndex); } } private static void mergeSort(int[] arr, int startIndtx, int centerIndex, int endIndex) { //定义一个临时数组 int[] tempArray=new int[endIndex-startIndtx+1]; //定义第一数组的起始索引 int i=startIndtx; //定义第二个数组的起始索引 int j=centerIndex+1; //定义临时数组的索引 int index=0; //两个数组元素，进行对比归并 while (i<=centerIndex&&j<=endIndex){ if(arr[i]<=arr[j]){ //把小的数放到临时数组中 tempArray[index]=arr[i]; i++; //递增一下索引 }else{ tempArray[index] = arr[j]; j++; //递增一下索引 } index++; //临时数组的索引也要递增 } //处理剩余元素 while (i<=centerIndex){ tempArray[index]=arr[i]; i++; index++; } while (j<=endIndex){ tempArray[index] = arr[j]; j++; index++; } //经过上面的操作后，临时数组中的元素就排序好了 // System.out.println(Arrays.toString(tempArray)); //把临时数组中的元素放到原数组中 for (int k = 0; k < tempArray.length; k++) { arr[startIndtx+k]=tempArray[k]; } } }

六，第六种：希尔排序

基本思想：先将原表按照增量分组，每个子文件按照直接插入排序，用下一个增量的一半，再将文件分子文件，在直接插入排序，直到增量为1时，整个文件就排好了 代码实现：

public class 希尔排序 { public static void main(String[] args) { int[] arr = {9, 4, 5, 6, 1, 0, 3, 2, 10, 20, 11, 24, 32, 13}; shellSort(arr); System.out.println(Arrays.toString(arr)); } private static void shellSort(int[] arr) { int jiange = 1; while (jiange <= arr.length / 3) { jiange = 3 * jiange + 1; } for (int h = jiange; h > 0; h = (h - 1) / 3) { for (int i = h; i < arr.length; i++) { for (int j = i; j > h - 1; j -= h) { if (arr[j] < arr[j - h]) { swapValue(arr, j, j - h); } } } } } private static void swapValue(int[] arr, int i, int j) { int t = arr[i]; arr[i] = arr[j]; arr[j] = t; } private static void insertSort(int[] arr) { for (int i = 1; i < arr.length; i++) { int j = i; while (j > 0 && arr[j - 1] > arr[j]) { swapValue(arr, j, j - 1); j--; } } } }

七，第七种：基数排序

基数排序的实现不需要进行对关键字的比较， 只需要对关键字进行“分配”与“收集”两种操作即可完成。 基数排序的数组每个关键字都必须是正整数数值，且其中的最大值由个位、十位和百位构成，每个数位上的数字从 0 到 9，首先将各个关键字按照其个位数字的不同进行分配，其中最大数有多少位，就进行多少轮，排到最后时按顺序取出，就排好了

public class 基数排序 { public static void main(String[] args) { int[] arr = {19, 0, 35, 6, 9, 2, 198, 390, 208, 23, 195, 2990, 1980, 1000, 1987}; int max = getMax(arr); int[][] temparr = new int[10][arr.length]; int[] arr1 = new int[10]; int len = String.valueOf(max).length(); for (int i = 0, n = 1; i < len; i++, n *= 10) { for (int j = 0; j < arr.length; j++) { int num = arr[j] / n % 10; temparr[num][arr1[num]++] = arr[j]; } int index = 0; for (int k = 0; k < arr1.length; k++) { if (arr1[k] != 0) { for (int h = 0; h < arr1[k]; h++) { //从桶中取出数组，放回原数组 arr[index] = temparr[k][h]; index++; } //取完之后，清空上一次的统计记录 arr1[k] = 0; } } } System.out.println(Arrays.toString(arr)); } private static int getMax(int[] arr) { int max = arr[0]; for (int i = 1; i < arr.length; i++) { if (arr[i] > max) { } max = arr[i]; } return max; } }