尔排序

排序时间的复杂度和稳定性-CSDN博客关于七大排序的时间复杂度和稳定性的总结帮助读者迅速掌握各各排序的优劣在不同情况下如何选择。

https://blog.csdn.net/2401_87944878/article/details/145404375

排序包含两种

外部排序数据太多不能同时放在内存中根据排序的过程不能在内外存之间移动的排序。

外部排序要对文件进行操作。

排序包含有四大实现插入排序选择排序交换排序归并排序。

根据这四个实现又可以分支出一共7个排序思想简单插入排序希尔排序选择排序堆排序冒泡排序快速排序归并排序。

下面我们对这七种排序进行讲解。

插入排序

如图简单插入怕排序就是遍历原数组将每一个元素放在其指定位置。

先拿出一个元素向前找看比它大的先后移直到找到比它小的。

//简单插入排序

希尔排序实际上是对简单插入排序的一种优化。

简单插入排序每次与其相邻的元素进行比较而希尔排序是将一个数组分成多个组将每个组进行简单插入排序这样可以让大的数迅速到前面去小的数迅速到后面去。

可以看到第一次gap是5时将下标0和5比较1和6比较2和7比较....这样可以迅速将大的数移到前面去将小的数移到后面去这样就使的数组更加趋于有序的状态。

通过gap从大到小的变化使得当gap较小的时候可以快速向前找到它的位置更快的让每次循环break掉让效率更快。

//希尔排序

简单选择排序就是遍历原数组直接找到最大值或最小值将其放在尾和首可以一次只找出一个最值也可以将最大值和最小值同时找到。

以上是遍历未排序的数组每次找出最下的元素交换下面演示遍历未排序的数组每次找打最小和最大的元素。

//交换函数

a[min]);//注意此处如果left对应的值就是最大值的时候//将min和left交换后max就在min的位置了if

(left

堆排序就是利用二叉树的性质通过建大堆或小堆将最大的数据或最小的数据放在指定位置。

在二叉树中已经详细讲过堆了这里就直接贴代码。

二叉树C语言-CSDN博客文章浏览阅读1.3k次点赞19次收藏18次。

帮助读者快速掌握树这一数据结构了解堆的功能能够实现堆排序以及如何再大量数据中快速找到前K个最大元素如何处理普通二叉树普通二叉树的遍历等知识。

https://blog.csdn.net/2401_87944878/article/details/145262931https://blog.csdn.net/2401_87944878/article/details/145262931https://blog.csdn.net/2401_87944878/article/details/145262931https://blog.csdn.net/2401_87944878/article/details/145262931https://blog.csdn.net/2401_87944878/article/details/145262931https://blog.csdn.net/2401_87944878/article/details/145262931

//向下调整

快速排序是将一个元素key作为基准先找到这个key的准确位置将小于key的放在key的左边将大于key的放在右边。

如图将数组首元素作为key通过左右指针让R指针先走找到小于key的值停L指针再走大于key的时候停将L位置和R位置交换直到L和R相遇时停止这个位置就是key排序后的位置。

思考为什么要让R指针想走能否让L指针想走

关于key的选择有三种方法选择最左边的随机选择比较数组左右中间这三个值选出次小的值。

此处选择三数取中最好可以尽量避免只出现一个递归函数。

//快排Hoare版本

end)return;//快排就是将key放在正确位置上去。

//三数取中int

mid

挖坑法就是将keyi的位置值保留R指针找比key小的将其填在keyi的位置R指针处变为坑直到L指针和R指针相遇将其位置的key填入坑。

//快排挖坑法

分别利用两个指针一个向前面走如果cur对用的值比key小就交换两个指针都向前移动如果cur对应的值大就不交换cur向前移动。

//快排双指针法

a[pre]);cur;pre;}else{cur;}}Swap(a[keyi],

a[pre

快排的非递归就是利用栈将其begin和end的值储存起来再利用栈的“后入先出”的性质每一次拿出一个范围再放入子范围直到栈的空间为空时停止。

typedef

归并排序的实现就是先对小范围排序再对大范围排序。

如图相对两个元素进行排序再对4个元素进行排序依次依次*2向后排序。

//归并排序

归并的非递归实现就不能用栈来存储18首尾的范围了可以直接从2个元素排序开始依次*2直到排完为止。

void

关于快排当有大量重复的数据出现的时候快排的key的位置可能就是最左边导致向下递归后还是只有一组当大量出现这种情况的时候就会导致快排变成简单选择排序时间复杂度大大增加导致效率降低。

此处可以采用三路划分的快排解决。

三路划分与普通快排的区别普通快排将数组分成两个部分大于key和小于key的而三路划分将快排分成三个部分大于key小于key和等于key的。

分为左右两个指针以及一个遍历数组的指针将大于key的调到右边将小于key的调到左边将等于key的放在中间。

void

a[right]);right--;}elsecur;}keyi

left;TQuickSort(a,