主要核心有7个排序一、直接插入排序时间复杂度O(N^2) 空间复杂度O(1) 稳定排序核心是将数组分为两个区间有序区间和待排序区间每次拿待排序区间第一个元素跟已排序区间从后往前比较大于才进行后移操作(保证稳定性)Java实现其中arr[cur1]value放在外面是为了保证下标为0的位置也可以插入元素C实现二、希尔排序时间复杂度最好能达到(N^1.3) 空间复杂度是O(1) 不稳定排序希尔排序是对直接插入排序的一种变形对直接插入排序当数组本身就有序跟要排的顺序一致或数组的小元素在前大元素在后时时间复杂度会下降。希尔排序利用这一点现将数组中元素分组对每组中数据进行直接插入排序最后再将分组个数减少最后到一组Java实现gap从 size/2 开始每次gap/2判断条件不能写gap1,会死循环所以最后加一个gap1时的希尔排序保证最后有序C语言实现这里gap每次除31这样不会死循环分组的次数也大三、选择排序时间复杂度O(N^2) 空间复杂度O(1) 不稳定排序使用了找数组中最值的思想也是分为待排序区间和已排序区间从待排序区间的首元素开始拿着它跟后面的元素比较比首元素小就交换找大放前面也行Java实现C语言实现四、堆排序时间复杂度O(NlogN) 空间复杂度O(1) 不稳定排序原理就是每次建立大堆的时候数组中最大的元素会被放在首元素小堆相反这样就可以每次让大堆的首元素与最后一个位置的元素交换减少堆中有效数据个数再向下调整重复操作Java实现C语言实现五、冒泡排序时间复杂度O(N^2) 空间复杂度O(1) 稳定排序原理很简单就是每次把最大值/最小值换到数组边上从前开始换小的从后开始换大的JavaC语言六、快速排序找一个基准值用最右边的定义两个指针分别从左右开始左边找到的就停下来右边找到的就停下来再交换。最后将left与right相遇位置数据与最右边数据交换此时这个基准值在数组中就有序了在返回相遇位置数组下标以[left,index-1] [index1,right]作为新区间重新进行。Java递归实现Java中非递归实现用一个栈对边界值进行保存C语言实现这是以最左边为基准值左边拿到的是基准值的右边拿到的是基准值的因为是拿beginend作为判断条件所以begin跟end会错位最后要返回end下标换有另一个写法快慢指针法定义一个cur一个prev将基准值的放右边的放左边每次cur走到小于基准值的地方就让prev若prev!cur就交换直到cur超出范围C语言非递归实现同样要借助栈来模拟后入先出的情况避免重复值太多使用三路划分保存key的值cur从left1开始arr[cur]小于基准值就跟left换换完leftcur,大于就和right换换完right--直至小于基准值数据换来换去会有很多无意义的操作官方数据库快排到一定深度时使用其他排序七、归并排序时间复杂度O(NlogN) 空间复杂度O(N) 稳定排序利用链表合并的思想将数组分为数组长度份单个元素让后再拼起来Java递归实现Java非递归实现这个非递归实现不需要栈来模拟后入先出的场景因此不需要栈只要一个size从1开始将数组分组相邻两组一合并因为采取[,)当mid或者rightsize时要让他sizeC语言递归实现与java大同小异区别就是C语言不能new数组所以一次申请一个相同长度的数组C语言非递归实现C语言对文件的归并排序八、计数排序时间复杂度O(Nrange) 空间复杂度O(range) 不稳定排序计数排序利用了哈希的思想拿待排序数据元素的值当新数组下标新数组的值当出现次数
