3-18(排序的完结)
排序：
就是使一串数据，按照其中的某个或某些关键字大小，递增或递减的排序操作。
稳定性指的是：当有相同元素时，排序完成后可以保证其相对位置不变，则就是稳定，如果不能保证其相对位置不变，那就不是稳定的。
1、插入排序
直接插入排序：在一个有序的序列中插入数据，使其序列仍然有序。
时间复杂度为O(N^2),最好情况为O(N)。
空间复杂度为O(1)
是一种稳定的排序算法。
希尔排序：先选定一个整数gap，把待排序的数据分为若干组，并对每一组进行排序。也就是直接插入排序的优化，根据gap大小，先进行了一次预排序，再将gap依次改变直到为1，其排序就是直接插入排序了。gap一定为：gap=gap/n+1;加1是为了gap一定会等于1.
当gap>1时，都是预排序，当gap=1时，就为直接插入排序。
时间复杂度为O(N^1.3)
是不稳定的排序。
2、选择排序
思想：每次在待排序数据中选出最小或最大的数据，存放在序列的起始位置。
直接选择排序：效率非常低，
时间复杂度为O(N^2);
空间复杂度为O(1);
排序算法不是稳定的。
堆排序：是利用建堆来排序的。
如果需要降序，则建小堆，如果升序，则建大堆。
时间复杂度为O(N*logN)
空间复杂度为O(1);
是不稳定的排序算法。
3、交换排序
冒泡排序：就是将数据一一比较，每次比较完成都会产生一个数，在其自己位置上，需要比较n-1次。
时间复杂度为O(N^2)。
空间复杂度为O(1)。
时稳定的排序算法。
快速排序
时间复杂度为O(N*logN)
空间复杂度为O(logN)
不稳定的排序算法。
hoare法（左右指针法）
就是将begin和end依次移动，如果升序，则begin这段找大与key，end找小于key的，找到就互换，知道begin==end。
最右边做key，左边先走，左边做key，右边先走。因为这样做，一定可以确定最后停的位置会和key交换。
挖坑法：
就是找左/右一端为key，使其为一个空位，在其右/左找个数插入其坑位，这样被插入数据的位置就变为坑位，再在左/右找个数插入，知道begin==end。
前后指针法
定义2个变量prev和cur，cur=begin,prev=begin-1;cur找小，遇到小，则prev前进一个，再互换cur和prev的值。遇到大，则cur前进，prev不变。
快排什么情况下最慢： 数据有序的时候。可以利用三数取中法来解决这个问题。
将快排的递归转化为非递归。利用栈就可以，将待排数据的下标放到栈里面。利用栈实现递归的过程
因为递归有时候会造成栈溢出。所以需要非递归。
4、归并排序
思想：就是将2个有序的序列，归并为一个有序的序列。
时间复杂度为O(NlogN)
空间复杂度为O(N)
稳定的排序算法
5、计数排序（非比较排序）
思想：1、统计每个元素出现的次数。再按照次数将每个元素返回回去。
按照最大值与最小值之间的差值，来定义统计次数数组的大小range.
时间复杂度为O(MAX(range,N))
空间复杂度为O(range)
是个稳定的排序算法。
补充知识点：
假设有一个10个G的大文件，需要将此排序。
可以将这个10G大文件切成10个1G的小文件，放到内存里面对这10个进行排序（建议使用快排），然后将这10个排好序的文件进行归并，得到一个10G有序的大文件。
主要需要注意：归并排序，计数排序，今天刚刚学的。
你的鼓励让我更有动力
赞赏
0人进行了赞赏支持
更多相关文章
- 排序算法——快速排序
- 排序算法——插入排序
- 2021-03-17：手写代码：单链表插入排序。
- 3-17（排序）
- 排序算法——选择排序
- 排序算法——冒泡排序
- 2021-03-16：手写代码：单链表归并排序。
- BAT iOS算法面试题（汇总）
- 必读|spark的重分区及排序