/*
* 希尔排序:先取一个小于n的整数d1作为第一个增量,把文件的全部记录分成(n除以d1)个组。所有距离为d1的倍数的记录放在同一个组中先在各组内进行直接插入排序;然后,取第二个增量d2<d1重复上述的分组和排序, 直至所取的增量dt=1(dt<dt-l<…<d2<d1),即所有记录放在同一组中进行直接插入排序为止。
*/
*归并操作(merge),也叫归并算法,指的是将两个已经排序的序列合并成一个序列的操作。 如设有数列{6,202,100,301,38,8,1}
* 初始状态: [6] [202] [100] [301] [38] [8] [1] 比较次数 i=1 [6 202 ] [ 100 301] [ 8 38] [ 1 ] 3 i=2 [ 6 100 202 301 ] [ 1 8 38 ] 4
* i=3 [ 1 6 8 38 100 202 301 ] 4
*/希尔排序代码- package cn.itcase;
- import java.util.Arrays;
- public class SortTest {
- public static void main(String[] args) {
- int[] arr = { 2, 5, 3, 1, 4 };
- System.out.println("排序前:" + Arrays.toString(arr));
- ShellSort.sort(arr);
- System.out.println("排序后:" + Arrays.toString(arr));
- }
- /*
- * 交换数组中的两个元素
- */
- public static void swap(int[] data, int i, int j) {
- int temp = data[i];
- data[i] = data[j];
- data[j] = temp;
- }
- }
- class ShellSort {
- public static void sort(int[] data) {
- for (int i = data.length / 2; i > 2; i /= 2) {
- for (int j = 0; j < i; j++) {
- insertSort(data, j, i);
- }
- }
- insertSort(data, 0, 1);
- }
- /**
- * @param data
- * @param j
- * @param i
- */
- private static void insertSort(int[] data, int start, int inc) {
- for (int i = start + inc; i < data.length; i += inc) {
- for (int j = i; (j >= inc) && (data[j] < data[j - inc]); j -= inc) {
- SortTest.swap(data, j, j - inc);
- }
- }
- }
- }
复制代码 归并- package cn.itcase;
- import java.util.Arrays;
- public class SortTest {
- public static void main(String[] args) {
- int[] arr = { 2, 5, 3, 1, 4 };
- System.out.println("排序前:" + Arrays.toString(arr));
- MergeSort.sort(arr);
- System.out.println("排序后:" + Arrays.toString(arr));
- }
- /*
- * 交换数组中的两个元素
- */
- public static void swap(int[] data, int i, int j) {
- int temp = data[i];
- data[i] = data[j];
- data[j] = temp;
- }
- }
- class MergeSort {
- public static void sort(int[] data) {
- int[] temp = new int[data.length];
- mergeSort(data, temp, 0, data.length - 1);
- }
- private static void mergeSort(int[] data, int[] temp, int l, int r) {
- int mid = (l + r) / 2;
- if (l == r)
- return;
- mergeSort(data, temp, l, mid);
- mergeSort(data, temp, mid + 1, r);
- for (int i = l; i <= r; i++) {
- temp[i] = data[i];
- }
- int i1 = l;
- int i2 = mid + 1;
- for (int cur = l; cur <= r; cur++) {
- if (i1 == mid + 1)
- data[cur] = temp[i2++];
- else if (i2 > r)
- data[cur] = temp[i1++];
- else if (temp[i1] < temp[i2])
- data[cur] = temp[i1++];
- else
- data[cur] = temp[i2++];
- }
- }
- }
复制代码 |