请选择 进入手机版 | 继续访问电脑版
设为首页收藏本站

houcx

 找回密码
 立即注册
搜索
热搜: 活动 交友 discuz
查看: 1366|回复: 0

Java实现几种常见排序方法

[复制链接]

235

主题

237

帖子

1189

积分

管理员

Rank: 9Rank: 9Rank: 9

积分
1189
发表于 2016-11-15 13:52:10 | 显示全部楼层 |阅读模式
  1. 代码

  2. Code highlighting produced by Actipro CodeHighlighter (freeware)http://www.CodeHighlighter.com/-->package test.sort;   
  3. import java.util.Random;   
  4. //Java实现的排序类  
  5. public class NumberSort {   
  6.     //私有构造方法,禁止实例化  
  7.     private NumberSort() {   
  8.         super();   
  9.     }   
  10.     //冒泡法排序
  11.     public static void bubbleSort(int[] numbers) {   
  12.         int temp; // 记录临时中间值   
  13.         int size = numbers.length; // 数组大小   
  14.         for (int i = 0; i < size - 1; i++) {   
  15.             for (int j = i + 1; j < size; j++) {   
  16.                 if (numbers[i] < numbers[j]) { // 交换两数的位置   
  17.                     temp = numbers[i];   
  18.                     numbers[i] = numbers[j];   
  19.                     numbers[j] = temp;   
  20.                 }   
  21.             }   
  22.         }   
  23.     }   
  24.     //快速排序
  25.     public static void quickSort(int[] numbers, int start, int end) {   
  26.         if (start < end) {   
  27.             int base = numbers[start]; // 选定的基准值(第一个数值作为基准值)   
  28.             int temp; // 记录临时中间值   
  29.             int i = start, j = end;   
  30.             do {   
  31.                 while ((numbers[i] < base) && (i < end))   
  32.                     i++;   
  33.                 while ((numbers[j] > base) && (j > start))   
  34.                     j--;   
  35.                 if (i <= j) {   
  36.                     temp = numbers[i];   
  37.                     numbers[i] = numbers[j];   
  38.                     numbers[j] = temp;   
  39.                     i++;   
  40.                     j--;   
  41.                 }   
  42.             } while (i <= j);   
  43.             if (start < j)   
  44.                 quickSort(numbers, start, j);   
  45.             if (end > i)   
  46.                 quickSort(numbers, i, end);   
  47.         }   
  48.     }   
  49.     //选择排序
  50.     public static void selectSort(int[] numbers) {   
  51.         int size = numbers.length, temp;   
  52.         for (int i = 0; i < size; i++) {   
  53.             int k = i;   
  54.             for (int j = size - 1; j > i; j--) {   
  55.                 if (numbers[j] < numbers[k])   
  56.                     k = j;   
  57.             }   
  58.             temp = numbers[i];   
  59.             numbers[i] = numbers[k];   
  60.             numbers[k] = temp;   
  61.         }   
  62.     }   
  63.     //插入排序   
  64.     // @param numbers  
  65.     public static void insertSort(int[] numbers) {   
  66.         int size = numbers.length, temp, j;   
  67.         for (int i = 1; i < size; i++) {   
  68.             temp = numbers[i];   
  69.             for (j = i; j > 0 && temp < numbers[j - 1]; j--)   
  70.                 numbers[j] = numbers[j - 1];   
  71.             numbers[j] = temp;   
  72.         }   
  73.     }   
  74.     //归并排序  
  75.     public static void mergeSort(int[] numbers, int left, int right) {   
  76.         int t = 1;// 每组元素个数   
  77.         int size = right - left + 1;   
  78.         while (t < size) {   
  79.             int s = t;// 本次循环每组元素个数   
  80.             t = 2 * s;   
  81.             int i = left;   
  82.             while (i + (t - 1) < size) {   
  83.                 merge(numbers, i, i + (s - 1), i + (t - 1));   
  84.                 i += t;   
  85.             }   
  86.             if (i + (s - 1) < right)   
  87.                 merge(numbers, i, i + (s - 1), right);   
  88.         }   
  89.     }   
  90.     //归并算法实现  
  91.     private static void merge(int[] data, int p, int q, int r) {   
  92.         int[] B = new int[data.length];   
  93.         int s = p;   
  94.         int t = q + 1;   
  95.         int k = p;   
  96.         while (s <= q && t <= r) {   
  97.             if (data[s] <= data[t]) {   
  98.                 B[k] = data[s];   
  99.                 s++;   
  100.             } else {   
  101.                 B[k] = data[t];   
  102.                 t++;   
  103.             }   
  104.             k++;   
  105.         }   
  106.         if (s == q + 1)   
  107.             B[k++] = data[t++];   
  108.         else  
  109.             B[k++] = data[s++];   
  110.         for (int i = p; i <= r; i++)   
  111.             data[i] = B[i];   
  112.     }   
  113.   
  114. }
复制代码


日常操作中常见的排序方法有:冒泡排序、快速排序、选择排序、插入排序、希尔排序,甚至还有基数排序、鸡尾酒排序、桶排序、鸽巢排序、归并排序等。
冒泡排序是一种简单的排序算法。它重复地走访过要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。
[url=][/url]
代码/**  
* 冒泡法排序<br/>  

* <li>比较相邻的元素。如果第一个比第二个大,就交换他们两个。</li>  
* <li>对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对。在这一点,最后的元素应该会是最大的数。</li>  
* <li>针对所有的元素重复以上的步骤,除了最后一个。</li>  
* <li>持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。</li>  

*   
*
@param numbers  
*            需要排序的整型数组  
*/  
public static void bubbleSort(int[] numbers) {   
   
int temp; // 记录临时中间值   
    int size = numbers.length; // 数组大小   
    for (int i = 0; i < size - 1; i++) {   
        
for (int j = i + 1; j < size; j++) {   
            
if (numbers < numbers[j]) { // 交换两数的位置   
                temp = numbers;   
                numbers
= numbers[j];   
                numbers[j]
= temp;   
            }   
        }   
    }   
}  


[url=][/url]



快速排序使用分治法策略来把一个序列分为两个子序列。

[url=][/url]
代码/**  
* 快速排序<br/>  
* <ul>  
* <li>从数列中挑出一个元素,称为“基准”</li>  
* <li>重新排序数列,所有元素比基准值小的摆放在基准前面,所有元素比基准值大的摆在基准的后面(相同的数可以到任一边)。在这个分割之后,  
* 该基准是它的最后位置。这个称为分割(partition)操作。</li>  
* <li>递归地把小于基准值元素的子数列和大于基准值元素的子数列排序。</li>  
* </ul>  
*   
*
@param numbers  
*
@param start  
*
@param end  
*/  
public static void quickSort(int[] numbers, int start, int end) {   
   
if (start < end) {   
        
int base = numbers[start]; // 选定的基准值(第一个数值作为基准值)   
        int temp; // 记录临时中间值   
        int i = start, j = end;   
        
do {   
            
while ((numbers < base) && (i < end))   
                i
++;   
            
while ((numbers[j] > base) && (j > start))   
                j
--;   
            
if (i <= j) {   
                temp
= numbers;   
                numbers
= numbers[j];   
                numbers[j]
= temp;   
                i
++;   
                j
--;   
            }   
        }
while (i <= j);   
        
if (start < j)   
            quickSort(numbers, start, j);   
        
if (end > i)   
            quickSort(numbers, i, end);   
    }   
}  


[url=][/url]



选择排序是一种简单直观的排序方法,每次寻找序列中的最小值,然后放在最末尾的位置。

[url=][/url]
代码/**  
* 选择排序<br/>  
* <li>在未排序序列中找到最小元素,存放到排序序列的起始位置</li>  
* <li>再从剩余未排序元素中继续寻找最小元素,然后放到排序序列末尾。</li>  
* <li>以此类推,直到所有元素均排序完毕。</li>  

*   
*
@param numbers  
*/  
public static void selectSort(int[] numbers) {   
   
int size = numbers.length, temp;   
   
for (int i = 0; i < size; i++) {   
        
int k = i;   
        
for (int j = size - 1; j >i; j--)  {   
            
if (numbers[j] < numbers[k])  k = j;   
        }   
        temp
= numbers;   
        numbers
= numbers[k];   
        numbers[k]
= temp;   
    }   
}  



[url=][/url]



插入排序的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。其具体步骤参见代码及注释。

[url=][/url]
代码/**  
* 插入排序<br/>  
* <ul>  
* <li>从第一个元素开始,该元素可以认为已经被排序</li>  
* <li>取出下一个元素,在已经排序的元素序列中从后向前扫描</li>  
* <li>如果该元素(已排序)大于新元素,将该元素移到下一位置</li>  
* <li>重复步骤3,直到找到已排序的元素小于或者等于新元素的位置</li>  
* <li>将新元素插入到该位置中</li>  
* <li>重复步骤2</li>  
* </ul>  
*   
*
@param numbers  
*/  
public static void insertSort(int[] numbers) {   
   
int size = numbers.length, temp, j;   
   
for(int i=1; i<size; i++) {   
        temp
= numbers;   
        
for(j = i; j > 0 && temp < numbers[j-1]; j--)   
            numbers[j]
= numbers[j-1];   
        numbers[j]
= temp;   
    }   
}  


[url=][/url]



归并排序是建立在归并操作上的一种有效的排序算法,归并是指将两个已经排序的序列合并成一个序列的操作。参考代码如下:

[url=][/url]
代码/**  
* 归并排序<br/>  
* <ul>  
* <li>申请空间,使其大小为两个已经排序序列之和,该空间用来存放合并后的序列</li>  
* <li>设定两个指针,最初位置分别为两个已经排序序列的起始位置</li>  
* <li>比较两个指针所指向的元素,选择相对小的元素放入到合并空间,并移动指针到下一位置</li>  
* <li>重复步骤3直到某一指针达到序列尾</li>  
* <li>将另一序列剩下的所有元素直接复制到合并序列尾</li>  
* </ul>  
*   
*
@param numbers  
*/  
public static void mergeSort(int[] numbers, int left, int right) {   
   
int t = 1;// 每组元素个数   
    int size = right - left + 1;   
   
while (t < size) {   
        
int s = t;// 本次循环每组元素个数   
        t = 2 * s;   
        
int i = left;   
        
while (i + (t - 1) < size) {   
            merge(numbers, i, i
+ (s - 1), i + (t - 1));   
            i
+= t;   
        }   
        
if (i + (s - 1) < right)   
            merge(numbers, i, i
+ (s - 1), right);   
    }   
}   
/**  
* 归并算法实现  
*   
*
@param data  
*
@param p  
*
@param q  
*
@param r  
*/  
private static void merge(int[] data, int p, int q, int r) {   
   
int[] B = new int[data.length];   
   
int s = p;   
   
int t = q + 1;   
   
int k = p;   
   
while (s <= q && t <= r) {   
        
if (data <= data[t]) {   
            B[k]
= data;   
            s
++;   
        }
else {   
            B[k]
= data[t];   
            t
++;   
        }   
        k
++;   
    }   
   
if (s == q + 1)   
        B[k
++] = data[t++];   
   
else  
        B[k
++] = data[s++];   
   
for (int i = p; i <= r; i++)   
        data
= B;   
}  


[url=][/url]




































来自:http://www.cnblogs.com/sevenyuan/archive/2009/12/04/1616897.html

[发帖际遇]: admin 发帖时在路边捡到 2 金钱,偷偷放进了口袋. 幸运榜 / 衰神榜
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

QQ|Archiver|手机版|小黑屋|houcx ( 京ICP备15004793号  

GMT+8, 2019-9-20 19:55 , Processed in 0.066896 second(s), 27 queries .

Powered by houcx! X3.2

© 2001-2013 Comsenz Inc.

快速回复 返回顶部 返回列表