复杂度排序：O(1) < O(log2n) < O(n) < O(nlogn) < O(n2) < O(n3) < O(nk) < O(2n)
1. 冒泡排序
1.1 介绍
- 冒泡排序（Bubble Sorting）的基本思想是：通过对待排序序列坐标从前往后，依次比较相邻的值，若发现逆序，就进行交换。
优化思想：如果发现整体从前向后判断完毕，未进行交换，那么说明已经达成顺序，无需进行排序，直接结束循环。
1.2 实现
public class BubbleSort {public void bubble(int[] arr){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]){int temp = arr[j+1];arr[j+1] = arr[j];arr[j] = temp;}}}}public void bubblePlus(int[] arr){boolean flag = false;for (int i=0;i<arr.length-1;i++){if (flag) return;flag = true;for (int j=0;j<arr.length-1-i;j++){if (arr[j]>arr[j+1]){flag = false;int temp = arr[j+1];arr[j+1] = arr[j];arr[j] = temp;}}}}}
注意：
- 外循环次数是length-1，因为要比较arr[j]与arr[j+1]，以防止数组越界。
- 里循环次数是length-i-1,因为通过一次循环冒泡，已经将最大值放到了数组末尾，因此无需对最后一个数进行判断。
2. 选择排序
2.1 介绍
属于内部排序法，通过每一次遍历找到最小的数并记录其坐标，与对应数组中对应位置的数进行交换，最终实现顺序排列。
2.2 实现
public class SelectSort {public void select(int[] arr){for (int i=0;i<arr.length-1;i++){int min = arr[i];int minIndex = i;for (int j=i+1;j<arr.length;j++){if (arr[j]<min) {min = arr[j];minIndex = j;}}arr[minIndex] = arr[i];arr[i] = min;}}}
注意：
- 外循环处理次数为length-1，因为当length-1个数排序完成，自然最后一个数就是最大数。
- 里循环处理从i+1开始，因为第i-1个位置已经处理完毕，是对应坐标的第i+1小的数；这时设置arr[i]为最小数，直接让其与其后面所有数进行判断即可。因此直接从i+1开始，以数组中最后一个数结束。
3. 插入排序
3.1 介绍
插入排序属于内部排序法，是对预处理的元素以插入的形式查找适当的位置进行插入，以达到排序的目的。
3.2 思想
插入排序（Insertion Sorting）的基本思想是：把n个元素看成两个表（一个有序表和一个无序表），开始时，有序表只有一个元素，无序表元素个数为n-1；排序过程就是从无序表中取出一个元素，让它与有序表中的元素进行判断，找到合适的位置进行插入操作。直至所有无序表中的元素都完成插入，这样实现了整体排序。
3.3 实现
public class InsertSort {/** 分成两个表(一个有序表,一个无序表),整个过程为 "无序表 -> 有序表"* 1. 选取第一个数作为一个有序表, 剩下的n-1为一个无序表* 2. 遍历循环n-1个数,与前面的有序表进行比较,找到位置进行插入* 3. 插入需要将无序表中当前正在判断的元素进行一个循环直到所有值都覆盖后* 4. 给指定位置赋值要插入的元素*/public void insertSort(int[] arr){int length = arr.length;// 选取有序表int num = arr[0];int index = 0;// 遍历无序表进行比较for (int i=1;i<length;i++){// 进行排序比较的数int x = arr[i];for (int j=0;j<=index;j++){if (x<arr[j]){for (int k=i;k>j;k--){arr[k] = arr[k-1];}arr[j] = x;index++;break;}}}}}
更高级的实现
- 在找插入位置时，前者方法是从头开始找，这里是从有序表的最后一个数开始找，并伴随着值的覆盖
代码更加简洁
public void insertSortPlus(int[] arr){for (int i=1;i<arr.length;i++){int val = arr[i];int index = i-1; // 找到当前无序表头元素中的前一个元素,也就是有序表的最后一个元素while(index>=0&&val<arr[index]){arr[index+1] = arr[index];index--;}arr[index+1] = val;}}
3.3 弊端
对于简单插入排序
- 如果数组是arr = {2,3,4,5,6,7,1}，在处理1这个元素时
使用上述的insertSortPlus就需要一个一个向前赋值并判断
结论：当使用简单的插入排序去处理较小的数时，后移的次数会比较多，直接影响排序的效率。
4. 希尔排序
4.1介绍
希尔排序是一种插入排序方法，它在简单的插入排序基础上，进行改进，变得更加高效，也称为缩小增量排序。
4.2 基本思想
希尔排序会把记录按下标一定增量进行分组，对每组直接使用插入排序算法。执行完成后，增量/2，随着增量减少，每组的需要处理的元素增多；最后当增量到1时，进行整体的一次插入排序，结束希尔排序。
4.3 实现
交换式：
public class ShellSort {public void shellSort(int[] arr){// 设置 "增量" 以及 "增量的变化规则" 和 "算法停止的规则"for (int group= arr.length/2;group>0;group/=2){// 增量分配后, 每组元素的处理从group坐标开始,不断往前进行交换,直到最后一个元素为止for (int i=group;i<arr.length;i++){// 给定一个坐标,根据group的分配,与通过j-=group保证与同组元素进行处理for (int j=i-group;j>=0;j-=group){// 当前需要实现顺序排列,因此当后面的元素小于前面的元素时,执行交换if (arr[j+group]<arr[j]){int temp = arr[j+group];arr[j+group] = arr[j];arr[j] = temp;}}}}}}
移位式：
// 移位式 public void shellSortPlus(int[] arr){ // 分组 for (int group= arr.length/2;group>0;group/=2){ // 从索引group开始,让每个元素与该元素索引前的所有同组元素进行插入排序 for (int i=group;i<arr.length;i++){ // i坐标位置为当前组最后一个元素,将这个元素当成有序表 int index = i; int val = arr[i]; if(val<arr[index-group]){ while(index-group>=0 && val<arr[index-group]){ arr[index] = arr[index-group]; index-=group; } arr[index] = val; } } } }5. 快速排序
5.1 介绍
快速排序（QuickSort）是对冒泡排序的一种改进。
基本思路：
- 找到中间位置（一般采用（left+right）/2）
- 以中间位置为基准，进行排序，将小于该中间位置对应数的放在中间位置的左边，将大于该中间位置对应数的放在中间位置的右边
- 实现这种排序的方式是，左边一个指针从头向后开始扫描，直到一个大于中间值的数，右边从尾向前开始扫描，找到一个小于中间值的数，然后让两者进行交换
然后将中间值左边的一段当成一个单独的数组，也进行如上操作，这里直接通过递归实现；同理中间值右边也是如此
5.2 实现
public class QuickSort { public void quickSort(int[] arr,int left,int right){ /** * 1. 找到中间值,将未排序的数组根据中间值分为两个部分 * 2. 根据中间值进行两边的排序 * 3. 排序完成后,判断条件是否满足,进而执行递归 */ // 记录传过来的左右左标,后面使用这两个指针进行操作 int l = left; int r = right; // 找到当前给定的数组段的中间值 int pivot = (left+right)/2; int pivotVal = arr[pivot]; // 当l<r,表示还没有完全扫描,因此需要继续进行 while(l<r){ // 找到左右两边不满足条件(左边的数小于中间值,右边的数大于中间值)的数 while(arr[l]<pivotVal) l++; while(arr[r]>pivotVal) r--; // 避免都移位到了中间值位置的情况 if (l>=r) break; int temp = arr[l]; arr[l] = arr[r]; arr[r] = temp; if (l==pivot) r--; if (r==pivot) l++; } if (l==r){ l++; r--; } // 递归 if (left<r) quickSort(arr,left,r); if (right>l) quickSort(arr,l,right); } }
6. 归并排序
6.1 介绍
归并排序(MERGE-SORT)是利用归并的思想实现的排序方法，该算法采用经典的分治（divide-and-conquer）策略（分治法将问题分（divide）成一组小问题然后归并进行求解，而治（conquer）的阶段则将得到的各种答案“修补”在一起，即分而治之）。
6.2 图解
6.3 思想
- 将整个数组不断分解，最终变成单个元素，然后每两个相邻元素进行一组进行“治”，然后组成一个两个元素的数组；第一次“治”结束后，继续进行将相邻的两组数组进行“治”，不断进行，最终拼凑成一个完整的数组。
“治”的过程：
- 使用两个指针从头开始扫描，比较两组元素中指定元素的大小，将小的那个放入temp临时数组中，不断扫描直到一方扫描都当前阶段的数组的末尾。
- 当上述循环结束后，将会只有一方数组剩余，或者都没有剩余，将剩余数组中的元素依次存放入temp数组中
-
6.4 实现
public class MergeSort { public void mergeSort(int[] arr,int left,int right,int[] temp){ // 保证分到单个时停止 if (left<right){ int mid = (left+right)/2; // 分 mergeSort(arr,left,mid,temp); mergeSort(arr,mid+1,right,temp); // 治 merge(arr,left,mid,right,temp); } } public void merge(int[] arr,int left,int mid,int right,int[] temp){ int i = left; int j = mid+1; int t = 0; while(i<=mid && j<=right){ // 治: 两个指针指对应的数组扫描,进行比较,然后将小的数优先放入temp临时数组中 if (arr[i]<=arr[j]){ temp[t] =arr[i]; i++; }else { temp[t] =arr[j]; j++; } t++; } // 再将剩余部分全部放入数组中 while(i<=mid){ temp[t] = arr[i]; t++; i++; } while(j<=right){ temp[t] = arr[j]; j++; t++; } // 将temp数组拷贝到arr中 t = 0; // 重新指向第一个元素,准备进行遍历赋值 int tempLeft = left; // left不能改变,但是需要使用它的值 while(tempLeft<=right){ arr[tempLeft] =temp[t]; t++; tempLeft++; } } }
7. 基数排序(桶排序)
7.1 介绍
- 桶排序的扩展
- 基数排序（radix sort）属于“分配式排序”（distribution sort），又称“桶子法”（bucket sort）或“bin sort”，它是通过键值的各个位的值，将要排序的元素分配至对应的桶之中，然后依次取出，然后再放入取出，循环直到所有数的每个位都进行过处理，那么最后取出的一个数组就是一个顺序。
-
7.2 思想
-
7.3 实现
public class RadixSort { public void radixSort(int[] arr){ /** * 1. 获取最大数的位数(作为大循环的执行次数) * 2. 初始化桶和桶中元素的计数器(这里使用一个数组模拟桶计数器,把每个桶中的元素个数数据聚集成一个整体,并且还通过其进行桶中添加元素的指针) * 3. 入桶,执行最大位次数;需要一个n,通过变化(*10)进而改变对不同位的数处理 * 4. 出桶,与入桶在一个大循环之中,因为每次入桶结束,必须要执行出桶,依次循环才能实现排序循环次数是10次(所有桶都要判断是否有元素,有则循环遍历出桶) * 5. 循环完毕,实现排序 */ //1. 获取最大数的位数(作为大循环的执行次数) int max = arr[0]; for (int i=1;i<arr.length;i++){ if (arr[i]>max) max = arr[i]; } int maxLength = (""+max).length(); // 2. 初始化桶和桶中元素的计数器(这里使用一个数组模拟桶计数器,把每个桶中的元素个数数据聚集成一个整体,并且还通过其进行桶中添加元素的指针) int[][] bucket = new int[10][maxLength]; int[] bucketElementCounts = new int[10]; // 需要给10个桶计数 // 3. 入桶,执行最大位次数;需要一个n,通过变化(*10)进而改变对不同位的数处理 for (int i=0,n=1;i<maxLength;i++,n*=10){ // 入桶 for (int j=0;j< arr.length;j++){ int digitOfElement = arr[j]/n%10; bucket[digitOfElement][bucketElementCounts[digitOfElement]++] = arr[j]; } // 出桶 int index = 0; for (int k=0;k<10;k++){ if (bucketElementCounts[k]>0){ for (int l=0;l<bucketElementCounts[k];l++){ arr[index++] = bucket[k][l]; } } bucketElementCounts[k] = 0; } } } }
8. 堆排序
8.1 介绍
若有收获，就点个赞吧
0 人点赞
