A股上市公司传智教育(股票代码 003032)旗下技术交流社区北京昌平校区

 找回密码
 加入黑马

QQ登录

只需一步,快速开始

© 一直很安静 中级黑马   /  2013-11-22 15:29  /  1387 人查看  /  3 人回复  /   0 人收藏 转载请遵从CC协议 禁止商业使用本文

本帖最后由 一直很安静 于 2013-11-22 16:44 编辑

什么是希尔排序?归并排序?最好举个例子说明。在网上查了下还是不太理解

3 个回复

倒序浏览
/*
* 希尔排序:先取一个小于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;

  3. public class SortTest {

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

  7. ShellSort.sort(arr);

  8. System.out.println("排序后:" + Arrays.toString(arr));
  9. }

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

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

  3. public class SortTest {

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

  7. MergeSort.sort(arr);

  8. System.out.println("排序后:" + Arrays.toString(arr));
  9. }

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

  24. private static void mergeSort(int[] data, int[] temp, int l, int r) {
  25. int mid = (l + r) / 2;
  26. if (l == r)
  27. return;
  28. mergeSort(data, temp, l, mid);
  29. mergeSort(data, temp, mid + 1, r);

  30. for (int i = l; i <= r; i++) {
  31. temp[i] = data[i];
  32. }
  33. int i1 = l;
  34. int i2 = mid + 1;
  35. for (int cur = l; cur <= r; cur++) {
  36. if (i1 == mid + 1)
  37. data[cur] = temp[i2++];
  38. else if (i2 > r)
  39. data[cur] = temp[i1++];
  40. else if (temp[i1] < temp[i2])
  41. data[cur] = temp[i1++];
  42. else

  43. data[cur] = temp[i2++];
  44. }
  45. }
  46. }
复制代码

评分

参与人数 1技术分 +1 收起 理由
田磊阳 + 1

查看全部评分

回复 使用道具 举报
一直很安静 来自手机 中级黑马 2013-11-22 16:44:26
藤椅
简★零度 发表于 2013-11-22 16:27
/*
* 希尔排序:先取一个小于n的整数d1作为第一个增量,把文件的全部记录分成(n除以d1)个组。所有距离为 ...

谢谢啦 我再研究研究
回复 使用道具 举报
您需要登录后才可以回帖 登录 | 加入黑马