- 插入排序
- 希尔排序
排序原理
- 把所有的元素分为两组,已经排序的和未排序的
- 找到未排序的组中的第一个元素,向已经排序的组中进行插入
- 倒叙遍历已经排序的元素,依次和待插入的元素进行比较,直到找到一个元素小于等于待插入元素,那么就把待插入元素放到这个位置,其他的元素向后移动一位
public class Insertion { public static void sort(Comparable[] a) { for (int i = 1 ; i < a.length ; i++) { for (int j = i; j > 0; j--) { if (greater(a[j-1],a[j])) { exch(a,j-1,j); }else {break;} } } } private static boolean greater(Comparable v, Comparable w) { return v.compareTo(w) > 0; } private static void exch(Comparable[] a, int i, int j) { Comparable temp; temp = a[i]; a[i] = a[j]; a[j] = temp; } public static void main(String[] args) { Integer[] a = {5,4,6,3,1,2,1}; sort(a); System.out.println(Arrays.asList(a)); } }希尔排序
排序原理:
- 选定一个增长量h,按照增长量h作为数据分组的依据,对数组进行分组
- 对分好的每一组数据完成插入排序
- 减少增长量,最小减为1,重复第二步操作
增长量h的确定:增长量h的值 固定的规则,采用一下:
int h = 1; while(h < 数组长度/2){ h = 2*h+1; } // 循环结束后我们就可以确定h的最大值 // h的减小规则为 h = h/2
//Shell类 public class Shell { //对数据a中的元素进行排序 public static void sort(Comparable[] a) { //1.根据数组a的长度,确定增长量h的初始值; int h = 1; while (h < a.length / 2) { h = 2 * h + 1; } //2.希尔排序 while (h >= 1) { //排序 //找到待插入的元素 for (int i = h; i < a.length; i++) { //把待插入的元素插入到有序数列中 for (int j = i; j >= h; j -= h) { //待插入的元素是a[j],比较a[j]和a[j-h] if (greater(a[j - h], a[j])) { //交换元素 exchange(a, j - h, j); } else { //待插入元素已经找到了合适的位置,结束循环 break; } } } //减小h的值 h = h / 2; } } //比较v元素是否大于w元素 private static boolean greater(Comparable v, Comparable w) { return v.compareTo(w) > 0; } //数组元素i和j交换位置 private static void exchange(Comparable[] a, int i, int j) { Comparable temp; temp = a[i]; a[i] = a[j]; a[j] = temp; } public static void main(String[] args) { Integer[] a = {5,4,6,3,1,2,1}; sort(a); System.out.println(Arrays.asList(a)); } }