八大排序算法总结

---

1. 冒泡排序

• 思想：元素两两进行比较，然后交换位置，通过两次层循环把数据排序

• 优点：数据量较小的时候，算法效率较高

• 缺点：

  1. 时间复杂度为O(n^2)，当数据量较大的时候，效率低下
  2. 可以看到，外层循环每一次结束后，实际上是将一个相对最大（最小）的数挑出来了，其他的数据虽然相对有序，但依然是无序的，需要再次比较，因此交换位置其实没有必要，我们只需要把最大（最小）值的角标记下来，当一次循环结束后，把制定位置的元素进行交换位置就可以了。这种排序算法就是选择排序；
  3. 我们可以将整个数组分成若干个小数组，对每个数组分别进行排序，然后把排好序的数组在合并起来，因为小数组的排序性能消耗较小，因此可以提高效率，这种排序算法就是快速排序，这实际上是分治思想（分而治之）；

• 使用场景：当数据的个数在[0 , 2^3]之间时，可以使用冒泡排序，因为在该种情况下，实际上进行不了几次比较；

• 注意事项：

  • 两处优化：
    • 1. 随着比较的趟数增加，数据会逐渐有序起来，而且数组后面的元素是有序的，因此这部分数据可以退出排序，因此内层循环可以通过控制要比较的元素的个数来达到这个目的，即j < array.length - 1 - i；
    • 2. 当比较的趟数还没有结束且数据已经是有序的时候，就不需要通过排序了，这个时候直接结束循环即可，那么可以通过一个标记flag来达到这个目的，如果内层循环在一次循环过程中，里面的if判断语句没有执行，就表示数据已经是有序的，因此就可以跳出循环了。

• 代码实现

    public void bubbleSort(int[] array) {
        if (array == null || array.length == 0) {
            throw new IllegalArgumentException();
        }
  
        //外层控比较的趟数
        for (int i = 0; i < array.length - 1; i++) {//有多少个元素就需要比较多少趟
            //内层控制比较的次数，每一次循环结束都会有一个最大（最小）值出现在数组的最后一个角标的位置
            //因此这个元素可以退出排序，从而减少内层循环的次数
            boolean flag = true;
            for (int j = 0; j < array.length - 1 - i; j++) {
                //从小到大排序
                if (array[j] > array[j + 1]) {
                    int temp = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = temp;
                    flag = false;
                }
            }
            //如果整个内层循环里面的比较都没有执行，就表明所有的数字就是有序的，可以不用再进行排序了，直接跳出循环
            if (flag) {
                break;
            }
        }
    }
  

---

2. 快速排序

• 思想：对冒泡排序的优化，

  • 基本思想:通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可以分别对这两部分记录继续进行排序，以达到整个序列有序。
  • 典型的分治思想，因为有递归调用，所以是二叉树的前序遍历；
  • 分治思想：将一个大的问题分解成几个小问题，然后对各个小问题各个击破，最后将所有子问题合并，最终得到母问题的解。因此递归也是分治思想。但需要注意的是，这里不是分类讨论的思想；

• 优点：数据量大且是线性结构时，效率较高；

• 缺点：

  1. 算法不稳定，有大量重复数据时，性能不好；
  2. 单向链式结构处理性能不好（一般来说，链式都不使用快速排序）；

• 使用场景：数据量大并且是线性结构（数组），当时链式结构时不要使用这种排序算法，JDK中Arrays里面的排序算法就是快速排序，Collections.sort(int[] arr)实际上调用的就是Arrays里面的排序算法。

• 实现步骤：

  1. 先进行一次快速排序，将数组分割成两部分，使得左边的数比指定位置的数小，右边的数比指定的位置的数大；
     1. 任取一个位置的元素（一般都选待排数组的第一个元素）作为枢轴，同时给待排数组的第一个元素标记为low，最后一个元素标记为high，设枢轴记录的关键字pivotKey；
     2. 将所有关键字比枢轴小的记录都安置在他的位置之前，将所有关键字比枢轴大的记录都排在他的位置之后，（由此可以将该“枢轴”记录最后所落得位置i作为分界线，使待排数组分成两个子数组）；
        • 具体做法：
          1. 首先从high所指位置起向前搜索，找到第一个关键字小于pivotKey的记录，并且和枢轴记录互相交换；
          2. 然后从low所指位置起向后搜索，找到第一个关键字大于pivotKey的记录，然后和枢轴记录互相交换；
          3. 重复第一第二步，直至low=high为止；
  2. 完成第一步后，分别对左边的数组和右边的数组递归进行排序；

• 代码实现

    public void quickSort(int[] arr, int begin, int end) {
        if (end - begin <= 0) {
            return;
        }
        //从右相左开始
        boolean isFromRight = true;
        int low = begin;
        int high = end;
        int pivotKey = arr[begin];
        //先从high开始
        L1:
        while (high > low) {
            //从右往左开始
            if (isFromRight) {
                for (int i = high; i > low; i--) {
                    //要求：pivotKey关键字右边的数都比pivotKey大
                    if (arr[i] <= pivotKey) {
                        //如果右边的比pivotKey小，就交换位置,注意这里不是交换两个元素
                        arr[low++] = arr[i];
                        high = i;
                        //交换之后，从相反的顺序开始
                        isFromRight = !isFromRight;
                        continue L1;
                    }
                }
                //只有当右边的数都比pivotKey大的时候，才会走到这里来
                high = low;
            } else {
                for (int i = low; i < high; i++) {
                    if (arr[i] >= low) {
                        arr[high--] = arr[i];
                        low = i;
                        isFromRight = !isFromRight;
                        continue L1;
                    }
                }
                low = high;
            }
        }
        //第一次快速排序结束，将最后找到的值放入中间，即pivotKey
        arr[low]=pivotKey;//因为此时low已经等于high，所以写谁都一样
  
        //对左边的数组进行排序
        quickSort(arr,begin,low-1);
        //对右边的数组进行排序
        quickSort(arr,high+1,end);
    }
  

---

3. 选择排序

• 思想

• 优点

• 缺点

• 使用场景

• 代码实现

3. 归并排序

4. 希尔排序

6. 插入排序

7. 堆排序

8. 基数排序（链式基数排序）

9. 二分查找算法