登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

AP计算机众里寻他千百度,名师成就满分路

AP计算机

 
 
 

日志

 
 
关于我

大学讲师,中国首批AP计算机教师,著有中国第一套,历经五年实践证明深受学生欢迎的成功的AP计算机双语教材,2013年以93%的满分率开创了中国AP计算机成功的先河,远远超出全美26.6%的满分率,为中国AP计算机教学树立了典范,并在同年加拿大计算机竞赛中勇夺桂冠,任教学生获哥伦比亚大学,麻省理工学院,卡耐基梅隆大学,宾夕法尼亚大学,康奈尔大学,西北大学等学校录取,远程学生遍及北京、长春、南京、重庆、广州、济南, 深圳、成都、费城,洛杉矶,加州,宾州,新罕布什尔州等地,希望借此平台为信息技术的发展做出贡献!

JAVA实现的各种排序算法  

2011-09-05 21:13:29|  分类: 默认分类 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |


import java.util.Random;

/**
 * @author George
 * @date:2011-1-31 18:42:28
 */
public class Sort {
    public static void OutputArray(int[] array) {
        for (int data : array) {
            System.out.print(data + " ");
        }
        System.out.println();
    }
    public static int[] createArray() {
        int array[] = new int[10];
        Random r = new Random();
        for (int i = 0; i < 10; i++) {
            array[i] = r.nextInt(100);
        }
        System.out.println("==========原始数组===========");
        OutputArray(array);
        return array;
    }
  /**
   * 冒泡排序----交换排序的一种
   * 方法:相邻两元素进行比较,如有需要则进行交换,每完成一次循环就将最大元素排在最后(如从小到大排序),
   * 下一次循环是将其他的数进行类似操作。*/
    public static void bubbleSort(int[] array, String sortType) {
        int temp;
        if (sortType.equals("asc")) { //从小排到大
            //比较的轮数
            for (int i = 0; i < array.length - 1; i++) {
                //将相邻两个数进行比较,较大的数下沉,较小的数上升
                for (int j = 0; j < array.length - i-1; j++) {
                    if (array[j] > array[j + 1]) {
                        temp=array[j];
                        array[j]=array[j+1];
                        array[j+1]=temp;
                    }
                }
            }
        } else if (sortType.equals("desc")) { //倒排序,从大排到小
            //比较的轮数
            for (int i =0; i <array.length-1; i++) {
                //将相邻两个数进行比较,较大的数往后冒泡
                for (int j = 0; j <array.length - i-1; j++) {
                    if (array[j] <array[j + 1]) {
                        //交换相邻两个数
                        temp=array[j];
                        array[j]=array[j+1];
                        array[j+1]=temp;
                    }
                }
            }
        } else {
            System.out.println("您输入的排序类型错误!");
        }
    }
 /** 直接选择排序法----选择排序的一种
 * 方法:每一趟从待排序的数据元素中选出最小(或最大)的一个元素,
 *顺序放在已排好序的数列的最后,直到全部待排序的数据元素排完。*/
 public static void selectSort(int[] array, String sortType) {
          int temp,index;
          if (sortType.equals("asc")) { //正排序,从小排到大
          for (int i = 0; i < array.length; i++) {
              index = i;//这里不是index=0
              for (int j = i+1; j <array.length; j++)
                if (array[index]>array[j])
                    index = j;
                if(index!=i)
                 {
                      temp=array[i];
                      array[i]=array[index];
                      array[index]=temp;
                 }
              }
        } else if (sortType.equals("desc")) { //倒排序,从大排到小
                    for (int i = 0; i <array.length; i++) {
                      index = i;//这里不是index=0
                      for (int j =i+1;j <array.length; j++)
                           if (array[index]<array[j])
                                  index = j;  
                            //交换在位置i和index(最大值)两个数
                   if(index!=i)
                     {
                      temp=array[i];
                      array[i]=array[index];
                      array[index]=temp;
                    }
                 }
         } else {
                   System.out.println("您输入的排序类型错误!");
            }
 }
 /**
    * 插入排序
    * 方法:将一个记录插入到已排好序的有序表(有可能是空表)中,从而得到一个新的记录数增1的有序表。     * 性能:比较次数O(n^2),n^2/4
    *比较次数是前两者的一般,而复制所需的CPU时间较交换少,所以性能上比冒泡排序提高一倍多,而比选择排序也要快。
     */
    public static void insertSort(int[] array, String sortType) {
          int insertValue;
          if (sortType.equals("asc")) { //正排序,从小排到大
          //比较的轮数
          for (int i = 1; i <array.length; i++) {
         //保证前i个数排好序
              insertValue=array[i];
              int index=i-1;
              while(index>=0&&array[index]>insertValue)
              {
                  array[index+1]=array[index];
                  index--;
              }
              array[index+1]=insertValue;
             }
          }
     else if (sortType.equals("desc")) { //倒排序,从大排到小
              //比较的轮数
          for (int i = 1; i <array.length; i++) {
         //保证前i个数排好序
              insertValue=array[i];
              int index=i-1;
              while(index>=0&&array[index]<insertValue)
              {
                  array[index+1]=array[index];
                  index--;
              }
              array[index+1]=insertValue;
             }
          } else
              System.out.println("您输入的排序类型错误!");
}
     /**
   * 快速排序 快速排序使用分治法(Divide and conquer)策略来把一个序列(list)分为两个子序列(sub-lists)。 步骤为:
   * 1. 从数列中挑出一个元素,称为 "基准"(pivot), 2.
   * 重新排序数列,所有元素比基准值小的摆放在基准前面,所有元素比基准值大的摆在基准的后面(相同的数可以到任一边)。在这个分割之后,该基准是它的最后位置。这个称为分割(partition)操作。
   * 3. 递归地(recursive)把小于基准值元素的子数列和大于基准值元素的子数列排序。
   * 递回的最底部情形,是数列的大小是零或一,也就是永远都已经被排序好了。虽然一直递回下去,但是这个算法总会结束,因为在每次的迭代(iteration)中,它至少会把一个元素摆到它最后的位置去。       *      * @param data
   * 待排序的数组 */

  public static void quickSort(int[] array, String sortType) {
     if (sortType.equals("asc")) { // 正排序,从小排到大
         qsort_asc(array, 0, array.length - 1); }
     else if (sortType.equals("desc")) { // 倒排序,从大排到小
      qsort_desc(array,0,array.length-1);
 } else {
 System.out.println("您输入的排序类型错误!");
 }
}
 /**
  * 快速排序的具体实现,排正序
  */
public static void qsort_asc(int[] array, int left, int right) {
    int i, j,pivot;
    if (left < right) { // 这个条件用来结束递归
      i = left;
      j = right;
      pivot= array[i];
      while (i < j) {
          while (i < j && array[j]>pivot)
             j--; // 从右向左找第一个小于pivot的数
          if (i < j) {
              array[i] = array[j];
              i++;
            }
        while (i < j &&array[i]<pivot)
         i++; // 从左向右找第一个大于pivot的数
        if (i < j) {
          array[j] = array[i];
           j--;
}
}
array[i] =pivot;
qsort_asc(array, left, i - 1);
qsort_asc(array, i + 1, right);
}
}

 /**
  * 快速排序的具体实现,排倒序
  */
public static void qsort_desc(int[] array, int left, int right) {
    int i, j,pivot;
    if (left < right) { // 这个条件用来结束递归
      i = left;
      j = right;
      pivot= array[i];
      while (i < j) {
          while (i < j && array[j]<pivot)
             j--; // 从右向左找第一个大于pivot的数
          if (i < j) {
              array[i] = array[j];
              i++;
            }
        while (i < j &&array[i]>pivot)
         i++; // 从左向右找第一个小于pivot的数
        if (i < j) {
          array[j] = array[i];
           j--;
}
}
array[i] =pivot;
qsort_desc(array, left, i - 1);
qsort_desc(array, i + 1, right);
}
}

   public static void main(String[] args) {
        int[] arr1=createArray();
        System.out.println("==========冒泡排序后(正序)==========");
        bubbleSort(arr1, "asc");
        OutputArray(arr1);
        System.out.println("==========冒泡排序后(倒序)==========");
        bubbleSort(arr1, "desc");
        OutputArray(arr1);
        int[] arr2=createArray();
        System.out.println("==========选择排序后(正序)==========");
        selectSort(arr2, "asc");
        OutputArray(arr2);
        System.out.println("==========选择排序后(倒序)==========");
        selectSort(arr2, "desc");
        OutputArray(arr2);
        int[] arr3=createArray();
        System.out.println("==========插入排序后(正序)==========");
        insertSort(arr3, "asc");
        OutputArray(arr3);
        System.out.println("==========插入排序后(倒序)==========");
        insertSort(arr3, "desc");
        OutputArray(arr3);
        int[] arr4=createArray();
        System.out.println("==========快速排序后(正序)==========");
        quickSort(arr4, "asc");
        OutputArray(arr4);
        System.out.println("==========快速排序后(倒序)==========");
        quickSort(arr4, "desc");
        OutputArray(arr4);
    }
}

双向冒泡排序
import java.util.Random;
/**
 * @author George
 * @date:2011-2-3 17:08:51
 */
public class BubbleSort {
    public static void OutputArray(int[] array) {
        for (int data : array) {
            System.out.print(data + " ");
        }
        System.out.println();
    }
    public static int[] createArray(int n) {
        int array[] = new int[n];
        Random r = new Random();
        for (int i = 0; i < n; i++) {
            array[i] = r.nextInt(100);
        }
        System.out.println("==========原始数组===========");
        OutputArray(array);
        return array;
    }
    public static void bubble(int[] array){
        int i,start=0,end=array.length-1,temp;
        boolean flag=true;
        while(start<end&&flag)
        {
            flag=false;
            for(i=start;i<end;i++)//从上往下冒泡
            {
                if(array[i]>array[i+1])
                {
                    temp=array[i];
                    array[i]=array[i+1];
                    array[i+1]=temp;
                    flag=true;//表示交换
                }
            }
            end--;
            for(i=end;i>start;i--)
            {
                if(array[i]<array[i-1])
                {
                    temp=array[i];
                    array[i]=array[i-1];
                    array[i-1]=temp;
                    flag=true;//表示交换
                }
            }
            start++;
        }
    }
    public static void main(String[] args) {
        int arr[]=createArray(10);
        bubble(arr);
        System.out.println("==========排序后数组===========");
        OutputArray(arr);
    }
}

 

import java.util.Random;
/**
 * @author George
 * @date:2011-2-5 18:42:10
 */
public class Sort {
 public static void OutputArray(int[] array) {
        for (int data : array) {
            System.out.print(data + " ");
        }
        System.out.println();
    }
    public static int[] createArray(int n) {
        int array[] = new int[n];
        Random r = new Random();
        for (int i = 0; i < n; i++) {
            array[i] = r.nextInt(100);
        }
        System.out.println("==========原始数组===========");
        OutputArray(array);
        return array;
    }
   private static  int[] merge_sort(int[] array, int start, int end){
      int[] result = new int[end-start+1];
        if(start<end){
           int mid= (start+end)/2;
           int[] left= merge_sort(array, start, mid);
           int[] right =  merge_sort(array, mid+1, end);
           result= merge(left,right);
        } else if (start == end) {
            result[0] = array[start];
            return result;
        }
        return result;
    }
   private static int[]  merge(int[] left, int[] right) {
        int[] result = new int[left.length+right.length];
        int i=0;
        int j=0;
        int k=0;
        while(i<left.length&&j<right.length){
            if(left[i]<right[j]){
                result[k++] = left[i++];
            }else{
                result[k++] = right[j++];

            }
        }
        while(i<left.length){
            result[k++] = left[i++];
        }
        while (j<right.length) {
           result[k++]= right[j++];
        }
        return result;
    }
    public static void main(String[] args) {
        int arr[]=createArray(10);
        int[] result =  merge_sort(arr, 0, arr.length-1);
        System.out.println("==========排序后数组===========");
        OutputArray(result);
    }
}

  评论这张
 
阅读(473)| 评论(0)

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018