MyException - 我的异常网
当前位置:我的异常网» 编程 » 惯用的排序方法

惯用的排序方法

www.MyException.Cn  网友分享于:2013-12-22  浏览:3次
常用的排序方法

package com.util;

/**
 * 常用的排序方法 排序算法的分类如下: 1.插入排序法(直接插入排序法、折半插入排序法、希尔排序法) 2.交换排序法(冒泡排序法、快速排序法)
 * 3.选择排序法(直接选择排序法、堆排序法) 4.归并排序法 5.基数排序法 关于排序方法的选择:
 * (1)若n较小(如n≤50),可采用直接插入或直接选择排序。
 * 当记录规模较小时,直接插入排序较好;否则因为直接选择移动的记录数少于直接插人,应选直接选择排序为宜。
 * (2)若文件初始状态基本有序(指正序),则应选用直接插人、冒泡或随机的快速排序为宜;
 * (3)若n较大,则应采用时间复杂度为O(nlgn)的排序方法:快速排序、堆排序或归并排序。
 *
 * @author LW
 */
public class Sort {

 public static final int ASC = 0;// 正序
 public static final int DESC = 1;// 倒序

 /**
  * 交换数据中指定两元素的位置
  *
  * @param data
  * @param x
  * @param y
  */
 private static void swap(int[] data, int x, int y) {
  int temp = data[x];
  data[x] = data[y];
  data[y] = temp;
 }

 /**
  * 插入排序的基本思想为:首先寻找一个有序数列,然后将数组中的每个元素插入到该有序序列中,
  * 则该数组序列即可变为有序数列。具体实施办法为,首选将第一个元素看作是一个有序序列,然后
  * 从第二个元素开始遍历数组,将每个元素插入到从第一个元素到前一个元素的有序序列中,即可完 成排序。
  *
  * @param temp
  */
 public static void insertSort(int[] data) {
  for (int i = 1; i < data.length; i++) {
   int temp = data[i];
   int j = i - 1;
   while (j >= 0 && temp < data[j]) {
    data[j + 1] = data[j];
    j--;
   }
   data[j + 1] = temp;
  }
 }

 /**
  * 折半插入排序算法的java实现
  *
  * @param temp
  */
 public static void bInsertSort(int[] data) {
  int length = data.length;
  for (int i = 1; i < length; i++) {
   int temp = data[i];
   int low = 0;
   int high = i - 1;
   while (low <= high) {
    int middle = (low + high) / 2;
    if (temp < data[middle])
     high = middle - 1;
    else
     low = middle + 1;
   }
   for (int j = i; j > high + 1; j--) {
    data[j] = data[j - 1];
   }
   data[high + 1] = temp;
  }
 }

 /**
  *
  * 冒泡排序----交换排序的一种
  *
  * 方法:相邻两元素进行比较,如有需要则进行交换,每完成一次循环就将最大元素排在最后(如从小到大排序),下一次循环是将其他的数进行类似操作。
  * 性能:比较次数O(n^2),n^2/2;交换次数O(n^2),n^2/4
  *
  * @param data
  *            要排序的数组
  * @param sortType
  *            排序类型 ASC、DESC
  * @return
  *
  */
 public static void bubbleSort(int[] data, int sortType) {
  if (sortType == ASC) {
   for (int i = 1; i < data.length; i++) {
    for (int j = 0; j < data.length - i; j++) {
     if (data[j] > data[j + 1]) {
      swap(data, j, j + 1);
     }
    }
   }
  } else if (sortType == DESC) {
   for (int i = 1; i < data.length; i++) {
    for (int j = 0; j < data.length - i; j++) {
     if (data[j] < data[j + 1]) {
      swap(data, j, j + 1);
     }
    }
   }
  }
 }

 /**
  *
  * 直接选择排序法----选择排序的一种
  *
  * 方法:每一趟从待排序的数据元素中选出最小(或最大)的一个元素, 顺序放在已排好序的数列的最后,直到全部待排序的数据元素排完。
  * 性能:比较次数O(n^2),n^2/2 交换次数O(n),n
  * 交换次数比冒泡排序少多了,由于交换所需CPU时间比比较所需的CUP时间多,所以选择排序比冒泡排序快。
  * 但是N比较大时,比较所需的CPU时间占主要地位,所以这时的性能和冒泡排序差不太多,但毫无疑问肯定要快些。
  *
  * @param data
  *            要排序的数组
  * @param sortType
  *            排序类型
  * @return
  *
  */
 public static void selectSort(int[] data, int sortType) {
  if (sortType == ASC) {
   int index;
   for (int i = 1; i < data.length; i++) {
    index = 0;
    for (int j = 1; j <= data.length - i; j++) {
     if (data[j] > data[index]) {
      index = j;
     }
    }
    swap(data, data.length - i, index);
   }
  } else if (sortType == DESC) {
   int index;
   for (int i = 1; i < data.length; i++) {
    index = 0;
    for (int j = 1; j <= data.length - i; j++) {
     if (data[j] < data[index]) {
      index = j;
     }
    }
    swap(data, data.length - i, index);
   }
  }
 }

}

文章评论

程序员必看的十大电影
程序员必看的十大电影
写给自己也写给你 自己到底该何去何从
写给自己也写给你 自己到底该何去何从
5款最佳正则表达式编辑调试器
5款最佳正则表达式编辑调试器
我的丈夫是个程序员
我的丈夫是个程序员
看13位CEO、创始人和高管如何提高工作效率
看13位CEO、创始人和高管如何提高工作效率
程序员的鄙视链
程序员的鄙视链
代码女神横空出世
代码女神横空出世
程序员的一天:一寸光阴一寸金
程序员的一天:一寸光阴一寸金
Java程序员必看电影
Java程序员必看电影
编程语言是女人
编程语言是女人
程序员周末都喜欢做什么?
程序员周末都喜欢做什么?
那些争议最大的编程观点
那些争议最大的编程观点
Web开发者需具备的8个好习惯
Web开发者需具备的8个好习惯
每天工作4小时的程序员
每天工作4小时的程序员
10个调试和排错的小建议
10个调试和排错的小建议
要嫁就嫁程序猿—钱多话少死的早
要嫁就嫁程序猿—钱多话少死的早
程序员和编码员之间的区别
程序员和编码员之间的区别
我跳槽是因为他们的显示器更大
我跳槽是因为他们的显示器更大
Java 与 .NET 的平台发展之争
Java 与 .NET 的平台发展之争
“肮脏的”IT工作排行榜
“肮脏的”IT工作排行榜
程序猿的崛起——Growth Hacker
程序猿的崛起——Growth Hacker
团队中“技术大拿”并非越多越好
团队中“技术大拿”并非越多越好
鲜为人知的编程真相
鲜为人知的编程真相
聊聊HTTPS和SSL/TLS协议
聊聊HTTPS和SSL/TLS协议
为啥Android手机总会越用越慢?
为啥Android手机总会越用越慢?
初级 vs 高级开发者 哪个性价比更高?
初级 vs 高级开发者 哪个性价比更高?
科技史上最臭名昭著的13大罪犯
科技史上最臭名昭著的13大罪犯
程序员眼里IE浏览器是什么样的
程序员眼里IE浏览器是什么样的
Web开发人员为什么越来越懒了?
Web开发人员为什么越来越懒了?
如何区分一个程序员是“老手“还是“新手“?
如何区分一个程序员是“老手“还是“新手“?
10个帮程序员减压放松的网站
10个帮程序员减压放松的网站
 程序员的样子
程序员的样子
总结2014中国互联网十大段子
总结2014中国互联网十大段子
不懂技术不要对懂技术的人说这很容易实现
不懂技术不要对懂技术的人说这很容易实现
亲爱的项目经理,我恨你
亲爱的项目经理,我恨你
程序员应该关注的一些事儿
程序员应该关注的一些事儿
做程序猿的老婆应该注意的一些事情
做程序猿的老婆应该注意的一些事情
老美怎么看待阿里赴美上市
老美怎么看待阿里赴美上市
如何成为一名黑客
如何成为一名黑客
老程序员的下场
老程序员的下场
一个程序员的时间管理
一个程序员的时间管理
程序员都该阅读的书
程序员都该阅读的书
漫画:程序员的工作
漫画:程序员的工作
旅行,写作,编程
旅行,写作,编程
“懒”出效率是程序员的美德
“懒”出效率是程序员的美德
软件开发程序错误异常ExceptionCopyright © 2009-2015 MyException 版权所有