|
算法和数据结构是每个高级程序员必须掌握的。常用的内部排序包括选择排序、交换排序、插入排序、归并排序、桶式排序和基数排序。本篇将详细讲述常用的内部排序中的交换排序。之所以称为交换排序，是因为这些算法的主体是数据组中的数据不断交换。交换排序包括冒泡排序和快速排序。 转载请注明出处——http://www.cnblogs.com/zrtqsk/p/3802583.html，谢谢！ 一、工具类 为了方便研究排序，这里，我创建了一个简单的工具类，用于生成排序数据，以及输出排序内容。研究排序，当然，所有数据设置为int类型就可以了。如下：  package sort; import java.util.Arrays; import java.util.Random; /** @ClassName: SortUtil * @Description: 排序工具类 * @author qsk * @date 2014年6月21日 下午8:14:55 */ public class SortUtil { /** * @Title: outputArray * @Description: 输出int类型数组 * @param @param array * @return void * @throws */ public static void outputArray(int[] array) { System.out.println(Arrays.toString(array)); } /** * @Title: getRandomArray * @Description: 得到100范围内的随机数组 * @param @param size * @param @return * @return int[] * @throws */ public static int[] getRandomArray(int size) { Random rd = new Random(System.currentTimeMillis()); int[] array = new int[size]; for (int i = 0; i < array.length; i++) { array[i] = rd.nextInt(100); } return array; } /** * @Title: getRandomArray * @Description: 得到100范围内的长度为10的随即数组 * @param @return * @return int[] * @throws */ public static int[] getRandomArray() { return getRandomArray(10); } }
二、冒泡排序 冒泡排序的大名，可谓无人不知。它的原理也是非常简单。 1、原理 对于n个数据的记录。 第1趟 ： 依次比较0和1、1和2、2和3...n-2和n-1索引处的元素，发现前面的大于后面的，就交换它们，这样一趟下来，最大的元素排到了最后面。 第2趟 ： 继续按照第1趟的做法再做一遍，一趟下来，第二大的元素排到了最后面。 ...... 这样经过n-1趟比较、交换，n个数据排序完毕。如果某一趟没有交换，表明已经排序完毕，可提前结束排序。
2、Java实现 package sort; /** * @ClassName: BubbleSort * @Description: 冒泡排序 * @author qsk * @date 2014年6月21日 下午4:45:57 */ public class BubbleSort { public static void sort(int[] source) { // 排序前先输出 SortUtil.outputArray(source); int size = source.length; for (int i = 0; i < size - 1; i++) { boolean isSwap = false; // 每次排序都从0开始，size-i-1结束,因为每一趟排序结束，都将排序队列中最大的那个移到最右边 for (int j = 0; j < size - i - 1; j++) { // if (source[j] > source[j + 1]) { int temp = source[j]; source[j] = source[j + 1]; source[j + 1] = temp; isSwap = true; } } // 如果没有换，代表排序已经结束 if (!isSwap) { break; } // 每一次交换结束时输出 SortUtil.outputArray(source); } } public static void main(String[] args) { sort(SortUtil.getRandomArray()); } } 如上，注释已经非常清楚了，结果如下： [35, 63, 63, 24, 21, 40, 26, 22, 2, 41] [35, 63, 24, 21, 40, 26, 22, 2, 41, 63] [35, 24, 21, 40, 26, 22, 2, 41, 63, 63] [24, 21, 35, 26, 22, 2, 40, 41, 63, 63] [21, 24, 26, 22, 2, 35, 40, 41, 63, 63] [21, 24, 22, 2, 26, 35, 40, 41, 63, 63] [21, 22, 2, 24, 26, 35, 40, 41, 63, 63] [21, 2, 22, 24, 26, 35, 40, 41, 63, 63] [2, 21, 22, 24, 26, 35, 40, 41, 63, 63]
3、时间复杂度和稳定性 冒泡排序的时间复杂度是O(N2)。 冒泡排序是稳定的算法，它满足稳定算法的定义。
三、快速排序 快速排序是一种速度非常快的交换排序方法，不过实现起来比较复杂。 1、原理 对于n个数据的记录。 从数据中取出第一个元素作为分界值、放在中间，所有比分界值小的元素放在左边，所有比分界值大的元素放在右边。然后对左右两个序列进行递归，重新选择分界值并进行移动。这样层层递归下去，直到每个子序列的元素只剩下一个。 这几天看到一副完全描述了快速排序的图片： （图片出处：http:///2001.html）
2、Java实现 package sort; /** * @ClassName: QuickSort * @Description: 快速排序 * @author qsk * @date 2014年6月21日 下午8:15:27 */ public class QuickSort { /** * @Title: sort * @Description: 用来调用迭代的子排序算法 * @param @param source * @return void * @throws */ public static void sort(int[] source) { SortUtil.outputArray(source); subSort(source, 0, source.length - 1); } /** * @Title: subSort * @Description: 子排序算法，可以继续迭代 * @param @param source * @param @param begin * @param @param end * @return void * @throws */ public static void subSort(int[] source, int begin, int end) { if (begin < end) { // 标记1从开始起,因为不包括base，而且使用前要++,所以为这个数 int sign1 = begin; // 标记2从结束起，使用前要--,所以为这个数 int sign2 = end + 1; // 假设第一个为base int base = source[begin]; while (true) { // 从左向右找第一个比base大的数，用sign1标记索引 while (source[++sign1] < base && sign1 < end) { ; } // 从右到左找第一个比base小的数，用sign2标记索引 while (source[--sign2] > base && sign2 > begin) { ; } // 若此时sign1和sign2没有碰头，就交换它们 if (sign1 < sign2) { swap(source, sign1, sign2); SortUtil.outputArray(source); // 若已经碰头，就结束循环 } else { break; } } //将base和sign2换一下，这样，已经将原数组分成2部分，中间的那个为base swap(source, begin, sign2); SortUtil.outputArray(source); subSort(source, begin, sign2 - 1); subSort(source, sign2 + 1, end); } } /** * @Title: swap * @Description: 交换数组中索引i和j处的值 * @param @param source * @param @param i * @param @param j * @return void * @throws */ public static void swap(int[] source, int i, int j) { int temp = source[i]; source[i] = source[j]; source[j] = temp; } public static void main(String[] args) { sort(SortUtil.getRandomArray()); } } 如上，注释已经非常清楚了，结果如下：
[83, 7, 11, 47, 66, 26, 85, 79, 44, 14] [83, 7, 11, 47, 66, 26, 14, 79, 44, 85] [44, 7, 11, 47, 66, 26, 14, 79, 83, 85] [44, 7, 11, 14, 66, 26, 47, 79, 83, 85] [44, 7, 11, 14, 26, 66, 47, 79, 83, 85] [26, 7, 11, 14, 44, 66, 47, 79, 83, 85] [14, 7, 11, 26, 44, 66, 47, 79, 83, 85] [11, 7, 14, 26, 44, 66, 47, 79, 83, 85] [7, 11, 14, 26, 44, 66, 47, 79, 83, 85] [7, 11, 14, 26, 44, 47, 66, 79, 83, 85]  3、时间复杂度和稳定性 快速排序是不稳定的算法，它不满足稳定算法的定义。
参考：《Java程序员的基本修养》 http://www.cnblogs.com/skywang12345/p/3596746.html http://www.cnblogs.com/skywang12345/p/3596232.html |
|
|
