package insert_sort;import java.util.Random;/*各类插入排序* ——数据存储范围1~s.length-1——-*主要包括*直接插入排序*折半插入排序*希尔排序*以下为代码实现,其中折半查找函数是为了供折半插入排序使用*/public class Sort {/** 折半查找*/private static int binarySerach(int s[], int t, int left, int right) {int mid = 0;while (left <= right) {mid = (left + right) / 2;if (t > s[mid])left = mid + 1;if (t < s[mid])right = mid – 1;if (t == s[mid])left = mid + 1;}return left;}/** 直接插入排序 稳定*/private static void insertSort(int s[]) { // 1~s.length-1int i, j;for (i = 2; i < s.length; i++) {int temp = s[i];for (j = i – 1; j > 0 && s[j] > temp; j–)s[j + 1] = s[j];s[j + 1] = temp;}}/** 折半插入排序 稳定*/private static void binaryInsertSort(int s[]) { // 1~s.length-1int i, j, flag;for (i = 2; i < s.length; i++) {int temp = s[i];if (temp < s[i – 1]) { // 发现逆序,去有序队列进行折半查找,直到找到插入的位置flag = binarySerach(s, temp, 1, i – 1);for (j = i – 1; j >= flag; j–) {s[j + 1] = s[j];}s[flag] = temp;}}}/** 希尔排序 不稳定*/private static void shellSort(int s[], int dk) {int i, j, temp;for (i = dk + 1; i < s.length; i++) {temp = s[i];for (j = i – dk; j > 0 && s[j] > temp; j = j – dk) {s[j + dk] = s[j];}s[j + dk] = temp;}}public static void main(String[] args) {int length = 10;int[] s = new int[length];for (int i = 1; i < s.length; i++)s[i] = new Random().nextInt(40);// binaryInsertSort(s);// insertSort(s);shellSort(s, 1);for (int i = 1; i < s.length; i++)System.out.println(s[i]);}}
版权声明：本文为博主原创文章，未经博主允许不得转载。
，有人要进来，有一些人不得不离开。
