概述

本文主要介绍面试常见的几种排序算法的基本思想、复杂度及其Java实现。包括冒泡、简单选择、直接插入和快速排序。

• 算法稳定性：假设在数列中存在a[i]=a[j]，若在排序之前，a[i]在a[j]前面；并且排序之后，a[i]仍然在a[j]前面。则这个排序算法是稳定的！否则不稳定！
• 内排序：所有排序操作都在内存中完成；
• 外排序：由于数据太大，因此把数据放在磁盘中，而排序通过磁盘和内存的数据传输才能进行
• 排序算法分类
  
  排序算法分类

1. 冒泡排序(Bubble Sort)

基本思想

• 冒泡排序就是把较小的元素往前调或者把较大的元素往后调。比较的是相邻的两个元素，交换也发生在这两个元素之间。所以，如果两个元素相等，是不会再交换的；如果两个相等的元素没有相邻，那么即使通过前面的两两交换把两个相邻起来，这时候也不会交换，所以相同元素的前后顺序并没有改变，所以冒泡排序是一种稳定排序算法。
• 算法原理：
  1. 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
  2. 对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
  3. 针对所有的元素重复以上的步骤，除了最后一个。
  4. 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较

算法复杂度

• 若文件初状为正序，则一趟起泡就可完成排序，排序码的比较次数为n-1，且没有记录移动，时间复杂度——O(n)
• 若文件初态为逆序，则需要n-1趟起泡，每趟进行n-i次排序码的比较，且每次比较都移动三次，比较和移动次数均达到最大值——O(n2)
• 平均时间复杂度——O(n2)

算法实现(Java)

 /**
     * 冒泡排序
     * @param arr
     */
    public static void bubbleSort(int[] arr){
        for (int i = 0; i < arr.length - 1; i++) {
            for (int j = 0; j < arr.length - 1 - i; j++) {
                if (arr[j] > arr[j+1]){ //相邻元素两两比较
                    int temp = arr[j]; //元素交换
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                }
            }
        }
    }

2. 简单选择排序(Simple Selection Sort)

基本思想

+每一趟从待排序的数据元素中选出最小（最大）的元素，顺序放在待排序的数列最前，直到全部待排序的数据元素全部排完。属于不稳定排序。

• 示例
  
  图片.png

算法复杂度

最佳情况：T(n) = O(n2) 最差情况：T(n) = O(n2) 平均情况：T(n) = O(n2)

算法实现(Java)

/**
     * 选择排序
     * @param arr
     */
    public static void selectSort(int[] arr){
        for (int i = 0; i < arr.length; i++) {
            for (int j = i+1; j < arr.length; j++) {
                if (arr[i] > arr[j]) {
                    int temp = arr[i];
                    arr[i] = arr[j];
                    arr[j] = temp;
                }
            }
        }
    }

3. 直接插入排序(Straight Insertion Sort)

基本思想

• 算法原理：
  从整个待排序列中选出一个元素插入到已经有序的子序列中去，得到一个有序的、元素加一的子序列，直到整个序列的待插入元素为0，则整个序列全部有序。在实际的算法中，我们经常选择序列的第一个元素作为有序序列（因为一个元素肯定是有序的)， 我们逐渐将后面的元素插入到前面的有序序列中，直到整个序列有序。
• 算法描述
  1. 从第一个元素开始，该元素可以认为已经被排序；
  2. 取出下一个元素，在已经排序的元素序列中从后向前扫描；
  3. 如果该元素（已排序）大于新元素，将该元素移到下一位置；
  4. 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；
  5. 将新元素插入到该位置后；
  6. 重复步骤2~5.
• 稳定性：如果碰见一个和插入元素相等的，那么插入元素把想插入的元素放在相等元素的后面。所以，相等元素的前后顺序没有改变，从原无序序列出去的顺序就是排好序后的顺序，所以插入排序是稳定的。
• 示例
  
  插入排序过程描述

算法复杂度

• 假设被排序的数列中有N个数。遍历一趟的时间复杂度是O(N)，需要遍历多少次呢？N-1！因此，直接插入排序的时间复杂度是O(N2)。T(n) = O(n2)

算法实现(Java)

/**
     * 直接插入排序
     * @param arr
     */
    public static void insertSort(int[] arr){
        for (int i = 1; i < arr.length; i++) {
            int tmp = arr[i]; //设置哨兵，用于存储无序列表中取出的待插元素
            int j = i - 1;
            while (j >= 0 && arr[j] > tmp){
                arr[j + 1] = arr[j];
                j--;
            }
            arr[j + 1] = tmp;
        }
    }

4. 快速排序( Quick Sort )

基本思想

• 快速排序是对冒泡排序的一种改进。通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程递归进行，以此达到整个数据变成有序序列。
• 算法描述
  快速排序使用分治法来把一个串（list）分为两个子串（sub-lists）。具体算法描述如下：
  1. 从数列中挑出一个元素，称为 “基准”，通常选择第一个或者最后一个元素；
  2. 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
  3. 递归地(recursive)把小于基准值元素的子数列和大于基准值元素的子数列进行排序。
• 示例
  
  一趟排序的过程描述

排序全过程描述

算法复杂度

T(n) = O(nlogn) ——当n较大时使用快排比较好，当序列基本有序时用快排反而不好。

算法实现(Java)

/**
     * 快速排序---最好的情况是O(n)，最差的情况是O(n2)，平均：O(nlogn)
     *      有两种实现方式！！！！
     * @param arr
     * @param low
     * @param high
     */
    public static void quickSort(int[] arr, int low, int high){
        if (low > high) //low 和high分别为序列的第一个和最后一个元素的索引
            return;
        int start = low;
        int end = high;
        int key = arr[low]; //设定一个基准元素
        while (start < end){
            while (start < end && arr[end] >= key){
                end--;
            }
            while (start < end && arr[start] <= key){
                start++;
            }
            if (start < end){
                swap(arr, start, end);  //交换元素
            }
        }
        swap(arr, low, start);  //将基准元素插入到start==end的索引位置，至此第一趟排序过程结束
        quickSort(arr, low, end-1);
        quickSort(arr,end+1, high);
    }

总结

种一棵树最好的时间是十年前，写一段代码最好的时间是现在！写的不好，欢迎批评指正！ 后边会陆续更新其它排序算法，如 堆排序、希尔排序、归并排序等！！