8.桶排序 桶排序 (Bucket sort)是一种排序思想。工作的原理是将数组分到有限数量的桶子里。每个桶子再个别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序）。当要被排序的数组内的数值是均匀分配的时候，桶排序使用线性时间（Θ（n））。但桶排序并不是 比较排序，他不受到 O(n log n) 下限的影响，受数据状况的影响较大。 1、非基于比较的排序，与被排序的样本的实际数据状况很有关系，所以实际中并不经常使用2、时间复杂度O(N)，额外空间复杂度O(N)3、稳定的排序 计数排序和基数排序是桶排序的实际运用。 桶排序运用（求相邻两数的最大差值） 给定一个数组，求如果排序之...

7.堆排序（快，不稳，使用较多） 总结 时间复杂度O(N*logN)，额外空间复杂度O(1)堆结构非常重要1，堆结构的heapInsert与heapify2，堆结构的增大和减少3，如果只是建立堆的过程，时间复杂度为O(N)4，优先级队列结构，就是堆结构 大根堆的插入heapInsert 将一个数加入到堆中的过程： 1.首先与父亲节点比较，当比父节点大时，发生交互，并更新自己的index； 2.重复步骤1。直到比父节点小，或者已经到堆顶时，停止。 时间复杂度：logN,最多比较已有数的高度。 static void heapInsert(int[] a,int index){ int paren...

6.快速排序(量大时特快,不稳定,对基础类型 随机快排最常用) 快排的几种写法: (基本快排,随机快排,优化随机快排,双轴快排) 时空分析: 平均时间复杂度:n*logn ;空间复杂度logN （因为要记录断点【放在数组的位置】，用数组记录相等的范围） 如果不用随机快排,最坏时间复杂度为N*2,随机快排最坏为nlogN 简单快排： 选第一个数字作为基准，分两个区 核心代码: public static void qucikSort1(int[] A, int L, int R){ if(L < R){ int pivot = A[L];//最左边的元素作为中轴元素 int i = L;/...

5.归并排序(较快,稳定,对象排序最常用) 1.归并排序: 1.将数组分为两个数组,将两个数组排序后合并;2.子数组的排序可以递归调用归并排序(也可规模较小时用插入排序) 归并分为 mergeSort()分的过程 和merge()合的过程。 mergeSort()分将一个数组均分成左边和右边，左边和右边再递归调用各自的mergeSort();然后再将左边右边merge(); merge()合是将两个有序数组合成一个新数组的过程。通过left，mid，right；将数组分成的两个有序的范围子数组合并。 //归并排序(时间复杂度为N*logN,稳定;数据库,Java,Python的对象排序都用它)...

4.希尔排序（相对较快,不稳定） 思想： 先确定一个间隔，我们从0开始，每经过一个间隔取一个数，把这些数分成一组，把这一组数用插入排序排好。然后将间隔逐渐变小，循环该过程。 为什么比插入排序的效率高？ 因为如果1在比较后面的位置，它要排到最前面必须经过很多次交换。如果用希尔排序，因为有间隔，所以只需要很少的次数就能把1排到前面。这就是它能提高效率的地方。希尔排序也叫改进排序。 希尔排序在间隔较大的时候交换的次数比较少，间隔小的时候交换的距离比较近。但希尔排序是跳着排的，所以不稳定。 实现： //希尔排序(也叫改进排序,是对插入排序的改进;时间复杂度为n**1.3,空间为1,不稳定) //思想:...

3.插入排序(小样本,基本有序时最快;稳定) 插入排序在工业和实际中应用比较多,当样本量小于60且基本有序时使用; 使用插入排序,可以保证排序数组的稳定性.经常在归并排序和快排中子数组规模小时使用. 普通插入排序: //插入排序(相对冒泡和选择较好,但时间复杂仍为n**2,空间为1,稳定) //思想:同打牌,将新摸到的牌插入到已排好的牌面上 //操作:每次将后面的数插入到前面已排好的数组中 static void insertionSort(int[] a ){ //NK for(int j=1;j<a.length;j++) { //N for (int i = j; i > 0...

选择排序与冒泡排序的使用很少，但依旧经典。 1.选择排序(慢,不稳定) //选择排序(时间复杂度为N**2,空间为1,不稳定) //每次找到最小的放在最前面,每次循环比较n次,换一次 for (int i = 0; i < arr.length - 1; i++) { int minIndex = i; for (int j = i + 1; j < arr.length; j++) { minIndex = arr[j] < arr[minIndex] ? j : minIndex; } swap(arr, i, minIndex); } //选择排序的优化 //每次循环找...

0.排序相关辅助函数(重点:对数器) 1.简单排序的交换函数[位运算版] (注意:位运算优先级较低,复合运算的时候需要加上小括号) 位运算一般较快.（但特殊情况自己与自己交换会变为0，如快排和堆排） public static void swap(int[] arr, int i, int j) { arr[i] = arr[i] ^ arr[j]; arr[j] = arr[i] ^ arr[j]; arr[i] = arr[i] ^ arr[j]; } 普通版：（辅助变量temp，适合所有场景，较慢） public static void swap(int[] arr, int i, in...

排序 总结 选泡快插基 统计堆归希   1.基于比较的排序 1）简单排序（熟练掌握插排） 1、选择排序 人的排序思想；每次选出最大（最小），不稳，特慢。 优化：每次同时选出最大和最小，放在头和尾。 最好、最坏、平均时间复杂度均为N**2 2、冒泡排序 类似鱼吐泡泡；相邻比较交换，每次将最大(或最小)换到正确位置，稳定，特慢 优化：第一次遍历完数组，没有发生交换直接返回。 最好时间复杂度为N，最坏、平均时间复杂度为N**2 3、插入排序 类似扑克插牌；每次将一个数插入到已排好序的数组中。稳定、较快。数组越有序，插入排序越快。当数据量小于60时，一般默认用插排。 优化1：通过二分查找直接找到要插入...

​ 网上有一句话，老师教什么是发动机，面试问会不会造飞机，工作让好好拧螺丝。 ​ 大学总是教一些特别底层基础的知识，面试总是问最新的技术和框架，而工作总是做一些比较基本的CRUD和点点点。大多数人在学习时感觉复杂枯燥，面试时感到惊恐无助，工作时感到乏味无聊，于是不知路在何方又该何去何从。 ​ 这让我想到一个故事，一名记者问三个正在砌墙的砖瓦工，你们在干什么？砖瓦工甲说：“没看见吗，我正在砌墙。”乙说：“我正在建造一栋高楼。”丙说：“我正在建一座城市。”若干年后，甲还在工地上砌墙，乙成为了工程师，丙成为了城市规划者。 ​ 故事简短而奇幻，但仔细一想又跟我们现在生活多么贴切。简单拿学习来说，如果学...