冒泡排序、插入排序、选择排序、快速排序、希尔排序和归并排序的算法实现

逃离我推掉我的手 2021-06-24 15:59 478阅读 0赞

1.冒泡排序(o(n^2))

冒泡排序基本思想：两两比较相邻记录的关键字，如果反序则交换位置，直到没有反序记录为止。

过程：遍历每个元素，每次与其后的元素比较，顺序错误就交换位置，重复进行直到不需要交换。这个算法名字的由来是因为越小的元素经由交换慢慢“浮”到数列的顶端。

代码实现如下：

2.插入排序(o(n^2))

插入排序基本思想：将一个记录插入到已排好序的有序表中，从而得到一个新的、记录数增1的有序表。

过程：第一个元素默认已排序，每次遍历下一元素，在已排序的元素序列中从后向前扫描每个元素并与之一一比较，如果遍历元素小于已排序元素，则将遍历元素插入到已排序元素的位置。

代码实现如下：

3.选择排序(o(n^2))

选择排序基本思想：是通过n-i次关键字间的比较，从n-i个记录中选出关键字最小的额记录，并和第i个记录交换位置。

过程：先在未排序序列中找到最小（大）元素，存放在已排序序列的起始位置；然后从剩余未排序元素中继续寻找最小（大）元素，然后放在已排序的末尾，直到所有元素排序完毕。

代码实现如下：

4.快速排序(o(nlog2(n)))

快速排序基本思想（过程）：

第一，在数据集之中选择一个元素作为基准；

第二，数组（除开基准值）里的每个元素与基准进行比较，所有小于基准的元素都放在左边的数组里；所有大于基准的元素都放在右边的数组里；

第三，对左边和右边的两个子集不断的重复第一步和第二步，直到所有子集只剩下一个元素为止；

第四，将所有子集拼接形成一个已排序的数组。

代码实现如下：

5.希尔排序(o(n^1.3))

希尔排序基本思想：它是第一个突破O(n^2)的排序算法，是简单插入排序的改进版。它与插入排序的不同之处在于，它会优先比较距离较远的元素。实质是分组插入排序，希尔排序又称缩小增量排序。

过程：把记录按步长（两元素间隔）gap分组，对每组记录采用直接插入排序方法进行排序；随着步长逐渐减小，每个分组包含的记录越来越多；当步长的值减小到1时，整个数据合成一组，构成一组有序记录，则完成排序。

代码实现如下：

6.归并排序(o(nlog2(n)))

归并排序的基本思想：该算法是采用分治法的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若有两个有序表合并成一个有序表，称为2-路归并。

过程：第一，把长度为n的输入序列分成两个长度为n/2的子序列；第二，对这两个子序列分别采用归并排序；第三，将两个排序好的子序列合并成一个最终的排序序列。

代码实现如下：

7. 二分查找算法（O(log2n)）

二分查找，也称为折半查找，是指在有序的数组里找出指定的值，返回该值在数组中的索引。查找步骤如下：  
（1）从有序数组的最中间元素开始查找，如果该元素正好是指定查找的值，则查找过程结束。否则进行下一步;  
（2）如果指定要查找的元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半区域查找，然后重复第一步的操作;  
（3）重复以上过程，直到找到目标元素的索引，查找成功;或者直到子数组为空，查找失败。

一、非递归实现：

二、递归实现：