排序算法

排序，给定一组数，按照指定顺序进行排列的过程。
排序算法有很多，一般可以分为二类：

• 内部排序，即使用内存

  • 插入排序：直接插入排序、希尔排序
  • 选择排序：简单选择排序、堆排序
  • 交换排序：冒泡排序、快速排序
  • 归并排序
  • 基数排序
• 外部排序，使用内存+外部存储

各个算法时间复杂度比较：

术语说明：

• 稳定：如果a原来就在b前面，而a = b，完成排序后a仍在b的前面。
• 不稳定：如果a原来就在b前面，而a = b，完成排序后a可能在b的后面。
• 内排序（In-place）：所有操作都在内存中完成。
• 外排序（Out-place）：由于数据太大，因而将数据放在磁盘中，排序操作通过外部存储和内存的数据传输才能进行。
• 时间复杂度：算法执行所耗费的时间。
• 空间复杂度：算法运行所需内存大小。

冒泡排序

冒泡排序思想：
通过对待排序序列从前向后，依次比较相邻的元素，逆序则交换，使得值较大的元素逐渐从前移到后部，类似冒泡从底部逐渐冒上来（排好序）。

冒泡排序代码如下：

/**
 * 冒泡排序
 * <pre>
 * 重复地遍历要排序的数列，一次比较两个元素，如果他们的顺序逆序(即排序标准)就把他们交换过来。
 * 走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。
 * </pre>
 * @author jyoryo
 */
public class BubbleSort {
    public static void main(String[] args) {
        int size = 100000;
        int array[] = new int[size];
        for(int i = 0; i < size; i++) {
            array[i] = (int)(Math.random() * size * 1000);
        }
        // System.out.println(Arrays.toString(array));
        long current = System.nanoTime();

        // bubbleSort(array);
        bubbleSort2(array);
        
        System.out.println(System.nanoTime() - current);
        // System.out.println(Arrays.toString(array));
    }
    
    // 冒泡排序
    public static void bubbleSort(int[] array) {
        int length = array.length;
        for(int i = 0; i < length; i ++) {
            for(int j = 0; j < (length - i - 1); j ++) {
                if(array[j] > array[j + 1]) {
                    int tmp = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = tmp;
                }
            }
        }
    }
    
    // 冒泡排序（优化过）
    public static void bubbleSort2(int [] array) {
        int length = array.length;
        boolean flag = false;    //标志是否经过交换
        for(int i = 0;  i < length; i++) {
            for(int j = 0; j < (length - i - 1); j++) {
                if(array[j] > array[j + 1]) {
                    flag = true;
                    int tmp = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = tmp;
                }
            }
            // 在一趟排序中未发生交换
            if(!flag) {
                break ;
            }
            // 重置标志
            flag = false;
        }
    }
}

- 阅读剩余部分 -