黑马程序员技术交流社区

标题: 和大家分享数据结构里面的排序 [打印本页]

---

作者: 王章亚    时间: 2012-5-31 14:19
标题: 和大家分享数据结构里面的排序


/**
         * 实现数值冒泡排序
         * @param num 要排序的数组
         */
        public static void maoPaoPaiXu(int[] num){
               
                for(int i=0;i<num.length-1;i++){  
                        for(int j=0;j<num.length-i-1;j++){
                                if(num[j]>num[j+1]){
                                        int temp=num[j];
                                        num[j]=num[j+1];
                                        num[j+1]=temp;
                                }
                        }
                }
                for(int i=0;i<num.length;i++){
                        System.out.print(num+" ");
                }
        }
-------------------------------------------------------------------------------------------------------
/**
     * 选择排序
     * @param num 需要排序的数组
     */
    public static void selectionSort(int[]num){
        
        int k=0;
        for(int i=0;i<num.length-1;i++){
            k=i;
            for(int j=i;j<num.length;j++){
                if(num[j]<num[k]){
                    k=j;
                }
            }
                 int   temp=num;   
                 num=num[k];      
                  num[k]=temp;
           
           
        }
        for(int i=0;i<num.length;i++){
            System.out.print(num+" ");
        }
    }
-------------------------------------------------------------------------------------------------------
/**
         * 插入排序
         * @param args 需要排序的数组
         */
        public static void insertSort(int[] num){
                int temp;
                for(int i=1;i<num.length;i++){
                        temp=num;
                        int j=i;
                        while(j>0&&num[j]>=temp){
                                
                                num[j]=num[j-1];
                                j--;
                        }
                        num[j]=temp;
                }
                for(int i=0;i<num.length;i++){
                        System.out.print(num+" ");
                }
        }
-------------------------------------------------------------------------------------------
至于效率最高的希尔排序算法我还没有领悟，求深刻理解思想

---

作者: 黑马—陈磊    时间: 2012-5-31 14:42
基本思想：先取一个小于n的整数d1作为第一个增量，把文件的全部记录分成d1个组。所有距离为d1的倍数的记录放在同一个组中。先在各组内进行直接插入排序；然后，取第二个增量d2<d1重复上述的分组和排序，直至所取的增量dt=1(dt<dt-l<…<d2<d1)，即所有记录放在同一组中进行直接插入排序为止。实质上是一种分组插入方法。

---

作者: 刘伯阳    时间: 2012-5-31 15:05
嗯  不错  仔细研究了下 这些算法是解决逻辑问题的重中之重  你的代码中有几处小问题
/**
     * 选择排序
     * @param num 需要排序的数组
     */
    public static void selectionSort(int[]num){
            int temp;
            int k=0;
            int j=0;
            for(int i=0;i<num.length-1;i++){
                    k=i;
                    for(j=i;j<num.length;j++){
                            if(num[j]<num[k]){
                                    k=j;
                            }
                    }
                    temp=num[j];            //你的这里貌似写错了  、我没有具体测试 、只是感觉 、 还有下面插入排序的调换顺序貌似也错了。
                    num[j]=num[k];
                    num[k]=temp;
            }
            for(int i=0;i<num.length;i++){
                    System.out.print(num+" ");
            }
    }

/**
     * 插入排序
     * @param args 需要排序的数组
     */
    public static void insertSort(int[] num){
            int temp;
            for(int i=1;i<num.length;i++){
                    temp=num;
                    int j=i;
                    while(j>0&&num[j]>=temp){
                           
                            num[j]=num[j-1];
                            j--;
                    }
                    num[j]=temp;
            }
            for(int i=0;i<num.length;i++){
                    System.out.print(num+" ");
            }
    }

------------------------------------------------------------------------------------------------------------------------------------------------------
希尔排序
基本思想： 先取一个小于n的整数d1作为第一个增量，把文件的全部记录分成d1个组。
所有距离为dl的倍数的记录放在同一个组中。
先在各组内进行直接插人排序；然后，取第二个增量d2<d1重复上述的分组和排序，
直至所取的增量dt=1(dt<dt-l<…<d2<d1)，即所有记录放在同一组中进行直接插入排序为止。
该方法实质上是一种分组插入方法。

public class shellSort {
public static int[] a = {  3, 1, 6, 2, 9, 0, 7, 4, 5 ,8};
public static void main(String args[]) {
  int i; // 循环计数变量
  int Index = a.length;// 数据索引变量
  System.out.print("排序前: ");
  for (i = 0; i < Index ; i++)
   System.out.printf("%3s ", a);
  System.out.println("");
// ShellSort(Index); // 选择排序
  // 排序后结果
  System.out.print("排序后: ");
  for (i = 0; i < Index ; i++)
   System.out.printf("%3s ", a);
  System.out.println("");
  System.out.println("--------------------------------");
   shell_sort(a);
   for( i=0;i<a.length;i++)
    System.out.print(a+" ");
}
public static void ShellSort(int Index) {
  int i, j, k; // 循环计数变量
  int Temp; // 暂存变量
  boolean Change; // 数据是否改变
  int DataLength; // 分割集合的间隔长度
  int Pointer; // 进行处理的位置
  DataLength = (int) Index / 2; // 初始集合间隔长度
  while (DataLength != 0) // 数列仍可进行分割
  {
   // 对各个集合进行处理
   for (j = DataLength; j < Index; j++) {
    Change = false;
    Temp = a[j]; // 暂存Data[j]的值,待交换值时用
    Pointer = j - DataLength; // 计算进行处理  的位置
    // 进行集合内数值的比较与交换值
    while (Temp < a[Pointer] && Pointer >= 0 && Pointer <= Index) {
     a[Pointer + DataLength] = a[Pointer];
     // 计算下一个欲进行处理的位置
     Pointer = Pointer - DataLength;
     Change = true;
     if (Pointer < 0 || Pointer > Index)
      break;
    }
    // 与最后的数值交换
    a[Pointer + DataLength] = Temp;
    if (Change) {
     // 打印目前排序结果
     System.out.print("排序中: ");
     for (k = 0; k < Index; k++)
      System.out.printf("%3s ", a[k]);
     System.out.println("");
    }
   }
   DataLength = DataLength / 2; // 计算下次分割的间隔长度
  }
}
//简单一点的写法，，
public static void shell_sort(int a[])
{
  int i,j,h,temp;
  int n= a.length;
  h = n/2;
  while(h!=0)
  {
   for(i=h;i<n;i++)
   {
    temp = a;
    for(j=i-h;j>=0&& a[j]>temp;j=j-h)
    {
     a[j+h] = a[j];
    }
    a[j+h] = temp;
    System.out.print("排序过程：");
     for(int k=0;k<a.length;k++)
      System.out.print(" " + a[k]+" ");
     System.out.println();
   }
   h = (int)(h/2.0);
  }
}
}

---

作者: 王章亚    时间: 2012-5-31 18:06
我都是测试过了没错啊

---

作者: 刘伯阳    时间: 2012-5-31 18:13

王章亚 发表于 2012-5-31 18:06
我都是测试过了没错啊

int temp=num;   //这里num是个整形变量吗？
num=num[k];     //将num[k]的值赋给num数组是什么意思？
num[k]=temp;

---

作者: 王章亚    时间: 2012-5-31 18:30
真是见鬼的，我写的不是这样的啊！我写的是

int temp=num[i];
num[i]=num[k];
num[k]=temp;
怎么会发表上去就出现错误了呢？而我重新编辑以后，还是错误的，就是写不出来。见鬼啦

---

作者: 王章亚    时间: 2012-5-31 18:36

刘伯阳 发表于 2012-5-31 18:13
int temp=num;   //这里num是个整形变量吗？
num=num[k];     //将num[k]的值赋给num数组是什么意思？
nu ...

真是见鬼啦，我写的不是这样的！可是提交之后后面的都没有啦！我写的跟你说的是一样的

---

作者: 刘伯阳    时间: 2012-5-31 18:39

王章亚 发表于 2012-5-31 18:36
真是见鬼啦，我写的不是这样的！可是提交之后后面的都没有啦！我写的跟你说的是一样的 ...

哦  哈哈  我说呢~  可能是格式的事吧

---

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

黑马程序员IT技术论坛 X3.2