思路：
将待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割为两子序列，做子序列中所有元素都小于基准值，右子序列所有元素都大于基准值，然后左右子序列重复该过程，知道所有元素都排列在相应位置上为止。
代码：
其中分为三种方法：
1.hoare版本的快排：
以左边或者右边作为基准值都可以，但是需要注意如果是左边做基准值则先从右边开始找小，再到左边找大。基本思路是，先执行一轮找到基准值的最终位置，假设最左边的值为基准值，当left小于right则进入循环，在循环中先在右边找小于基准值的值并记录下该值的下标，然后在左序列找比基准值大的值，交换这两个值的位置。注意在右边找小左边找大的时候可能会出现越界问题所以在这里需要做多一次判断left是否小于right，还有可能出现等于基准值的情况，当等于基准值时不做交换。当left和right相遇时，返回相遇下标，该下标将原序列分为两个区间，再递归对这两个区间进行新一轮的排序。结束条件则是当begin大于或者等于end时则说明该区间只剩一个元素则不需要继续递归进行排序。
2.挖坑法快排：
假设基准值还是最左侧的值，并引入一个新的变量hole，第一次进入循环的hole=left，先在右边找小，将小的值放入hole的位置上，并将刚刚找到的小的位置设为新的hole，再进行左边找大，将大的值放在hole的位置上，并将此时找到大的位置设为新的hole如此循环。当left和right相遇时跳出循环，并将一开始记录的基准值放在最后的hole上，此时的hole就是基准值的最终位置。这是一轮循环找到一个最终位置，并返回最终的hole，以hole将原序列分为两个子序列递归继续排序。结束条件依然为当begin大于或等于end时结束递归。
3.前后指针快排：
创建两个变量prev和cur，prev初始值为left，cur初始值为left+1，当cur小于right时则循环。cur的作用是再原序列中找出比基准值小的值然后与prev进行交换，cur的作用就是在原序列中探路，prev与cur之间就是比基准值大的值，循环交换prev和cur的值会将他们两个下标之间比基准值大的值翻滚式的向后移动，最终当cur大于right时，prev所处的位置则是基准值的最终位置，prev的下标将序列分为两个子序列，如此递归完成每一轮排序。
思路：
利用栈先进后出的原则，将原序列区间压入栈中，先将end压入再将begin压入栈中。当栈不为空时，先将栈顶元素赋值给left，然后弹出栈顶元素，再将此时的栈顶元素赋值给right，然后再弹出栈顶元素。执行一轮快排找出当前区间基准值的最终位置，将原序列分为两个子序列，当两个子序列的区间满足条件时则压入栈中继续循环找出子序列区间基准值的最终位置。
代码：（栈相关实现函数在前面的栈的实现总结中）
1.快速排序整体的综合性能和使用场景都是比较好的
2.时间复杂度为O(N*logN)
3.空间复杂度为O(logN)
4.稳定性：不稳定性
基本思想：
采用了分治法，将原序列的子序列通过比较两个序列的元素大小一一尾插，再将其拷贝回到允许列中。即先使子序列有序，再将每个子序列之间有序，最终将两个有序的子序列合成原序列。
递归实现归并排序：
递归实现归并思想：
需要传入原序列，begin，end（原序列区间），拷贝序列。先判断当前区间是否可以递归，当begin不等于end时则可以递归。先找出中间下标，将原序列拆分成两个子序列，并将两个子序列的区间作为递归的参数传入。当原序列经过递归拆分到最小区间时，也就是一组两个元素，对这两个元素继续创建两个区间并对这两个元素比较大小尾插至拷贝序列中，当有其中一组序列结束时，则跳出两个元素直接比较大小的循环，找出未结束的子序列尾插至拷贝序列中，再将拷贝序列拷贝回到原序列的该层递归的区间中。至此完成最深层次的递归函数的归并，返回上一层循环如此。
非递归实现归并排序：
非递归实现归并排序思路：
创建变量gap=1，gap代表此时归并数据一组中含有的元素个数，gap赋值为1是因为根据递归方式实现归并，是先从最深层次完成第一轮归并，逐层向上。当gap小于原序列元素个数时则进入循环，再创建一个循环，该循环的作用是将原序列拆分为每组含有gap个元素的子序列，并对第1组和第2组，第3组和第4组进行归并。（如下图过程）
并创建归并两组，每组的区间并对两个区间之间的元素按顺序进行比较尾插到拷贝数组中。
注意
1.这种方法可能会出现两组区间越界的问题，需要规避一些情况，当end1大于等于原序列元素个数（n）的情况或者begin2大于n的情况下无法实现两组归并则直接跳出循环，若是直接跳出循环则需要归并完一组拷贝一组数据。
2.当end2大于等于n时，需要将end2修正，end2=n-1。只需要归并到n-1的位置即可。同时也是需要归并完一组拷贝一组。
归并排序特性总结：
1.归并的缺点在于需要O(N)的空间复杂度，归并排序的思考更多的是解决再磁盘中的外排问题。
2.时间复杂度：O(N*logN)
3.空间复杂度：O(N)
4.稳定性：稳定
思路：
1.创建数组统计每个数据出现的次数，将数组的下标作为数据的值，在数组中该下标的值为该数据出现的次数
2.根据统计次数排序
代码：
代码思路：
创建两个变量记录原序列最大和最小值，创建新序列的大小为max-min+1，将新序列初始化。遍历原数组数据减去最小值则是该值对应新序列下标的相对映射，最后再将新序列的值和下标按顺序一一赋值到原序列中。
时间复杂度：O(N+range)
空间复杂度：O(range)
缺陷：
1.依赖数据范围，适用于范围集中的数组。
2.只能用于整形。
当出现重复数据较多时可以利用此方法
思路：
将等于key的值移动到中间，小于key的值放至左边，大于key的值放至右边。
代码思路：
创建新变量cur，用于遍历数组并判断当前位置的值与key比较。当cur小于等于right时进入循环，有三种情况：1.a[cur]小于key值，交换a[left]和a[cur]，left++，cur++,left可以加1是因为left是一定指向key值的；2.当a[cur]大于key值，交换a[right]和a[cur]，right--，此时的cur不加1是因为不确定交换过来的a[right]是否小于key；3.当a[cur]等于key值时则cur加1。此处代码大致是将hoare版本的快排思想和快慢指针的快排思想结合，将key值翻滚式的往中间挪动。