顿搜
飞过闲红千叶，夕岸在哪
类目归类
排序——算法设计 · 篇三
08/12
一、冒泡排序
GitHub地址：冒泡排序.cpp
略
二、插入排序
GitHub地址：插入排序.cpp
思想：在一个已经排序好的序列中，为下一个元素找合适的插入位置
1、从第二个元素开始进行插入排序，依次遍历后面的元素
2、对于当前元素，向前遍历，并将大于当前值的元素后移，直到找到一个小于当前值的元素
3、将当前值插入到该值的后面，然后继续下一次遍历
## 三、快速排序 > GitHub地址：快速排序.cpp > 1、确定一个基准点，将其值作为比较的对象key > 2、使用双指针，一个记录上次交换的位置，即后指针，初始化为-1，交换之前自增。 > 3、另一个记录当前遍历到的元素，即前指针，初始化为0。 > 4、每每遇到大于key的元素，前指针右移；遇到小与key的元素，与后指针交换当前值。 > 5、最后将基准点放到前指针下一个位置。 > 6、递归刚才的过程即可 另一种方法是从两端交替往中间扫描，最后将基准点放到中间位置。 ## 四、归并排序 > GitHub地址：归并排序.cpp 略 ## 五、原地归并排序 > GitHub地址：原地归并排序.cpp + ①、将同一个数组中两段有序序列合并为一个，可以使用插入的排序方式（但不优雅） > 1、对后半部分的每一个元素，都在前半部分找到合适的位置 ，然后插入（类似于插入排序） + ②、不使用额外的空间将两段有序序列进行合并 有两段有序空间分别为A B，从A中找第一个大于B[0]的元素并记录为A[i]，从B中找第一个大于A[i]的元素并记录为B[j]，将B[0]到B[j]中进行右移，然后就变得有序 > 1、从前面的有序序列中找到一个元素，其大于后序有序序列中的第一个元素 > 2、从后面有序子序列中找到一个元素，其大于前面有序序列的第i个元素 > 3、记原来两个序列的分界点为mid，以它为旋转中心，右旋转 > 4、更新前面子序列中未排序元素的位置（ j-mid）
