手工画图理解常见七种排序算法

本文主要是介绍手工画图理解常见七种排序算法，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

常见排序算法及介绍
一，直接插入排序
原理：
整个区间分为有序区间和无序区间，每次拿到无序区间的第一个数去有序区间里找对应的位置。

稳定性:稳定
空间复杂度：O(1)
平均时间复杂度：O(n的平方)
最优情况时间复杂度：O(n)
最坏情况下时间复杂度：O(n的平方)
注意：默认第一个数是有序的故从第二个数开始
代码实现 ：

 //直接插入排序public static void indexSort(int[] arr) {int tmp = arr[0];for(int i = 1;i < arr.length;i++) {tmp = arr[i];int j;for( j = i-1;j >= 0;j--) {if(arr[j] > tmp) {arr[j+1] = arr[j];}else {break;}}arr[j+1] = tmp;}}

对于直接插入排序当数据小的时候工作量不是很大，但是当数据多的时候直接插入就有点效率低了，因此在直接插入的基础上还可以改进在有序区间找的时候可以利用二分查找法
代码如下：

//直接插入排序下的折半查找public static void BsInsertSort(int[] arr) {for(int i = 1;i < arr.length;i++) {int ret = arr[i];int left = 0;int right = i;while(left < right) {int mid = (left + right)/2;if(arr[mid] <= ret) {left = mid+1;}else {right = mid;//考虑到当在边界时，故不能-1；}}for(int j = i;j >left;j--) {arr[j] = arr[j-1];}arr[left] = ret;}}

二，希尔排序
希尔排序法又称缩小增量法。希尔排序法的基本思想是：先选定一个整数，把待排序文件中所有记录分成个组，所有距离为gap的记录分在同一组内，并对每一组内的记录进行排序。然后，取，重复上述分组和排序的工作。当到达gap=1时，所有记录在统一组内排好序。
即选择好要排序的组数，从大到小进行

稳定性:不稳定
空间复杂度：O(1)
平均时间复杂度：O(n的1.3次方)
最优情况时间复杂度：O(n)
最坏情况下时间复杂度：O(n的平方)
原排序数字：

在下图中选择gap = 5 ，3 1
当gap = 5时：
第一次结果如下：
当取gap=3时，即分为三组
此时如图所示
交换后结果：
从此次结果可以看出，越小的越靠前，越有序，

接下来在整体进行直接插入排序 ，即可，
最终得到排序结果：
代码实现：

//希尔排序public static void shell(int[] arr,int gap

这篇关于手工画图理解常见七种排序算法的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---