Java实现几种常见排序方法（下）

xiaofei006

Java实现几种常见排序方法（下）
插入排序的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。其具体步骤参见代码及注释。
view plaincopy to clipboardprint?
   1. /**
   2.  * 插入排序
   3.  *  
   4.  * 从第一个元素开始，该元素可以认为已经被排序
   5.  * 取出下一个元素，在已经排序的元素序列中从后向前扫描
   6.  * 如果该元素（已排序）大于新元素，将该元素移到下一位置
   7.  * 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
   8.  * 将新元素插入到该位置中
   9.  * 重复步骤2
  10.  *  
  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 0 && temp  *  * 从第一个元素开始，该元素可以认为已经被排序 * 取出下一个元素，在已经排序的元素序列中从后向前扫描 * 如果该元素（已排序）大于新元素，将该元素移到下一位置 * 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置 * 将新元素插入到该位置中 * 重复步骤2 *  * * @param numbers */ public static void insertSort(int[] numbers) { int size = numbers.length, temp, j; for(int i=1; i 0 && temp  
   3.  *  
   4.  * 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
   5.  * 设定两个指针，最初位置分别为两个已经排序序列的起始位置
   6.  * 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
   7.  * 重复步骤3直到某一指针达到序列尾
   8.  * 将另一序列剩下的所有元素直接复制到合并序列尾
   9.  *  
  10.  * 算法参考：Java部落
  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  *  * 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列 * 设定两个指针，最初位置分别为两个已经排序序列的起始位置 * 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置 * 重复步骤3直到某一指针达到序列尾 * 将另一序列剩下的所有元素直接复制到合并序列尾 *  * 算法参考：Java部落 * * @param numbers */ public static void mergeSort(int[] numbers, int left, int right) { int t = 1;// 每组元素个数 int size = right - left + 1; while (t  
  21.      *  
  22.      * 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
  23.      * 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
  24.      * 针对所有的元素重复以上的步骤，除了最后一个。
  25.      * 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
  26.      *  
  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  
  46.      *  
  47.      * 从数列中挑出一个元素，称为“基准”
  48.      * 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分割之后，
  49.      * 该基准是它的最后位置。这个称为分割（partition）操作。
  50.      * 递归地把小于基准值元素的子数列和大于基准值元素的子数列排序。
  51.      *  
  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  base) && (j > start))  
  66.                     j--;  
  67.                 if (i  i)  
  78.                 quickSort(numbers, i, end);  
  79.         }  
  80.     }  
  81.     /**
  82.      * 选择排序
  83.      *  
  84.      * 在未排序序列中找到最小元素，存放到排序序列的起始位置
  85.      * 再从剩余未排序元素中继续寻找最小元素，然后放到排序序列末尾。
  86.      * 以此类推，直到所有元素均排序完毕。
  87.      *  
  88.      *  
  89.      * @param numbers
  90.      */  
  91.     public static void selectSort(int[] numbers) {  
  92.         int size = numbers.length, temp;  
  93.         for (int i = 0; i  i; j--) {  
  96.                 if (numbers[j]  
106.      *  
107.      * 从第一个元素开始，该元素可以认为已经被排序
108.      * 取出下一个元素，在已经排序的元素序列中从后向前扫描
109.      * 如果该元素（已排序）大于新元素，将该元素移到下一位置
110.      * 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
111.      * 将新元素插入到该位置中
112.      * 重复步骤2
113.      *  
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  0 && temp  
128.      *  
129.      * 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
130.      * 设定两个指针，最初位置分别为两个已经排序序列的起始位置
131.      * 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
132.      * 重复步骤3直到某一指针达到序列尾
133.      * 将另一序列剩下的所有元素直接复制到合并序列尾
134.      *  
135.      * 算法参考：Java部落
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  *  * 比较相邻的元素。如果第一个比第二个大，就交换他们两个。 * 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。 * 针对所有的元素重复以上的步骤，除了最后一个。 * 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。 *  * * @param numbers * 需要排序的整型数组 */ public static void bubbleSort(int[] numbers) { int temp; // 记录临时中间值 int size = numbers.length; // 数组大小 for (int i = 0; i  *  * 从数列中挑出一个元素，称为“基准” * 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分割之后， * 该基准是它的最后位置。这个称为分割（partition）操作。 * 递归地把小于基准值元素的子数列和大于基准值元素的子数列排序。 *  * * @param numbers * @param start * @param end */ public static void quickSort(int[] numbers, int start, int end) { if (start  base) && (j > start)) j--; if (i  i) quickSort(numbers, i, end); } } /** * 选择排序 *  * 在未排序序列中找到最小元素，存放到排序序列的起始位置 * 再从剩余未排序元素中继续寻找最小元素，然后放到排序序列末尾。 * 以此类推，直到所有元素均排序完毕。 *  * * @param numbers */ public static void selectSort(int[] numbers) { int size = numbers.length, temp; for (int i = 0; i  i; j--) { if (numbers[j]  *  * 从第一个元素开始，该元素可以认为已经被排序 * 取出下一个元素，在已经排序的元素序列中从后向前扫描 * 如果该元素（已排序）大于新元素，将该元素移到下一位置 * 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置 * 将新元素插入到该位置中 * 重复步骤2 *  * * @param numbers */ public static void insertSort(int[] numbers) { int size = numbers.length, temp, j; for (int i = 1; i  0 && temp  *  * 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列 * 设定两个指针，最初位置分别为两个已经排序序列的起始位置 * 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置 * 重复步骤3直到某一指针达到序列尾 * 将另一序列剩下的所有元素直接复制到合并序列尾 *  * 算法参考：Java部落 * * @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; } }
数字排序算法通常用来作为算法入门课程的基本内容，在实际应用（尤其是普通商业软件）中使用的频率较低，但是通过排序算法的实现，可以深入了解计算机语言的特点，可以以此作为学习各种编程语言的基础。
               
               
               

本文来自ChinaUnix博客，如果查看原文请点：http://blog.chinaunix.net/u2/88379/showart_2093716.html