黑马程序员技术交流社区

标题: 希尔排序和归并排序 [打印本页]
作者: 一直很安静    时间: 2013-11-22 15:29
标题: 希尔排序和归并排序
本帖最后由 一直很安静 于 2013-11-22 16:44 编辑

什么是希尔排序？归并排序？最好举个例子说明。在网上查了下还是不太理解
作者: 简★零度    时间: 2013-11-22 16:27
/*
* 希尔排序：先取一个小于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
*/希尔排序代码
  1. package cn.itcase;
  2. import java.util.Arrays;

  4. public class SortTest {

  6. public static void main(String[] args) {
  7. int[] arr = { 2, 5, 3, 1, 4 };
  8. System.out.println("排序前：" + Arrays.toString(arr));

  10. ShellSort.sort(arr);

  12. System.out.println("排序后：" + Arrays.toString(arr));
  13. }

  15. /*
  16. * 交换数组中的两个元素
  17. */
  18. public static void swap(int[] data, int i, int j) {
  19. int temp = data[i];
  20. data[i] = data[j];
  21. data[j] = temp;
  22. }
  23. }
  24. class ShellSort {
  25. public static void sort(int[] data) {
  26. for (int i = data.length / 2; i > 2; i /= 2) {
  27. for (int j = 0; j < i; j++) {
  28. insertSort(data, j, i);
  29. }
  30. }
  31. insertSort(data, 0, 1);
  32. }

  34. /**
  35. * @param data
  36. * @param j
  37. * @param i
  38. */
  39. private static void insertSort(int[] data, int start, int inc) {
  40. for (int i = start + inc; i < data.length; i += inc) {
  41. for (int j = i; (j >= inc) && (data[j] < data[j - inc]); j -= inc) {
  42. SortTest.swap(data, j, j - inc);
  43. }
  44. }
  45. }
  46. }
复制代码
归并
  1. package cn.itcase;
  2. import java.util.Arrays;

  4. public class SortTest {

  6. public static void main(String[] args) {
  7. int[] arr = { 2, 5, 3, 1, 4 };
  8. System.out.println("排序前：" + Arrays.toString(arr));

  10. MergeSort.sort(arr);

  12. System.out.println("排序后：" + Arrays.toString(arr));
  13. }

  15. /*
  16. * 交换数组中的两个元素
  17. */
  18. public static void swap(int[] data, int i, int j) {
  19. int temp = data[i];
  20. data[i] = data[j];
  21. data[j] = temp;
  22. }
  23. }
  24. class MergeSort {
  25. public static void sort(int[] data) {
  26. int[] temp = new int[data.length];
  27. mergeSort(data, temp, 0, data.length - 1);
  28. }

  30. private static void mergeSort(int[] data, int[] temp, int l, int r) {
  31. int mid = (l + r) / 2;
  32. if (l == r)
  33. return;
  34. mergeSort(data, temp, l, mid);
  35. mergeSort(data, temp, mid + 1, r);

  37. for (int i = l; i <= r; i++) {
  38. temp[i] = data[i];
  39. }
  40. int i1 = l;
  41. int i2 = mid + 1;
  42. for (int cur = l; cur <= r; cur++) {
  43. if (i1 == mid + 1)
  44. data[cur] = temp[i2++];
  45. else if (i2 > r)
  46. data[cur] = temp[i1++];
  47. else if (temp[i1] < temp[i2])
  48. data[cur] = temp[i1++];
  49. else

  51. data[cur] = temp[i2++];
  52. }
  53. }
  54. }
复制代码
作者: 一直很安静    时间: 2013-11-22 16:44
简★零度 发表于 2013-11-22 16:27
/*
* 希尔排序：先取一个小于n的整数d1作为第一个增量，把文件的全部记录分成（n除以d1）个组。所有距离为 ...

谢谢啦 我再研究研究



欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/) 黑马程序员IT技术论坛 X3.2