黑马程序员技术交流社区

标题: 常用排序方法（多种）你会几个? [打印本页]
作者: 穿靴子的猫    时间: 2013-8-23 23:47
标题: 常用排序方法（多种）你会几个?
本帖最后由 穿靴子的猫 于 2013-8-24 11:02 编辑
  1. <div class="blockcode"><blockquote>// 1.耳熟能详的冒泡排序
  2.                 int[] arr = { 10, 23, 11, 56, 45, 26, 59, 28, 84, 79 }; // 给出原始数组序列
  3.                 int temp;
  4.                 System.out.println("初始序列的数组为：");// 输出在数组中数字的顺序
  5.                 for (int a : arr) {
  6.                         System.out.print(a + " ");
  7.                 }
  8.                 System.out.println();
  9.                 for (int i = 0; i < arr.length - 1; i++) {
  10.                         for (int j = 0; j < arr.length - i - 1; j++) {
  11.                                 if (arr[j] > arr[j + 1]) {
  12.                                         temp = arr[j];
  13.                                         arr[j] = arr[j + 1];
  14.                                         arr[j + 1] = temp;
  15.                                 }
  16.                         }
  17.                 }
  18.                 System.out.println("排好序的数组：");// 输出排好序的数组
  19.                 for (int a : arr) {
  20.                         System.out.print(a + " ");
  21.                 }
复制代码
冒泡排序已经修改了
  1. // 2.选择排序法
  2.         public static void main(String[] args) {
  3.                 int[] arr = { 10, 23, 11, 56, 45, 26, 59, 28, 84, 79 };
  4.                 int index, temp;
  5.                 System.out.println("初始数组为:");
  6.                 for (int a : arr) { // 对n个记录进行n-1趟的选择排序
  7.                         System.out.print(a+" ");
  8.                 }
  9.                 for(int i = 0; i < arr.length-1; i++) {
  10.                         index=i;  //初始化第i趟选择排序的最小记录的指针
  11.                         for (int j = i+1; j <arr.length; j++) { //在无序区选取最小记录
  12.                                 if(arr[j]<arr[index]){
  13.                                         index=j;
  14.                                 }
  15.                         }
  16.                                                         //
  17.                          if (index!=i){ //讲最小记录于arr交换
  18.                                 temp=arr[i];
  19.                                 arr[i]=arr[index];
  20.                                                         
  21.                                 arr[index]=temp;
  22.                          }
  23.                 }
  24.                 System.out.println();
  25.                                                         
  26.                 System.out.println("排序后数组为:");
  27.                 for(int a : arr){
  28.                                                         
  29.                         System.out.print(a+" ");
  30.                 }
  31.         }
  32.                
  33. }
复制代码
  1. // 3.插入排序法
  2.         public static void main(String[] args) {
  3.                 int[] arr = { 10, 23, 11, 56, 45, 26, 59, 28, 84, 79 }; // 给出原始数的序列
  4.                 int i, j, temp; // 定义变量名称
  5.                 System.out.println("初始数组为:"); // 输出初始序列
  6.                 for (int a : arr) {
  7.                         System.out.print(a + " ");
  8.                 }
  9.                 for (i = 1; i < arr.length; i++) {
  10.                         temp = arr[i]; // 设置哨兵,暂存当前值
  11.                         for (j = i - 1; j >= 0 && temp < arr[j]; j--) { // 寻找插入位置
  12.                                 arr[j + 1] = arr[j];
  13.                         }
  14.                         arr[j + 1] = temp; // 大于当前值的,插在当前值后面
  15.                 }
  16.                 System.out.println();
  17.                 System.out.println("排序后数组为:"); // 输出新序列
  18.                 for (int a : arr) {
  19.                         System.out.print(a + " ");
  20.                 }
  21.         }
复制代码
  1. // 4.归并排序
  2.         private static void merge(int r[], int r1[], int s, int m, int t) {
  3.                 int i = s, j = m + 1, k = s;
  4.                 while (i <= m && j <= t) {
  5.                         if (r[i] <= r[j]) {
  6.                                 r1[k++] = r[i++];// 取r和r[j]中比较小者放如r1[k]
  7.                         } else {
  8.                                 r1[k++] = r[j++];
  9.                         }
  10.                 }
  11.                 if (i <= m) {
  12.                         while (i <= m) { // 若第一个子序列处理完,则进行收尾处理
  13.                                 r1[k++] = r[i++];
  14.                         }
  15.                 } else {
  16.                         while (j <= t) {// 若第二个子序列处理完,则进行收尾处理
  17.                                 r1[k++] = r[j++];
  18.                         }
  19.                 }
  20.         }

  22.         private static void mergePass(int r[], int r1[], int n, int h) {
  23.                 int i = 0;
  24.                 while (i <= n - 2 * h) {// 待归并记录至少有两个长度为h的子序列
  25.                         merge(r, r1, i, i + h - 1, i + 2 * h - 1);
  26.                         i += 2 * h;
  27.                 }
  28.                 if (i < n - h) {
  29.                         merge(r, r1, i, i + h - 1, n); // 待归并序列中有一个长度小于h
  30.                 } else {
  31.                         for (int k = i; k <= n; k++) {// 待归并序列中只剩一个子序列
  32.                                 r1[k] = r[k];
  33.                         }
  34.                 }
  35.         }

  37.         public static void mergeS(int r[], int r1[], int n) {
  38.                 int h = 1;
  39.                 while (h < n) {
  40.                         mergePass(r, r1, n - 1, h);
  41.                         h = 2 * h;
  42.                         mergePass(r1, r, n - 1, h);
  43.                         h = 2 * h;
  44.                 }
  45.         }

  47.         public static void main(String[] args) {
  48.                 int r[] = { 36, 45, 12, 56 };
  49.                 int r1[] = new int[4];
  50.                 System.out.println("原始数组为:");
  51.                 for (int i = 0; i < r.length; i++) {
  52.                         System.out.print(" " + r[i]);
  53.                 }
  54.                 mergeS(r, r1, r.length);
  55.                 System.out.println();
  56.                 System.out.println("新数组为:");
  57.                 for (int i = 0; i < r.length; i++) {
  58.                         System.out.print(" " + r[i]);
  59.                 }
  60.         }
复制代码
因上传过程中出现排版错误..所以如果有不对请提醒 第四个归并测试没问题
作者: 耶稣说wō乖    时间: 2013-8-24 08:51
冒泡排序错了。。



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