尔排序

直接插入排序是一种简单的插入排序法其基本思想是把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中直到所有的记录插入完为止得到一个新的有序序列。

下面进行动图演示

a[end];end--;}else{break;}}a[end

tmp;}

改进插入排序效率的重点减少比较的次数如何减少比较的次数2的方向

折半查找

R[0…i-1]是采用顺序比较的方法。

由于有序区的元素是有序的,可以采用折半查找方法先在R0…i-1中找到插入位置,再通过移动元素进行插入,这样的插入排序称为折半插入排序(binary

insertion

折半插入排序的元素移动次数与直接插入排序相同,不同的仅是变分散移动为集中移动。

在R0…i-1中查找插入R[]的位置,折半查找的平均关键字比较次数约为log(i1)-1,平均移动元素的次数为i/22,所以平均时间复杂度为:

实际上,折半插入排序和直接插入排序相比移动元素的性能没有改善,仅仅减少了关键字的比较次数。

就平均性能而言,由于折半查找优于顺序查找,所以折半插入排序也优于直接插入排序。

折半插入排序的空间复杂度为(1),也是一种稳定的排序方法。

1.3

希尔排序法又称缩小增量法。

希尔排序法的基本思想是先选定一个整数gap把待排序文件中所有数据分成gap个组所有距离为gap的数据分在同一组内并对每一组内的数据进行排序。

然后取

gap

gap/2重复上述分组和排序的工作。

当到达gap1时数据将排好序.

算法实现

希尔排序法是一种不稳定的排序算法。

例如,若希尔排序分为{3,10,7,8,20}和(5,8,2,1,6)两组,显然第1组的8排列在第2组的8的后面,两组采用直接插入排序后的结果为(3,7,8,10,20}和{1,2,5,6,8),这样第1组的8排列到第2组的8的前面,它们的相对位置发生了改变。

二、选择排序

与lr下标对应的元素交换std::swap(a[Min_i],

Max_i){Max_i

显然,无论初始数据序列的状态如何,在第i趟排序中选出最小关键字的元素,内for循环需做n-1-(i1)1-n-i-1次比较,因此总的比较次数为:

另外,简单选择排序算法是一个不稳定的排序方法。

例如排序序列为(5,3,2,5,4,1,8,7),第1趟排序时选择出最小关键字1,将其与第1个位置上的元素交换,得到(1,3,2,5,4,5,8,7},从中看到两个5的相对位置发生了改变。

2.2

k;)看成是一棵完全二叉树的顺序存储结构,利用完全二叉树中双亲结点和孩子结点之间的位置关系在无序区中选择关键字最大(或最小)的元素。

算法实现

a[fa***r]){std::swap(a[Maxchild],

a[fa***r]);fa***r

综上所述,堆排序的最坏时间复杂度为O(nlogn)。

堆排序的平均性能分析较难,但实验研究表明,它较接近最坏性能。

实际上,堆排序和简单选择排序算法一样,其时间性能与初始序列的顺序无关,也就是说,堆排序算法的最好、最坏和平均时间复杂度都是O(nlogn)。

由于建初始堆所需的比较次数较多,所以堆排序不适合元素数较少的排序表堆排序只使用i、i、tmp等辅助变量,其辅助空间复杂度为(1)。

另外,在进行筛选时可能把后面相同关键字的元素调整到前面,所以堆排序算法是一种不稳定的排序方法。

三、交换排序

sort)也称为气泡排序,是一种典型的交换排序方法,其基本思想是通过无序区中相邻元素关键字间的比较和位置的交换使关键字最小/最大的元素如气泡一般逐渐往上“漂浮”直至“水面”

算法实现

冒泡排序算法辅助空间复杂度为O(1),也就是说它是一个就地排序。

另外,当ii日R[i].keyR[i].key时,两者没有逆序,不会发生交换,也就是说使R[i]和R[i]的相对位置保持不变,所以冒泡排序是一种稳定的排序方法。

3.2

快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法其基本思想任取待排序元素序列中的某元素作为基准值按照该排序码将待排序集合分割成两子序列左子序列中所有元素均小于基准值右子序列中所有元素均大于基准值然后最左右子序列重复该过程直到所有元素都排列在相应位置上为止。

算法实现

上面是Hoare大佬的原版思路但有些人认为Hoare的方法有很多小坑于是又有许多人提出了快速排序的其他实现思路如挖坑法前后指针法下面我们一一道来

挖坑法

a[cur]);}cur;}std::swap(a[keyi],

a[prev]);keyi

j){st.push(j);st.push(begin);}}

}四、归并排序

基本思想归并排序MERGE-SORT是建立在归并操作上的一种有效的排序算法,该算法是采用分治法Divide

andConquer的一个非常典型的应用。

将已有序的子序列合并得到完全有序的序列即先使每个子序列有序再使子序列段间有序。

若将两个有序表合并成一个有序表称为二路归并。

形象来讲就是将数组拆成一个个元素再逐渐将它们组合起来。

这符合递归的特性下面我们通过递归展开图来看。

递归展开图虽然看起来像把数组里的元素拆成了一个个新数组但我们必须要清晰的认识到这些元素还是在原数组里。

明白了这点让我们来好好思考一下如何归并。

有人说交换一下就行了。

比如上面最下面一层10

6归并回去的时候大的和小的交换一下位置不就有序了。

但倒数第二层呢?4个数互相交换吗这就有点复杂化了。

比较好的做法是创建一个临时数组tmp将需要归并的元素通过直接插入排序插入到临时数组里面,再把临时数组拷贝回去。

如下图

算法实现

sort顾名思义它是透过键值的部份资讯将要排序的元素分配至某些“桶”中藉以达到排序的作用基数排序法是属于稳定性的排序其时间复杂度为O

(nlog®m)其中r为所采取的基数而m为堆数在某些时候基数排序法的效率高于其它的稳定性排序法。

二种方式

first)法简称MSD法先按k1排序分组同一组中记录关键码k1相等再对各组按k2排序分成子组之后对后面的关键码继续这样的排序分组直到按最次位关键码kd对各子组排序后。

再将各组连接起来便得到一个有序序列。

最低位优先(Least

first)法简称LSD法先从kd开始排序再对kd-1进行排序依次重复直到对k1排序后便得到一个有序序列。

算法实现

计数排序是一种非比较排序其核心是将序列中的元素作为键存储在额外的数组空间中而该元素的个数作为值存储在数组空间中通过遍历该数组排序。

算法实现

排序方法时间复杂度空间复杂度稳定性平均情况最坏情况最好情况直接插入排序O(

n^2