|
2.3 代码实现
- /**
- * 选择排序
- * @param array
- * @return
- */
- public static int[] selectionSort(int[] array) {
- if (array.length == 0)
- return array;
- for (int i = 0; i < array.length; i++) {
- int minIndex = i;
- for (int j = i; j < array.length; j++) {
- if (array[j] < array[minIndex]) //找到最小的数
- minIndex = j; //将最小数的索引生涯
- }
- int temp = array[minIndex];
- array[minIndex] = array[i];
- array[i] = temp;
- }
- return array;
- }
2.4 算法说明
最佳环境：T(n) = O(n2) 最差环境：T(n) = O(n2) 均匀环境：T(n) = O(n2)
3、插入排序(Insertion Sort)
插入排序(Insertion-Sort)的算法描写是一种简朴直观的排序算法。它的事变道理是通过构建有序序列，对付未排序数据，在已排序序列中从后向前扫描，找到响应位置并插入。插入排序在实现上，凡是回收in-place排序(即只需用到O(1)的特殊空间的排序)，因而在从后向前扫描进程中，必要重复把已排序元素慢慢向后挪位，为最新元素提供插入空间。插入排序：直接插入排序
3.1 算法描写
- 一样平常来说，插入排序都回收in-place在数组上实现。详细算法描写如下：
- 从第一个元素开始，该元素可以以为已经被排序;
- 取出下一个元素，在已经排序的元素序列中从后向前扫描;
- 假如该元素(已排序)大于新元素，将该元素移到下一位置;
- 一再步调3，直到找到已排序的元素小于可能便是新元素的位置;
- 将新元素插入到该位置后;
- 一再步调2~5。
3.2 动图演示
3.2 代码实现
- /**
- * 插入排序
- * @param array
- * @return
- */
- public static int[] insertionSort(int[] array) {
- if (array.length == 0)
- return array;
- int current;
- for (int i = 0; i < array.length - 1; i++) {
- current = array[i + 1];
- int preIndex = i;
- while (preIndex >= 0 && current < array[preIndex]) {
- array[preIndex + 1] = array[preIndex];
- preIndex--;
- }
- array[preIndex + 1] = current;
- }
- return array;
- }
3.4 算法说明
最佳环境：T(n) = O(n) 最坏环境：T(n) = O(n2) 均匀环境：T(n) = O(n2)
4、希尔排序(Shell Sort)
希尔排序是希尔(Donald Shell)于1959年提出的一种排序算法。希尔排序也是一种插入排序，它是简朴插入排序颠末改造之后的一个更高效的版本，也称为缩小增量排序，同时该算法是突破O(n2)的第一批算法之一。它与插入排序的差异之处在于，它会优先较量间隔较远的元素。希尔排序又叫缩小增量排序。希尔排序：希尔排序
希尔排序是把记录按下表的必然增量分组，对每组行使直接插入排序算法排序;跟着增量逐渐镌汰，每组包括的要害词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。
4.1 算法描写
我们来看下希尔排序的根基步调，在此我们选择增量gap=length/2，缩小增量继承以gap = gap/2的方法，这种增量选择我们可以用一个序列来暗示，{n/2,(n/2)/2…1}，称为增量序列。希尔排序的增量序列的选择与证明是个数学困难，我们选择的这个增量序列是较量常用的，也是希尔提议的增量，称为希尔增量，但其拭魅这个增量序列不是最优的。此处我们做示例行使希尔增量。
先将整个待排序的记录序列支解成为多少子序列别离举办直接插入排序，详细算法描写：
- 选择一个增量序列t1，t2，…，tk，个中ti>tj，tk=1;
- 按增量序列个数k，对序罗列办k 趟排序;
- 每趟排序，按照对应的增量ti，将待排序列支解成多少长度为m 的子序列，别离对各子表举办直接插入排序。仅增量因子为1 时，整个序列作为一个表来处理赏罚，表长度即为整个序列的长度。
4.2 进程演示
 （编辑：河北网）
【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!
|
