`
bj_dzj
  • 浏览: 16395 次
  • 性别: Icon_minigender_1
  • 来自: 北京
社区版块
存档分类
最新评论

java常用排序

 
阅读更多

日常操作中常见的排序方法有：冒泡排序、快速排序、选择排序、插入排序、希尔排序，甚至还有基数排序、鸡尾酒排序、桶排序、鸽巢排序、归并排序等。

冒泡排序是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。

 

 

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

 

Java代码 复制代码
  1. /**  
  2.  * 快速排序<br/>  
  3.  * <ul>  
  4.  * <li>从数列中挑出一个元素，称为“基准”</li>  
  5.  * <li>重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分割之后，  
  6.  * 该基准是它的最后位置。这个称为分割（partition）操作。</li>  
  7.  * <li>递归地把小于基准值元素的子数列和大于基准值元素的子数列排序。</li>  
  8.  * </ul>  
  9.  *   
  10.  * @param numbers  
  11.  * @param start  
  12.  * @param end  
  13.  */  
  14. public static void quickSort(int[] numbers, int start, int end) {   
  15.     if (start < end) {   
  16.         int base = numbers[start]; // 选定的基准值（第一个数值作为基准值）   
  17.         int temp; // 记录临时中间值   
  18.         int i = start, j = end;   
  19.         do {   
  20.             while ((numbers[i] < base) && (i < end))   
  21.                 i++;   
  22.             while ((numbers[j] > base) && (j > start))   
  23.                 j--;   
  24.             if (i <= j) {   
  25.                 temp = numbers[i];   
  26.                 numbers[i] = numbers[j];   
  27.                 numbers[j] = temp;   
  28.                 i++;   
  29.                 j--;   
  30.             }   
  31.         } while (i <= j);   
  32.         if (start < j)   
  33.             quickSort(numbers, start, j);   
  34.         if (end > i)   
  35.             quickSort(numbers, i, end);   
  36.     }   
  37. }  

 

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

 

Java代码 复制代码
  1. /**  
  2.  * 选择排序<br/>  
  3.  * <ul>  
  4.  * <li>在未排序序列中找到最小元素，存放到排序序列的起始位置</li>  
  5.  * <li>再从剩余未排序元素中继续寻找最小元素，然后放到排序序列末尾。</li>  
  6.  * <li>以此类推，直到所有元素均排序完毕。</li>  
  7.  * </ul>  
  8.  *   
  9.  * @param numbers  
  10.  */  
  11. public static void selectSort(int[] numbers) {   
  12.     int size = numbers.length, temp;   
  13.     for (int i = 0; i < size; i++) {   
  14.         int k = i;   
  15.         for (int j = size - 1; j >i; j--)  {   
  16.             if (numbers[j] < numbers[k])  k = j;   
  17.         }   
  18.         temp = numbers[i];   
  19.         numbers[i] = numbers[k];   
  20.         numbers[k] = temp;   
  21.     }   
  22. }  

 

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

 

view plaincopy to clipboardprint?
  1. /** 
  2.  * 插入排序<br/> 
  3.  * <ul> 
  4.  * <li>从第一个元素开始，该元素可以认为已经被排序</li> 
  5.  * <li>取出下一个元素，在已经排序的元素序列中从后向前扫描</li> 
  6.  * <li>如果该元素（已排序）大于新元素，将该元素移到下一位置</li> 
  7.  * <li>重复步骤3，直到找到已排序的元素小于或者等于新元素的位置</li> 
  8.  * <li>将新元素插入到该位置中</li> 
  9.  * <li>重复步骤2</li> 
  10.  * </ul> 
  11.  *  
  12.  * @param numbers 
  13.  */  
  14. public static void insertSort(int[] numbers) {  
  15.     int size = numbers.length, temp, j;  
  16.     for(int i=1; i<size; i++) {  
  17.         temp = numbers[i];  
  18.         for(j = i; j > 0 && temp < numbers[j-1]; j--)  
  19.             numbers[j] = numbers[j-1];  
  20.         numbers[j] = temp;  
  21.     }  
  22. }  

 

 

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

 

view plaincopy to clipboardprint?
  1. /** 
  2.  * 归并排序<br/> 
  3.  * <ul> 
  4.  * <li>申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列</li> 
  5.  * <li>设定两个指针，最初位置分别为两个已经排序序列的起始位置</li> 
  6.  * <li>比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置</li> 
  7.  * <li>重复步骤3直到某一指针达到序列尾</li> 
  8.  * <li>将另一序列剩下的所有元素直接复制到合并序列尾</li> 
  9.  * </ul> 
  10.  * 算法参考：<a href="http://www.cnitblog.com/intrl/" mce_href="http://www.cnitblog.com/intrl/">Java部落</a> 
  11.  *  
  12.  * @param numbers 
  13.  */  
  14. public static void mergeSort(int[] numbers, int left, int right) {  
  15.     int t = 1;// 每组元素个数   
  16.     int size = right - left + 1;  
  17.     while (t < size) {  
  18.         int s = t;// 本次循环每组元素个数   
  19.         t = 2 * s;  
  20.         int i = left;  
  21.         while (i + (t - 1) < size) {  
  22.             merge(numbers, i, i + (s - 1), i + (t - 1));  
  23.             i += t;  
  24.         }  
  25.         if (i + (s - 1) < right)  
  26.             merge(numbers, i, i + (s - 1), right);  
  27.     }  
  28. }  
  29. /** 
  30.  * 归并算法实现 
  31.  *  
  32.  * @param data 
  33.  * @param p 
  34.  * @param q 
  35.  * @param r 
  36.  */  
  37. private static void merge(int[] data, int p, int q, int r) {  
  38.     int[] B = new int[data.length];  
  39.     int s = p;  
  40.     int t = q + 1;  
  41.     int k = p;  
  42.     while (s <= q && t <= r) {  
  43.         if (data[s] <= data[t]) {  
  44.             B[k] = data[s];  
  45.             s++;  
  46.         } else {  
  47.             B[k] = data[t];  
  48.             t++;  
  49.         }  
  50.         k++;  
  51.     }  
  52.     if (s == q + 1)  
  53.         B[k++] = data[t++];  
  54.     else  
  55.         B[k++] = data[s++];  
  56.     for (int i = p; i <= r; i++)  
  57.         data[i] = B[i];  
  58. }  

 

 

将之前介绍的所有排序算法整理成NumberSort类，代码

 

view plaincopy to clipboardprint?
  1. /** 
  2.  * BubbleSort.class 
  3.  */  
  4. package test.sort;  
  5. import java.util.Random;  
  6. /** 
  7.  * Java实现的排序类 
  8.  *  
  9.  * @author cyq 
  10.  *  
  11.  */  
  12. public class NumberSort {  
  13.     /** 
  14.      * 私有构造方法，禁止实例化 
  15.      */  
  16.     private NumberSort() {  
  17.         super();  
  18.     }  
  19.     /** 
  20.      * 冒泡法排序<br/> 
  21.      * <ul> 
  22.      * <li>比较相邻的元素。如果第一个比第二个大，就交换他们两个。</li> 
  23.      * <li>对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。</li> 
  24.      * <li>针对所有的元素重复以上的步骤，除了最后一个。</li> 
  25.      * <li>持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。</li> 
  26.      * </ul> 
  27.      *  
  28.      * @param numbers 
  29.      *            需要排序的整型数组 
  30.      */  
  31.     public static void bubbleSort(int[] numbers) {  
  32.         int temp; // 记录临时中间值   
  33.         int size = numbers.length; // 数组大小   
  34.         for (int i = 0; i < size - 1; i++) {  
  35.             for (int j = i + 1; j < size; j++) {  
  36.                 if (numbers[i] < numbers[j]) { // 交换两数的位置   
  37.                     temp = numbers[i];  
  38.                     numbers[i] = numbers[j];  
  39.                     numbers[j] = temp;  
  40.                 }  
  41.             }  
  42.         }  
  43.     }  
  44.     /** 
  45.      * 快速排序<br/> 
  46.      * <ul> 
  47.      * <li>从数列中挑出一个元素，称为“基准”</li> 
  48.      * <li>重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分割之后， 
  49.      * 该基准是它的最后位置。这个称为分割（partition）操作。</li> 
  50.      * <li>递归地把小于基准值元素的子数列和大于基准值元素的子数列排序。</li> 
  51.      * </ul> 
  52.      *  
  53.      * @param numbers 
  54.      * @param start 
  55.      * @param end 
  56.      */  
  57.     public static void quickSort(int[] numbers, int start, int end) {  
  58.         if (start < end) {  
  59.             int base = numbers[start]; // 选定的基准值（第一个数值作为基准值）   
  60.             int temp; // 记录临时中间值   
  61.             int i = start, j = end;  
  62.             do {  
  63.                 while ((numbers[i] < base) && (i < end))  
  64.                     i++;  
  65.                 while ((numbers[j] > base) && (j > start))  
  66.                     j--;  
  67.                 if (i <= j) {  
  68.                     temp = numbers[i];  
  69.                     numbers[i] = numbers[j];  
  70.                     numbers[j] = temp;  
  71.                     i++;  
  72.                     j--;  
  73.                 }  
  74.             } while (i <= j);  
  75.             if (start < j)  
  76.                 quickSort(numbers, start, j);  
  77.             if (end > i)  
  78.                 quickSort(numbers, i, end);  
  79.         }  
  80.     }  
  81.     /** 
  82.      * 选择排序<br/> 
  83.      * <ul> 
  84.      * <li>在未排序序列中找到最小元素，存放到排序序列的起始位置</li> 
  85.      * <li>再从剩余未排序元素中继续寻找最小元素，然后放到排序序列末尾。</li> 
  86.      * <li>以此类推，直到所有元素均排序完毕。</li> 
  87.      * </ul> 
  88.      *  
  89.      * @param numbers 
  90.      */  
  91.     public static void selectSort(int[] numbers) {  
  92.         int size = numbers.length, temp;  
  93.         for (int i = 0; i < size; i++) {  
  94.             int k = i;  
  95.             for (int j = size - 1; j > i; j--) {  
  96.                 if (numbers[j] < numbers[k])  
  97.                     k = j;  
  98.             }  
  99.             temp = numbers[i];  
  100.             numbers[i] = numbers[k];  
  101.             numbers[k] = temp;  
  102.         }  
  103.     }  
  104.     /** 
  105.      * 插入排序<br/> 
  106.      * <ul> 
  107.      * <li>从第一个元素开始，该元素可以认为已经被排序</li> 
  108.      * <li>取出下一个元素，在已经排序的元素序列中从后向前扫描</li> 
  109.      * <li>如果该元素（已排序）大于新元素，将该元素移到下一位置</li> 
  110.      * <li>重复步骤3，直到找到已排序的元素小于或者等于新元素的位置</li> 
  111.      * <li>将新元素插入到该位置中</li> 
  112.      * <li>重复步骤2</li> 
  113.      * </ul> 
  114.      *  
  115.      * @param numbers 
  116.      */  
  117.     public static void insertSort(int[] numbers) {  
  118.         int size = numbers.length, temp, j;  
  119.         for (int i = 1; i < size; i++) {  
  120.             temp = numbers[i];  
  121.             for (j = i; j > 0 && temp < numbers[j - 1]; j--)  
  122.                 numbers[j] = numbers[j - 1];  
  123.             numbers[j] = temp;  
  124.         }  
  125.     }  
  126.     /** 
  127.      * 归并排序<br/> 
  128.      * <ul> 
  129.      * <li>申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列</li> 
  130.      * <li>设定两个指针，最初位置分别为两个已经排序序列的起始位置</li> 
  131.      * <li>比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置</li> 
  132.      * <li>重复步骤3直到某一指针达到序列尾</li> 
  133.      * <li>将另一序列剩下的所有元素直接复制到合并序列尾</li> 
  134.      * </ul> 
  135.      * 算法参考：<a href="http://www.cnitblog.com/intrl/" mce_href="http://www.cnitblog.com/intrl/">Java部落</a> 
  136.      *  
  137.      * @param numbers 
  138.      */  
  139.     public static void mergeSort(int[] numbers, int left, int right) {  
  140.         int t = 1;// 每组元素个数   
  141.         int size = right - left + 1;  
  142.         while (t < size) {  
  143.             int s = t;// 本次循环每组元素个数   
  144.             t = 2 * s;  
  145.             int i = left;  
  146.             while (i + (t - 1) < size) {  
  147.                 merge(numbers, i, i + (s - 1), i + (t - 1));  
  148.                 i += t;  
  149.             }  
  150.             if (i + (s - 1) < right)  
  151.                 merge(numbers, i, i + (s - 1), right);  
  152.         }  
  153.     }  
  154.     /** 
  155.      * 归并算法实现 
  156.      *  
  157.      * @param data 
  158.      * @param p 
  159.      * @param q 
  160.      * @param r 
  161.      */  
  162.     private static void merge(int[] data, int p, int q, int r) {  
  163.         int[] B = new int[data.length];  
  164.         int s = p;  
  165.         int t = q + 1;  
  166.         int k = p;  
  167.         while (s <= q && t <= r) {  
  168.             if (data[s] <= data[t]) {  
  169.                 B[k] = data[s];  
  170.                 s++;  
  171.             } else {  
  172.                 B[k] = data[t];  
  173.                 t++;  
  174.             }  
  175.             k++;  
  176.         }  
  177.         if (s == q + 1)  
  178.             B[k++] = data[t++];  
  179.         else  
  180.             B[k++] = data[s++];  
  181.         for (int i = p; i <= r; i++)  
  182.             data[i] = B[i];  
  183.     }  
  184.   
  185. }  

 

数字排序算法通常用来作为算法入门课程的基本内容，在实际应用（尤其是普通商业软件）中使用的频率较低，但是通过排序算法的实现，可以深入了解计算机语言的特点，可以以此作为学习各种编程语言的基础。

分享到：
| Linux 常用命令
评论
发表评论

您还没有登录,请您登录后再发表评论

相关推荐

    Java常用排序算法&程序员必须掌握的8大排序算法+二分法查找

    本资料包聚焦于"Java常用排序算法"和"程序员必须掌握的8大排序算法"，并深入探讨了"二分法查找"这一高效搜索技术。 首先，我们来看八大排序算法。这些算法包括： 1. **冒泡排序**：最简单的排序方法，通过不断交换...

    Java常用排序算法

    以下是关于"Java常用排序算法"的详细解释： 1. 插入排序（Insertion Sort） 插入排序是一种简单直观的排序算法，它的工作原理类似于我们日常生活中整理扑克牌的过程。算法分为两个阶段：遍历待排序的数组，将每个...

    详解Java常用排序算法-选择排序

    详解Java常用排序算法-选择排序 选择排序（Selection Sort）是一种简单的排序算法，它的基本思想是每次从待排序的元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的元素排完。 选择...

    详解Java常用排序算法-归并排序

    Java常用排序算法-归并排序 归并排序是一种分治思想的排序算法，其基本思想是将待排序的数组分成若干个子序列，每个子序列都是有序的，然后再将子序列合并成一个有序的数组。这种算法的时间复杂度为O(n log n)，...

    Java常用排序算法程序员必须掌握的8大排序算法Java开

    本文将深入探讨Java中的八大常用排序算法，这些算法对于提升程序效率、优化数据处理具有重要意义。这8大排序算法包括：冒泡排序、插入排序、选择排序、快速排序、归并排序、堆排序、希尔排序以及桶排序。 1. **冒泡...

    Java常用排序算法程序员必须掌握的8大排序算法

    冒泡排序--Java常用排序算法程序员必须掌握的8大排序算法

    Java常用排序算法源码

    以下是对Java中几种常见排序算法的详细解析： 1. 冒泡排序： 冒泡排序是一种简单直观的排序算法，通过不断交换相邻的不正确顺序元素来达到排序的目的。它的时间复杂度为O(n^2)，在处理大量数据时效率较低。尽管效率...

    java 常用排序算法

    总结来说，Java中常用的排序算法如Shell排序和快速排序各有特点，Shell排序适用于处理大型数据，而快速排序通常在平均情况下具有较高的效率。在实际应用中，根据数据特性选择合适的排序算法至关重要，以实现最佳性能...

    Java常用排序算法&程序员必须掌握的8大排序算法+二分法查找（同步到博客）.doc

    【Java 常用排序算法】排序是编程中常见的任务之一，主要分为四类：插入排序、交换排序、选择排序和归并排序。此外，还有分配排序中的基数排序。以下是对这些排序算法的详细说明： 1. **直接插入排序**： 直接插入...

    详解Java常用排序算法-桶排序

    在 Java 中，桶排序可以使用以下步骤来实现： 1. 首先，找到输入数组中的最小值和最大值，以确定桶的个数。 2. 然后，创建一个大小为桶的个数的桶列表，用于存储待排序的元素。 3. 接下来，将输入数组中的元素分配...

    详解Java常用排序算法-基数排序

    在 Java 中，基数排序可以通过以下步骤来实现： 1. 首先，找到输入数组中的最大值，并计算最大值的位数。 2. 创建一个大小为 10 的桶列表，用于存储每个桶中的元素。 3. 依次遍历输入数组，将每个元素按照其个位、...

    详解Java常用排序算法-插入排序

    在 Java 中，插入排序算法可以通过以下代码实现： ```java public class Insertion { public static void insertionSort(int[] arr) { int n = arr.length; for (int i = 1; i ; i++) { int key = arr[i]; int ...

    Java常用排序 经典算法

    - 实例：在Java中，通过两个嵌套循环实现，外层循环控制未排序部分，内层循环用于将当前元素与已排序部分的元素进行比较并移动，直到找到合适的位置插入。 - 代码实现（部分）： ```java for (int i = 1; i ; i+...

    详解Java常用排序算法-希尔排序

    在 Java 中，希尔排序可以使用以下代码实现： ```java public class Shell { public static void shellSort(int[] arr) { int n = arr.length; for (int gap = n / 2; gap &gt; 0; gap /= 2) { for (int i = gap; ...

    详解Java常用排序算法-快速排序

    在 Java 中，快速排序算法可以使用递归函数来实现。例如，下面的代码就是一个使用快速排序算法对整数数组进行排序的示例： ```java public class Quick { public static void quickSort(int[] arr, int low, int ...

    详解Java常用排序算法-冒泡排序

    Java排序算法之冒泡排序详解 冒泡排序（Bubble Sort）是一种简单的排序算法，它重复地遍历要排序的数列，一次比较两个元素，如果它们的顺序错误就交换位置。这个过程持续对数列的末尾进行，直到整个数列都排序完成...

    常用排序算法java演示

    本文将深入探讨标题"常用排序算法java演示"中涉及的知识点，包括排序算法的原理、Java实现方式以及其在实际应用中的图形演示。 首先，让我们逐一了解几种常见的排序算法： 1. **冒泡排序（Bubble Sort）**：这是一...

Magicbox
Global site tag (gtag.js) - Google Analytics