最近学到了排序算法，每一种排序我都会自己总结，今天先来两个最常见到的冒泡，选择排序

冒泡排序：

基本思想： 通过对待排序序列从前向后（从下标较小的元素开始），依次比较相邻元素的值，若发现逆序则交换，使值较大的元素逐渐从前向后移动，就像水底下的气泡逐渐向上冒。

案例： 原始数组：3, 9，-1, 10, 20

第一趟排序 ① 3, 9，-1, 10, 20 ② 3，-1, 9，10，20 ③ 3， -1, 9，10, 20 ④ 3， -1, 9，10, 20

第二趟排序 ① -1， 3， 9， 10， 20 ②-1， 3， 9， 10， 20 ③-1， 3， 9， 10， 20

第三趟排序 ①-1， 3， 9， 10， 20 ②-1， 3， 9， 10， 20

第四趟排序 ①-1， 3， 9， 10， 20

小结： ①一共进行数组的大小 -1 次的循环 ②每一趟排序的次数在逐渐的减少

代码实现：

public class BubbleSort { public static void main(String[] args) { int arr[] = {3,9,-1,10,-2}; int temp = 0; boolean flag = false; //冒泡排序的时间复杂度O（n^2） 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("第"+i+1+"趟排序后的数组："+ Arrays.toString(arr)); if(flag == true){ //在排序过程中，如果一次交换都没有，则退出循环，表示排序完毕 return; }else { //否则初始化flag flag = false; } } } }

选择排序

基本思想： 第一次从arr[0] ~ arr[n-1]中选取最小值，与arr[0]交换，第二次从arr[1] ~ arr[n-1]中选取最小值，与arr[1]交换，第三次从arr[2] ~ arr[n-1]中选取最小值，与arr[2]交换…，总共通过n-1次获得一个按顺序从小到大排列的有序序列

案例： 原始数组： 101,34,119,1

第一趟排序：1,34,119,101 第二趟排序：1,34,119,101 第三趟排序：1,34,101,119

小结：

说明选择排序一共有数组大小 -1 次排序每一轮排序，优势一个循环，循环的规则（代码实现）先假定这个数是最小数然后跟后面的每个数进行比较，如果发现有比当前数更小的数，就重新确定最小数，并得到下标当遍历到数组的最后时，就得到本轮最小数和下标交换

代码实现：

public class SelectSort { public static void main(String[] args) { //原始数组：101,34,119,1 int[] arr = {101,34,119,1}; for(int i=0; i<arr.length-1; i++) { //定义最小数下标 int minIndex = i; //假定最小数为第一个元素 int min = arr[i]; for (int j = i + 1; j < arr.length; j++) { if (min > arr[j]) { //说明假定的数不是最小值 min = arr[j]; //重置最小数 minIndex = j; //重置最小数索引 } } //将最小数，放在arr[0]中，交换 arr[minIndex] = arr[i]; arr[i] = min; System.out.println("第"+i+1+"轮后：" + Arrays.toString(arr)); } } }

插入排序

基本思想： 把n个待排序的元素看成一个有序表和无序表，开始时有序表中只包括一个元素，无序表中包括n-1个元素， 排序过程中每次从无序表中取出第一个元素，把他的排序码一次与有序表中的排序码进行比较，将他插入到有序 表中适当位置，使之形成新的有序表

代码实现：

public class InsertSort { public static void main(String[] args) { //原始数组 int[] arr = {101,5,-1,88,9,12}; for(int i=1; i<arr.length; i++) { //定义待插入的数（一个数组第一个数据设为有序表，之后数据设为无序表，无序表中的第一个数据和有序表中数据依次比较 int insertVal = arr[i]; //定义待插入的数前面的数的下标 int insertIndex = i - 1; /* 给待插入的数找到插入的位置 1.insertIndex >= 0 是为了保证待插入的数和前面比较时不会越界到-1, 2.insertVal < arr[insertIndex] 说明待插入的数还没有找到合适位置，需要交换 3.arr[insertIndex]要后移 */ while (insertIndex >= 0 && insertVal < arr[insertIndex]) { arr[insertIndex + 1] = arr[insertIndex]; //待插入的数后移； insertIndex--; //继续让待插入的数和前面的有序表中的数据进行比较 } //当退出while循环时，说明插入的位置找到，insertIndex + 1 arr[insertIndex + 1] = insertVal; } System.out.println(Arrays.toString(arr)); } }

希尔排序

基本思想： 记录按下表的一定数量分组，对每组使用直接插入排序排序，随着增量逐渐减少，每组包含的关键词越来越多，当增量为1时，整个文件恰好被分成一组，算法终止 代码实现:

public class DonaIdShellSort { public static void main(String[] args) { //原始数组8,9,1,7,2,3,5,4,6,0 int[] arr = {8,9,1,7,2,3,5,4,6,0}; //对一个数组进行分组，将他的长度除以2，当他大于0时执行（每次分组时除以2结果大于0，每次按照之前的分组再分组除以2 for(int group = arr.length/2; group>0; group /= 2){ for(int i=group; i<arr.length; i++){ //遍历所有元素，共group/2组，步长为group/2 for(int j=i-group; j>=0; j-=group){ //分组后的元素与他们对应的元素比较 if(arr[j] > arr[j+group]){ int temp = arr[j]; arr[j]=arr[j+group]; arr[j+group]=temp; } } } } System.out.println(Arrays.toString(arr)); } }

快速排序

基本思想： 通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分是所有数据都要小。然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列 代码实现：

public int[] quicklysort( int[] nums) { if(nums == null) return new int[0]; int len = nums.length; if(len <= 1) return nums; quicklysort(nums, 0, len-1); return nums; } private void quicklysort(int[] num, int left, int right) { if(left < right) { int middle = partition(num, left, right); quicklysort(num, left, middle-1); quicklysort(num, middle+1, right); } } private int partition(int[] nums, int left, int right) { int randomIndex = left + new Random().nextInt(right - left); int pivot = nums[randomIndex]; swap(nums, randomIndex, right); int i = left-1; for(int j=left;j<=right;j++) { if(nums[j] <= pivot) { i++; swap(nums, i, j); } } return i; } private void swap(int[] nums, int i, int j) { int temp = nums[i]; nums[i] = nums[j]; nums[j] = temp; }

归并排序

基本思想： 归并排序是一种效率较高的排序方法，它分为拆分和合并两大部分，先拆后合。 拆分，就是将一堆无序的数拆成单个，方便合并。 合并，就是将拆分好的数按照排序规则再拼凑起来 代码实现：

public class MergetSort { public static void main(String[] args) { int[] arr = {8,4,5,7,1,3,6,2}; int[] temp = new int[arr.length]; mergerSort(arr,0,arr.length-1,temp); System.out.println(Arrays.toString(arr)); } //分解+合并方法 public static void mergerSort(int[] arr, int left, int right, int[] temp){ if(left < right){ int mid = (left+right)/2; //向左递归 mergerSort(arr,left,mid,temp); //向右递归 mergerSort(arr,mid+1,right,temp); //合并 merget(arr,left,mid,right,temp); } } //合并方法 //(一)先把左右两边已经有序的数组填充到临时temp数组中，直到全部填充完毕 public static void merget(int[] arr, int left, int mid, int right, int[] temp){ int t = 0; //临时数组temp的当前索引 int i =left; //原始数组左边的有序数组索引 int j = mid + 1; //原始数组右边的有序数组索引 while(i<=mid && j<=right){ //左边有序数组的元素 小于等于 右边有序数组的元素时，将左边的元素填充到临时数组中 if(arr[i] <= arr[j]){ temp[t] = arr[i]; //分别将i，t右移 t++; i++; //否则的话就是右边的元素填充到临时数组中 }else { temp[t] = arr[j]; t++; j++; } } //(二)把剩余的元素填充到临时数组temp中 //发现比较完后有剩余元素 while(i <= mid){ temp[t] = arr[i]; t++; i++; } while(j <= right){ temp[t] = arr[j]; t++; j++; } //（三）将临时数组的数据拷贝到原始数组中 t = 0; int tempLeft = left; //临时temp数组的左边索引，注意的是这里每次拷贝的长度是不一样的 //说明临时存放元素的数组是个有序数组，进行拷贝到原数组 while( tempLeft <= right){ arr[tempLeft] = temp[t]; t++; tempLeft++; } } }

基数排序

基本思想： 将待排序序列的元素切分为许多个部分作为排序键，对序列的每一趟排序都会更换不同的键（由低位到高位或是由高位到低位）进行计数排序。这种排序思想要求每一趟排序都是稳定的，即相同键值的相对位置不会发生改变，而计数排序可以满足这个要求。 代码实现：

package 数据结构算法.排序.基数排序; import java.util.Arrays; /** * 扩展的桶排序 */ public class RadixSort { public static void main(String[] args) { int[] arr = {53,3,542,748,14,214}; radixSort(arr); } public static void radixSort(int[] arr){ //找到数组中的最大数,然后确定最大数的长度 int max = 0; for(int m=1; m<arr.length; m++) { if (arr[m] > max) { max = arr[m]; } } //得到数组中最大数的长度(得到最大数是个几位数),让最大数加上一个空字符串，得到这个字符串的长度 int maxLength = (max + "").length(); /* 定义一个二维数组，表示10个桶。每个桶都是一个一维数组，为了防止溢出，桶的大小设为arr.length */ int[][] bucket = new int[10][arr.length]; //定义一个每个桶中实际存放了多少个数据，比如：bucketElmmentCounts[0]记录的就是bucket[0]中存放了多少个数据 int[] bucketElmmentCounts = new int[10]; //循环进行排序 for(int i=0,n=1; i<arr.length; i++,n*=10){ //针对每个元素的对应位进行排序；第一次是个位。第二次是十位。第三次是百位... for(int j=0; j<arr.length; j++){ //取出每个元素对应位的值 int digitOfElmment = arr[j] / n % 10; //得到的对应位的值，放到对应的桶中 bucket[digitOfElmment][bucketElmmentCounts[digitOfElmment]] = arr[j]; bucketElmmentCounts[digitOfElmment]++; } //每一轮放入桶中后，按照放入的顺序取出，放入到原数组中 int index = 0; //遍历每一个桶，将桶中的数据放入原数组中 for(int k=0; k<bucket.length; k++){ //如果桶中有数据才放 if(bucketElmmentCounts[k] != 0){ //遍历桶中数据放入 for(int l=0; l<bucketElmmentCounts[k]; l++){ arr[index] = bucket[k][l]; index++; } } //每一轮排序后，将每个bucketElmmentCounts[k] = 0 ！！！！！！！！ bucketElmmentCounts[k] = 0; } } System.out.println(Arrays.toString(arr)); } }

堆排序

基本思想：

1、将待排序数组构造成一个大根堆（元素上升） 2、固定一个最大值，将剩余的数再构造成一个大根堆（元素下降）

代码实现：

public static void heapSort(int[] arr) { //构造大根堆 heapInsert(arr); int size = arr.length; while (size > 1) { //固定最大值 swap(arr, 0, size - 1); size--; //构造大根堆 heapify(arr, 0, size); } } //构造大根堆（通过新插入的数上升） public static void heapInsert(int[] arr) { for (int i = 0; i < arr.length; i++) { //当前插入的索引 int currentIndex = i; //父结点索引 int fatherIndex = (currentIndex - 1) / 2; //如果当前插入的值大于其父结点的值,则交换值，并且将索引指向父结点 //然后继续和上面的父结点值比较，直到不大于父结点，则退出循环 while (arr[currentIndex] > arr[fatherIndex]) { //交换当前结点与父结点的值 swap(arr, currentIndex, fatherIndex); //将当前索引指向父索引 currentIndex = fatherIndex; //重新计算当前索引的父索引 fatherIndex = (currentIndex - 1) / 2; } } } //将剩余的数构造成大根堆（通过顶端的数下降） public static void heapify(int[] arr, int index, int size) { int left = 2 * index + 1; int right = 2 * index + 2; while (left < size) { int largestIndex; //判断孩子中较大的值的索引（要确保右孩子在size范围之内） if (arr[left] < arr[right] && right < size) { largestIndex = right; } else { largestIndex = left; } //比较父结点的值与孩子中较大的值，并确定最大值的索引 if (arr[index] > arr[largestIndex]) { largestIndex = index; } //如果父结点索引是最大值的索引，那已经是大根堆了，则退出循环 if (index == largestIndex) { break; } //父结点不是最大值，与孩子中较大的值交换 swap(arr, largestIndex, index); //将索引指向孩子中较大的值的索引 index = largestIndex; //重新计算交换之后的孩子的索引 left = 2 * index + 1; right = 2 * index + 2; } } //交换数组中两个元素的值 public static void swap(int[] arr, int i, int j) { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; }