插入排序最优_排序专题插入排序

今天开始，我计划用几篇专题来集中练习下有关排序的算法，排序算法是算法中最基础的算法了，所以这部分我们是要尽可能的全都掌握了。排序算法最常见的有如下几种：

• 插入排序(Insertion Sort)

• 选择排序(Selection Sort)

• 希尔排序(Shell Sort)

• 冒泡排序(Bubble Sort)

• 快速排序(Quick Sort)

• 归并排序(Merge Sort)

• 堆排序(Heap Sort)

• 计数排序(Counting Sort)

• 桶排序(Bucket Sort)

• 基数排序(Radix Sort)

废话不多说了，开始今天的算法练习。

???今日练习(一)插入排序。

?思路

插入排序从左到右进行，每次都将当前元素插入到左侧已经排序的数组中，使得插入之后左部数组依然有序。第 j 元素是通过不断向左比较并交换来实现插入过程：当第 j 元素小于第 j - 1 元素，就将它们的位置交换，然后令 j 指针向左移动一个位置，不断进行以上操作。

private void sort(int[] nums){ int len =nums.length; if ( len< 2) { return nums; } for(int i=1;i for(int j=i;j>0;j--){ if(nums[j]< nums[j-1]){ int temp = nums[j]; nums[j]=nums[j-1]; nums[j-1]=temp; } } } return nums;}

---

???今日练习(二)希尔排序。?思路希尔排序也是一种插入排序，它是简单插入排序经过改进之后的一个更高效的版本，也称为缩小增量排序，同时该算法是冲破O(n2)的第一批算法之一。它与插入排序的不同之处在于，它会优先比较距离较远的元素。希尔排序又叫缩小增量排序。希尔排序是把数组按下标的一定增量间隙分组，对每组使用直接插入排序算法排序；随着增量间隙逐渐缩小，每组包含的元素越来越多，当增量间隙减至1时，整个文件恰被分成一组，算法便终止。在此我们选择增量gap=length/2，缩小增量继续以gap = gap/2的方式，这种增量选择我们可以用一个序列来表示，{n/2,(n/2)/2…1}，称为增量序列。希尔排序的增量序列的选择与证明是个数学难题，我们选择的这个增量序列是比较常用的，也是希尔建议的增量，称为希尔增量，但其实这个增量序列不是最优的。此处我们做示例使用希尔增量，如图：

看着上图，结合代码，大家最好能自己手写下数组中元素的变化过程这样理解的会更深刻，图中仅展示出了增量不同时最终的变化情况，中间过程并不能体现。

代码：public void shellSrot(int[] nums) { int len = nums.length; if (len < 2) { return; } int gap = len / 2; while (gap > 0) { for (int i = gap; i < len; i++) { int temp = nums[i]; int prevI = i - gap; while (prevI >= 0 && nums[prevI] > temp) { nums[prevI + gap] = nums[prevI]; prevI -= gap; } nums[prevI + gap] = temp; } gap = gap / 2; }}

---

???今日练习(三)选择排序。?思路

选择出数组中的最小元素，将它与数组的第一个元素交换位置。再从剩下的元素中选择出最小的元素，将它与数组的第二个元素交换位置。不断进行这样的操作，直到将整个数组排序。

public void selectSort(int[] nums){ int len=nums.length; if(len<2){ return; } for (int i=0;i<len-1;i++){ int min=i; for (int j=i+1;j<len;j++){ if(nums[j] min=j; } } int temp=nums[min]; nums[min]=nums[i]; nums[i]=temp; }}

---

不积跬步，无以至千里。

文章有帮助的话，点个转发、在看呗。

谢谢支持哟 (*^__^*)

END

?

总结

以上是生活随笔为你收集整理的插入排序最优_排序专题插入排序的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。