冒泡排序3.1

基本思想所谓交换就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置。

交换排序的特点是将键值较大的记录向序列的尾部移动键值较小的记录向序列的前部移动。

冒泡排序

冒泡排序是一种非常容易理解的排序时间复杂度O(N^2)空间复杂度O(1)稳定性稳定

3.1

}同样的方法先实现单趟排序如果前一个大于后一个就交换把最大的放在了最后。

得注意把控区间的位置如果if中的代码是a[i1]a[i],那么上面循环的区间就是从0到n-1。

来看看使用结果

如果说没有给定的数据已经排好序了就不用经行交换了就加一个标志bool

exchange

快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法。

其基本思想为任取待排序元素序列中的某元素作为基准值按照该排序码将待排序集合分割成两子序列左子序列中所有元素均小于基准值右子序列中所有元素均大于基准值然后最左右子序列重复该过程直到所有元素都排列在相应位置上为止。

4.1

然后右边边开始走可以发现当右边找到第一个比key小的值就停下来。

然后走左边左边找到第一个比key大的值然后左右两边交换交换完又继续。

R遇到LR没有找到比key小的值就一直走直到遇见L相遇位置是L比key小。

L遇到RR先走找到小于key的值就停下,L找大一直找没有找到但是遇见R就停下来相遇位置就是R找到小的位置也比key要小。

4.1.1

但是走到结尾会发生错误可能会错位出现rightleft的情况所以在循环里面多加一个判断。

left

right)来走当走完后交换key和left。

任何继续排下一个数。

这里的keyi将区间分为三部分[begin,keyi-1],keyi,[keyi1,end]。

用递归实现当这个区间只有一个值或者没有值时候结束。

否则就调用左区间和右区间。

实现结果

然后右边先走找到比key要小的值然后就把这个值取出来放到这个坑中。

4.2.1

挖坑法没有hoare版的复杂先找到右边找到小放在坑里左边找到大的放坑里在相遇时候把key放进去就行。

举个例子实现一下

cur遇到比key小的值就prev,交换prev和cur位置的值

cur先走

当cur比key的值小时就继续走否则就prev然后prev与cur交换。

举个例子看看