排序算法：冒泡排序、插入排序、选择排序、快速排序对比

对大小是 60000 的数组进行排序

执行结果（毫秒）：

        /*
         * Creating arrays uses time: 16
         * 冒泡排序： 4651
         * 插入排序： 1465
         * 选择排序： 1399
         * 快速排序： 14
         */
      

代码：

package test;

public class T{
    public static void main(String[] args) {

        long start = System.currentTimeMillis();
        int[] arr1 = createArray();
        int[] arr2 = createArray();
        int[] arr3 = createArray();
        int[] arr4 = createArray();
        
        quick_sort qs = new quick_sort();
        long end = System.currentTimeMillis();
        System.out.println("Creating arrays uses time: " + (end - start));

        start = System.currentTimeMillis();
        bubble_sort(arr1);
        end = System.currentTimeMillis();
        System.out.println("冒泡排序： " + (end - start));

        start = System.currentTimeMillis();
        insertion_sort(arr3);
        end = System.currentTimeMillis();
        System.out.println("插入排序： " + (end - start));

        start = System.currentTimeMillis();
        selection_sort(arr2);
        end = System.currentTimeMillis();
        System.out.println("选择排序： " + (end - start));
        
        
        start = System.currentTimeMillis();
        qs.sort(arr4);
        end = System.currentTimeMillis();
        System.out.println("快速排序： " + (end - start));
        
        /*
         * Creating arrays uses time: 16
         * 冒泡排序： 4651
         * 插入排序： 1465
         * 选择排序： 1399
         * 快速排序： 14
         */
       

    }

    public static int[] createArray() {
        int length = 60000;
        int[] arr = new int[length];

        int i = 0;
        for (; i < length; i++) {
            arr[i] = (int) (Math.random() * length);
        }
        return arr;
    }

    /**
     * 冒泡排序：
     * 
     *  一、 重复的遍历要排序的序列 n 次。（n为数组的长度）
     *  二、 对于每次遍历：
     *      2.1  要遍历的元素个数减 1 （因为尾部的已经排好）
     *      2.2  每次都要比较两个元素。如果符合条件，则交换位置。
     */
    public static void bubble_sort(int[] arr) {
        int i, j, temp, len = arr.length;
        // 1. 遍历 i 次
        for (i = 0; i < len - 1; i++)
            // 2. 对于 0 到 len-i 中的元素
            for (j = 0; j < len - 1 - i; j++)
                // 3. 如果前面的大，则交换（冒泡）到后面
                if (arr[j] > arr[j + 1]) {
                    temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
    }

    /**
     * 插入排序：
     * 
     *  一、从数组的第1个元素开始遍历至第n个。（n为数组的长度）
     *  二、对于每一个遍历到的元素：
     *      2.1 向前倒着找（已经排好序的）自己的位置。
     *      2.2 如果不符合条件，则前面的元素向后移动，与之交互位置。
     *          直至条件符合。
     */
    public static void insertion_sort(int[] arr) {
        for (int i = 0; i < arr.length - 1; i++) { // 1. 遍历每一个 i
            for (int j = i + 1; j > 0; j--) { // 2. 从 0-j 是已经排序好的。
                if (arr[j - 1] <= arr[j])
                    break; // 位置已经找到，不用再比了。继续下一个 i
                // 对于每一个 i，向后移动每一个j，腾出空间。直至找到 i 的位置。
                int temp = arr[j];
                arr[j] = arr[j - 1];
                arr[j - 1] = temp;
            }
        }
    }

    /**
     * 选择排序:
     * 
     *  一、遍历从 0 到 n 个位置。（n为数组的长度）
     *  二、对于每一个位置：
     *      2.1 从剩余的数中找到符合条件的，放到该位置上。
     */
    public static void selection_sort(int[] arr) {
        int i, j, min, temp, len = arr.length;
        // 1. 遍历每一个 位置 i
        for (i = 0; i < len - 1; i++) {
            min = i;
            for (j = i + 1; j < len; j++)
                // 2. 遍历每一个 j，找出最小的
                if (arr[min] > arr[j])
                    min = j;
            // 3. 把 找出的值放在 i 的位置
            temp = arr[min];
            arr[min] = arr[i];
            arr[i] = temp;
        }
    }

}


/** 
 * 快速排序（Quicksort）: 
 * 又称为划分交换排序（partition-exchange sort） 
 *  
 * 快速排序使用分治法（Divide and conquer）策略來把一个序列（list）分为两个子序列（sub-lists）。 
 * 步骤： 
 *      1. 从序列中选一个数作为基准（pivot）。【本例中使用最后一个元素】
 *      2. 分别从左右两侧开始向中间推进。
 *         左侧：从左至右前进，直至找到大于等于基准的数。
 *         右侧：从右至左前进，直至找到小于基准的数。
 *         左右两个数调换位置。
 *      3. 重复2的过程，直至左右相碰，全部遍历完一遍。
 *         此时在相碰处：
 *         左侧：所有的数都小于基准小。
 *         右侧：所有的数都大于或等于基准。
 *         中间：基准元素的位置已确定了。
 *      4. 把相碰处分为两个子序列，递归的调用2，3步骤。
 */  
class quick_sort {
    int[] arr;  
  
    private void swap(int x, int y) {
        int temp = arr[x];  
        arr[x] = arr[y];  
        arr[y] = temp;  
    }  
  
    private void quick_sort_recursive(int start, int end) {
        if (start >= end)  return;            
        int mid = arr[end];  
        int left = start, right = end - 1;
        
        //1. left 区先和 right 区比
        while (left < right) {  
            while (arr[left] < mid && left < right)    // 找到left中比mid大的或相等的。
                left++;  
            while (arr[right] >= mid && left < right)  // 只找到right中比mid小的。
                right--;
            if(left < right) swap(left, right);// 将2个的位置调换。
        }
        
        //2. left 区再和 mid 比
        // 如果左侧最右边（右侧最左边）的值比mid大，
        // 则mid要归小值区。  left的值不加。
        // 即保证：left 区的值都是小的。
        if (arr[left] >= arr[end])
            swap(left, end);
        else
            left++;
        
        // left 此时为中间值，位置已被最终确定。无需包含 left。
        // 故从 left-1, left + 1 开始。
        quick_sort_recursive(start, left - 1);  
        quick_sort_recursive(left + 1, end);
    }  
  
    public void sort(int[] arrin) {
        arr = arrin;  
        quick_sort_recursive(0, arr.length - 1);  
    }  
}

另附：快速排序执行过程分析

package test;

public class T {
    
    public static void main(String[] args) {
        
        // 快速排序使用最后一个元素作为基准，
        // 对于最坏的情况：
        
        int[] arr = new int[] {2,3,4,5,6,7,1};
        
        quick_sort qs = new quick_sort();
        
        qs.sort(arr);
        
        /*
         * 
         *  1 -  [ 1, 3, 4, 5, 6, 7, 2 ]
         *  2 -  [ 1, 2, 4, 5, 6, 7, 3 ]
         *  3 -  [ 1, 2, 3, 5, 6, 7, 4 ]
         *  4 -  [ 1, 2, 3, 4, 6, 7, 5 ]
         *  5 -  [ 1, 2, 3, 4, 5, 7, 6 ]
         *  6 -  [ 1, 2, 3, 4, 5, 6, 7 ]
         */
      
    }
    
    
    
   static class quick_sort {
        int[] arr;
        
        private void printArray(){
            String str = "[ ";
            int i = 0;
            for (;i<arr.length;i++){
                str += arr[i] + ", ";
            }
            str = str.substring(0, str.length() - 2) + " ]";
            System.out.println(str);
        }

        private void swap(int x, int y) {
            int temp = arr[x];
            arr[x] = arr[y];
            arr[y] = temp;
        }

        private void quick_sort_recursive(int start, int end) {
            if (start >= end)
                return;
            int mid = arr[end];
            int left = start, right = end - 1;
            while (left < right) {
                while (arr[left] < mid && left < right)
                    left++;
                while (arr[right] >= mid && left < right)
                    right--;
                swap(left, right);
            }
            if (arr[left] >= arr[end])
                swap(left, end);
            else
                left++;
            
            printArray();
            
            quick_sort_recursive(start, left - 1);
            quick_sort_recursive(left + 1, end);
        }

        public void sort(int[] arrin) {
            arr = arrin;
            quick_sort_recursive(0, arr.length - 1);
        }
    }

}

引用：

https://zh.wikipedia.org/wiki/冒泡排序
https://zh.wikipedia.org/wiki/插入排序
https://zh.wikipedia.org/wiki/选择排序
https://zh.wikipedia.org/wiki/快速排序



-
转载请注明
原文出处： http://lixh1986.iteye.com/blog/2322727















-