基本排序算法回顾-bubble/select/insert
没有独立的文字说明，因为是边回忆，边写，边查经典，所以所有的文字说明都在代码中。呵呵
?
package org.acooly.datastructure.sort;import org.apache.commons.lang.ArrayUtils;import org.apache.commons.lang.math.RandomUtils;/** * 排序算法回顾和学习 <br> * <li>先回忆下算法，然后根据普通逻辑思维，写my排序算法()。 * <li>翻开经典《JAVA数据结构和算法第二部》，学习经典排序算法，然后对比学习 * * @author zhangpu * */public abstract class JavaBaseSort {// { 3, 21, 46, 75, 56, 39, 7, 95, 93, 1 };public static void main(String[] args) {int dataSize = 10;int[] randomData = new int[dataSize];for (int i = 0; i < randomData.length; i++) {int member = RandomUtils.nextInt(dataSize * 10);if (!ArrayUtils.contains(randomData, member)) {randomData[i] = member;} else {i--;}}long start = 0;int[] data = randomData.clone();System.out.println("我的冒泡排序:");printArray("原始数据: ", data = new int[]{6,5,4,67,23,3,12,32,30,1});start = System.currentTimeMillis();myBubbleSort(data);System.out.println("排序时间: " + (System.currentTimeMillis() - start) + "ms");printArray("排序数据：", data);System.out.println();System.out.println("经典冒泡排序:");printArray("原始数据: ", data = randomData.clone());start = System.currentTimeMillis();bubbleSort(data);System.out.println("排序时间: " + (System.currentTimeMillis() - start) + "ms");printArray("排序数据: ", data);System.out.println();System.out.println();System.out.println("我的选择排序:");printArray("原始数据: ", data = randomData.clone());start = System.currentTimeMillis();mySelectSort(data);System.out.println("排序时间: " + (System.currentTimeMillis() - start) + "ms");printArray("排序数据: ", data);System.out.println();System.out.println("经典选择排序:");printArray("原始数据: ", data = randomData.clone());start = System.currentTimeMillis();selectSort(data);System.out.println("排序时间: " + (System.currentTimeMillis() - start) + "ms");printArray("排序数据: ", data);System.out.println();System.out.println();System.out.println("我的插入排序:");printArray("原始数据: ", data = randomData.clone());start = System.currentTimeMillis();myInsertSort(data);System.out.println("排序时间: " + (System.currentTimeMillis() - start) + "ms");printArray("排序数据: ", data);System.out.println();System.out.println("经典插入排序:");printArray("原始数据: ", data = randomData.clone());start = System.currentTimeMillis();insertSort(data);System.out.println("排序时间: " + (System.currentTimeMillis() - start) + "ms");printArray("排序数据: ", data);}/** * 我的写法 * 逐个与开始位置的比较，小的向左边沉 * @param data */public static void myBubbleSort(int[] data) {int swapCount = 0;int loopCount = 0;for (int j = 0; j < data.length - 1; j++) {for (int i = j+1; i < data.length; i++) {if (data[j] > data[i]) {swap(data, j, i);swapCount++;}loopCount++;}}System.out.println("交换次数：" + swapCount);System.out.println("比较次数：" + loopCount);}/** * JAVA数据结构和算法第二版的写法 <br> * 书中算法有小BUG，原书中out > 1,应该是大于0，或in < out修改为in <= out * * @param data */public static void bubbleSort(int[] data) {int swapCount = 0;int loopCount = 0;for (int out = data.length - 1; out > 0; out--) {for (int in = 0; in < out; in++) {if (data[in] > data[in + 1]) {swap(data, in, in + 1);swapCount++;}loopCount++;}}System.out.println("交换次数：" + swapCount);System.out.println("比较次数：" + loopCount);}/** * 我的选择排序 <br> * <li>还是经典的厉害，虽然效果一样，思路一样，但是我就是多了个min变量来保存每次循环的最小值。实际这个值对排序是无意义的。 * <li>但是，我没有想到，经过测试（10000个数字），我这个写法比经典的要快进40%左右。可能是，经典算法每次要定位然后在比较，我少了定位这一步。 * * <li>选择排序与冒泡比较来说，主要是少了交换次数，控制在N-1交换，比较次数一样。算法效率有提升(10000个数排序测试)。 <br> * <li>如果交换时间比比较时间更耗时，那么选择排序会比冒泡优越很多。 * * @param data */public static void mySelectSort(int[] data) {int swapCount = 0;int loopCount = 0;for (int i = 0; i < data.length - 1; i++) {int min = data[i];int minIndex = i;for (int j = i; j < data.length; j++) {if (min > data[j]) {min = data[j];minIndex = j;}loopCount++;}swap(data, i, minIndex);swapCount++;}System.out.println("交换次数：" + swapCount);System.out.println("比较次数：" + loopCount);}/** * 选择排序（书中经典写法） * * @param data */public static void selectSort(int[] data) {int swapCount = 0;int loopCount = 0;int out, in, min;for (out = 0; out < data.length - 1; out++) {min = out;for (in = out; in < data.length; in++) {if (data[min] > data[in]) {min = in;}loopCount++;}swap(data, out, min);swapCount++;}System.out.println("交换次数：" + swapCount);System.out.println("比较次数：" + loopCount);}/** * 我的插入排序<br> * <li>只能一个郁闷了得，我只是理解了算法的思路，写法太龌龊了。不加注释估计看不懂。</li> * <li>还是经典的看起舒服。可读性强，好理解。</li> * * <li>插入排序在原始数据完全无序的情况下比较和复杂和冒泡，选择排序无限接近O(N^2) * <li>原始数据基本有序或部分有序的情况下，因为内层循环判断会减少，所有无限接近O(N) * * @param data */public static void myInsertSort(int[] data) {int swapCount = 0;int loopCount = 0;for (int i = 1; i < data.length; i++) { // 从第2个元素开始向前比较int flag = data[i]; // 开始比较的基准元素int targetIndex = 0; // 默认没有找到插入位置，则插入到第1个// 从开始比较的元素前面一个开始比较，找到比基准元素小的元素，// 以该元素的前面个位置作为插入点，其它元素依次后移。// 如果查到到起点都没有比基准元素小的值，则插入到第1个元素的为位置for (int j = i - 1; j >= 0; j--) {if (flag >= data[j]) {// 找到比基准元素小的值，保持插入点，退出循环targetIndex = j + 1;break;} else {// 没有找到比基准元素小的值，则向后移动data[j + 1] = data[j];swapCount++;}loopCount++;}// 插入data[targetIndex] = flag;swapCount++;}System.out.println("交换次数：" + swapCount);System.out.println("比较次数：" + loopCount);}/** * 经典插入算法 * * @param data */public static void insertSort(int[] data) {int swapCount = 0;int loopCount = 0;for (int out = 1; out < data.length; out++) {int flag = data[out];int in = out;while (in > 0 && data[in - 1] >= flag) {data[in] = data[in - 1];in--;loopCount++;swapCount++;}data[in] = flag;swapCount++;}System.out.println("交换次数：" + swapCount);System.out.println("比较次数：" + loopCount);}/** * 交换数组中两个元素的值 * * @param data * @param i * @param j */private static void swap(int[] data, int i, int j) {int temp = data[i];data[i] = data[j];data[j] = temp;}private static void printArray(String message, int[] data) {System.out.println(message + ArrayUtils.toString(data));}}??