⭐交换排序
🎄5. 冒泡排序
思路：
比较 相邻的两个元素。如果第一个比第二个大则交换他们的位置(升序排列，降序则反过来)。
从列表的开始一直到结尾，依次对每一对相邻元素都进行比较。这样，值最大的元素就通过交换“冒泡”到了列表的结尾，完成第一轮“冒泡”。
重复上一步，继续从列表开头依次对相邻元素进行比较。已经“冒泡”出来的元素不用比较(一直比较到结尾也可以，已经“冒泡”到后面的元素即使比较也不需要交换，不比较可以减少步骤)。
继续从列表开始进行比较，每轮比较会有一个元素“冒泡”成功。每轮需要比较的元素个数会递减，一直到只剩一个元素没有“冒泡”时(没有任何一对元素需要比较)，则列表排序完成。
算法优化
如若在一轮排序中没有发生位置的交换，那么说明数据已经有序，不用继续进行后边的排序了
图解：
代码实现：
/** * 时间复杂度： * 最好最坏都是O(n^2) 但是：如果优化了 ，有序的时候就是O(n) * 空间复杂度：O(1) * 稳定性：稳定的排序 * 冒泡 直接插入 * @param array */ public static void bubbleSort(int[] array) { for (int i = 0 ;i < array.length-1; i++){//外循环只用length-1趟 boolean flg = false;//记录当前这一趟是否有换位子 for (int j = 0 ; j <array.length-1-i ; j++){//内循环array.length-1-i趟 if (array[j] > array[j+1]){ int tmp = array[j]; array[j] = array[j+1]; array[j+1] = tmp; flg = true; } } if (flg==false) {//如果当前趟没换位置，说明已经有序，不需要再排序了 break; } } }
🎄6. 快速排序
思路：
快速排序使用 分治策略 来把一个序列（list）分为两个子序列（sub-lists）。步骤为：
从数列中挑出一个元素，称为"基准"（pivot）。
①选择边上（左或者右）默认用这种方式
②随机选择
③几数取中（例如三数取中）：array[left], array[mid], array[right] 大小是中间的为基准值
重新排序数列（挖坑法），所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准后面（相同的数可以到任一边）。在这个分区结束之后，该基准就处于数列的 中间位置。这个称为分区（partition）操作。
递归地（recursively）把小于基准值元素的子数列和大于基准值元素的子数列排序。
递归到最底部时，数列的大小是零或一，也就是已经排序好了。这个算法一定会结束，因为在每次的迭代（iteration）中，它至少会把一个元素摆到它最后的位置去。
图解：
代码实现：
/** * 时间复杂度： * 最好：O(n*logn) 均匀的分割下 * 最坏：o(n^2) 数据有序的时候 * 空间复杂度： * 最好：logn * 最坏：O(n) * 稳定性：不稳定的排序 * * k*n*logn * 2 * 1.2 * @param array */ public static void quickSort(int[] array) { sort(array, 0, array.length - 1); } private static void sort(int[] array, int low, int high) { int i = low; int j = high; if (array.length <= 1) { return; } if (i >= j) { return; } int pivot = array[i]; //跳出while循环之后，因为循环的条件是i<j,所以，跳出循环时，i和j是相等的 while (i < j) { //哨兵i从左往右找 while (i < j && array[j] >= pivot){ j--; } //哨兵j从右往左找 while (i < j && array[i] <= pivot){ i++; } //如果满足条件则交换两个数在数组中的位置 if (i<j) {//当哨兵i和哨兵j没有相遇时 int t = array[j]; array[j] = array[i]; array[i] = t; } } //最终基准数归位 array[low] = array[i];//一开始low位置的数就是基准数 array[i] = pivot;//i下标值就是pivot基准值，由此可以递归左右两边的序列 sort(array, low, i - 1);//继续处理左边的，这里是递归的过程 sort(array, i + 1, high);//继续处理右边的，这里是递归的过程 }
非递归实现快速排序（重点掌握递归实现）
/** * 非递归实现快速排序 * @param array */ public static void quickSort_FDG(int[] array) { Stack<Integer> stack = new Stack<>(); int start = 0; int end = array.length-1; int pivot = partition(array,start,end); //左边有2个元素及以上 if(pivot > start+1) { stack.push(0); stack.push(pivot-1); } if(pivot < end-1) { stack.push(pivot+1); stack.push(end); } while (!stack.empty()) { end = stack.pop(); start = stack.pop(); pivot = partition(array,start,end); //左边有2个元素及以上 if(pivot > start+1) { stack.push(0); stack.push(pivot-1); } if(pivot < end-1) { stack.push(pivot+1); stack.push(end); } } }
⭐🎄7. 归并排序·
思路：
归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide andConquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。
图解：
分而治之
可以看到这种结构很像一棵完全二叉树，本文的归并排序我们采用递归去实现（也可采用迭代的方式去实现）。“分” 阶段可以理解为就是递归拆分子序列的过程，递归深度为log2n。
2.合并相邻有序子序列
再来看看 “治” 阶段，我们需要将两个已经有序的子序列合并成一个有序序列，比如上图中的最后一次合并，要将[4,5,7,8]和[1,2,3,6]两个已经有序的子序列，合并为最终序列[1,2,3,4,5,6,7,8]，来看下实现步骤。
代码实现：
public static void merge(int[] array,int low,int mid,int high) { int s1 = low; int e1 = mid; int s2 = mid+1; int e2 = high; int[] tmp = new int[high-low+1]; int k = 0;//代表tmp数组的下标 while (s1 <= e1 && s2 <= e2) { if(array[s1] <= array[s2]) { tmp[k++] = array[s1++]; //k++; //s1++; }else { tmp[k++] = array[s2++]; } } //有2种情况 while (s1 <= e1){ //说明第2个归并段没有了数据 把第1个归并段剩下的数据 全部拷贝过来 tmp[k++] = array[s1++]; } while (s2 <= e2) { //说明第1个归并段没有了数据 把第2个归并段剩下的数据 全部拷贝过来 tmp[k++] = array[s2++]; } //tmp数组当中 存储的就是当前归并好的数据,现在还需要拷贝到原数组中 //这样的代码是错误的 /*for (int i = 0; i < array.length; i++) { array[i] = tmp[i]; }*/ for (int i = 0; i < tmp.length; i++) { array[i+low] = tmp[i];//加上对应的low，用来处理第二个归并段，如果是第一个归并段，low=0 } } public static void mergeSortInternal(int[] array,int low,int high) { if(low >= high) { return; } int mid = (low+high) / 2; mergeSortInternal(array,low,mid);//分解前半段 mergeSortInternal(array,mid+1,high);//分解后半段 //合并的过程 merge(array,low,mid,high); } /** * 时间复杂度： O(N*log n) * 空间复杂度：O(N) * 稳定性：稳定的 * @param array */ public static void mergeSort(int[] array) { mergeSortInternal(array, 0,array.length-1); }
非递归实现归并排序（了解即可，重点掌握递归实现）：
/** * 非递归实现 归并排序 * @param array * @param gap */ public static void merge2(int[] array,int gap) { int[] tmp = new int[array.length]; int k = 0; int s1 = 0; int e1 = s1+gap-1; int s2 = e1+1; //int e2 = s2+gap-1 >= array.length ? array.length-1 : s2+gap-1; int e2 = s2+gap-1 < array.length ? s2+gap-1 : array.length-1; //保证有两个归并段 while (s2 < array.length) { while (s1 <= e1 && s2 <= e2) { if(array[s1] <= array[s2]) { tmp[k++] = array[s1++]; }else { tmp[k++] = array[s2++]; } } while (s1 <= e1) { tmp[k++] = array[s1++]; } while (s2 <= e2) { tmp[k++] = array[s2++]; } //一组完了 确定新的区间的开始和结束 s1 = e2+1; e1 = s1+gap-1; s2 = e1+1; e2 = s2+gap-1 < array.length ? s2+gap-1 : array.length-1; } //e2 > array.length while (s1 <= array.length-1) { tmp[k++] = array[s1++]; } for (int i = 0; i < tmp.length; i++) { array[i] = tmp[i]; } } public static void mergeSort_FDG(int[] array) { for (int i = 1; i < array.length; i*=2) { merge2(array,i); } }
🛸非基于比较的排序
🎄8. 基排序
思路：
基数排序的思想就是先排好 个位，然后 排好个位的基础上排十位，以此类推，直到遍历最高位 次，排序结束（仔细理解最后一句话）
基数排序不是比较排序，而是通过分配和收集的过程来实现排序
初始化10个桶(固定的)，桶下标为0-9
通过得到待排序数字的个十百等位的数字，把这个数字对应的item放到对应的桶中
基数排序有两种排序方式：LSD和MSD，最小位优先(从右边开始)和最大位优先(从左边开始)
图解：
代码实现：
public static void radixSort(int[] array) { ArrayList<ArrayList<Integer>> queue = new ArrayList<>(); for (int i = 0; i <10 ; i++) { queue.add(new ArrayList<>());// 创建一个基数从0---9 每个数字上都是一个list } // 找到最大值，并判断最大值是几位数 int max = array[0]; for (int i = 1; i < array.length; i++) { if (max < array[i]) { max = array[i]; } } int time = 0; while (max > 0) { max /= 10; time++; } for (int i = 0; i < time; i++) {// 循环每一个位数（个位、十位、百位） for (int j = 0; j < array.length; j++) {// 循环数组，取每一个值 int x = array[j] % (int) Math.pow(10, i + 1) / (int) Math.pow(10, i); ArrayList<Integer> queue3 = queue.get(x); queue3.add(array[j]); queue.set(x, queue3); } int count = 0; for (int k = 0; k < 10; k++) { while (queue.get(k).size() > 0) { ArrayList<Integer> queue4 = queue.get(k); array[count] = queue4.get(0); queue4.remove(0); count++; } } } }
🗽总结
一个稳定的排序，可以变成不稳定的排序但是一个不稳定的排序，不可能变成稳定的排序
