===============
== 大程熙 ==
===============
一个小学生

算法之快速排序学习

快速排序算法重新学习。

交换排序算法有以下几种:

  • 冒泡排序
  • 快速排序

快速排序算法

快速排序算法可以减少冒泡排序中重复移动数据的问题。算法描述如下:在数据序列中选取一个元素作为基准值(可以选择任意一个元素),然后开始从序列的两端开始交替和基准值进行比较,如果比基准值小,则将元素放到序列的左边;如果比基准值大,则将元素放到序列的右边。最后中间的元素就是基准值的位置。以基准值为分隔点,左右两边的两个子序列,左边的都比基准值小,右边的都比基准值大。在分别对两个子序列进行快速排序,一直到子序列长度为1,排序完成。

快速排序代码示例

/**
 * 快速排序
 * 赋值填充方式,一端挖坑一端填充
 * 从右边找比基准小的元素,找到后将该元素填到基准元素所在位置,
 * 然后从左边找比基准大的元素,找到后填充到刚才的比基准元素小的那个元素位置上
 * @param source 待排序数组
 */
public void quickSort(Integer[] source) {
    sort(source, 0, source.length - 1);
}

private void sort(Integer[] source, int begin, int end) {
    if (begin < end) {
        // 基准值
        Integer pivot = source[begin];
        // 序列左边
        int i = begin;
        // 序列右边
        int j = end;
        while (i < j) {
            // 从右边开始找,找比基准小的元素
            while (i < j && source[j] > pivot) {
                j--;
            }

            if (i < j) {
                // 将比基准元素小的这个元素填充到左边空缺位置(基准元素位置或者已经交换过元素的位置)
                source[i] = source[j];
                i++;
            }

            // 右边找到比基准小的元素并交换后,开始从左到右找比基准大的元素
            while (i < j && source[i] < pivot) {
                i++;
            }

            if (i < j) {
                // 比基准元素大的元素,放到右边交换过元素的位置
                source[j] = source[i];
                j--;
            }
        }

        // i == j表示i、j相交,此时基准元素的位置就是这个相交位置
        source[i] = pivot;
        // 比基准元素小的序列,左边序列,进行快排
        sort(source, begin, i - 1);
        // 比基准元素大的序列,右边序列,进行快排
        sort(source, i + 1, end);
    }
}

public static void main(String[] args) {
    Integer[] array = new Integer[] {38, 55, 65, 97, 27, 76, 27, 13, 19};
    System.out.println("before: " + Arrays.asList(array));
    new QuickSort().quickSort(array);
    System.out.println("after: " + Arrays.asList(array));
}

快速排序算法分析

时间复杂度

  • 最好情况,每趟排序将序列分为两个长度相近的子序列,时间复杂度$O(n \times log_{2}n)$
  • 最坏情况,每趟序列将序列分为两个长度差异很大的子序列,时间复杂度$O(n^2)$

空间复杂度

算法中执行中需要递归,需要花费一定空间,使用栈来保存参数,栈所占用空间与递归调用次数有关,空间复杂度介于$O( log_{2}n)$和O(n)之间

算法的稳定性

排序知乎,相同值的元素相对位置可能会改变,快速排序算法是不稳定的。

适用场景

  • 当序列中数据较多并且随机排列时,快速排序效果是很好的。
  • 当序列中数据比较少或者基准值选择不合适的时候,排序较慢。

快速排序算法的各种实方式

快速排序算法有多种实现方法,上面示例的是一种,赋值填充方式。还有其他若干实现方式以及更先进的双轴快排算法。

赋值填充方式

赋值填充方式,是一端进行挖坑另外一端数据来填充该坑,两端交替进行交换数据。算法描述如下:

  • 选择基准值,一般选择左边第一个元素作为基准值。
  • 先从最右边开始,往左边找比基准值小的元素,如果找到了,将该处元素交换到左边空缺位置(基准元素位置或者是已经交换过元素的空位)
  • 接着从左边开始,往右边找比基准值大的元素,如果找到了,将该处元素交换到右边空缺位置
  • 左右两边相交的位置,就是基准值应该放的位置。

示例代码如下:

/**
 * 快速排序
 * 赋值填充方式,一端挖坑一端填充
 * 从右边找比基准小的元素,找到后将该元素填到基准元素所在位置,
 * 然后从左边找比基准大的元素,找到后填充到刚才的比基准元素小的那个元素位置上
 * @param source 待排序数组
 */
public void quickSort(Integer[] source) {
    sort(source, 0, source.length - 1);
}

private void sort(Integer[] source, int begin, int end) {
    if (begin < end) {
        // 基准值
        Integer pivot = source[begin];
        // 序列左边
        int i = begin;
        // 序列右边
        int j = end;
        while (i < j) {
            // 从右边开始找,找比基准小的元素
            while (i < j && source[j] > pivot) {
                j--;
            }

            if (i < j) {
                // 将比基准元素小的这个元素填充到左边空缺位置(基准元素位置或者已经交换过元素的位置)
                source[i] = source[j];
                i++;
            }

            // 右边找到比基准小的元素并交换后,开始从左到右找比基准大的元素
            while (i < j && source[i] < pivot) {
                i++;
            }

            if (i < j) {
                // 比基准元素大的元素,放到右边交换过元素的位置
                source[j] = source[i];
                j--;
            }
        }

        // i == j表示i、j相交,此时基准元素的位置就是这个相交位置
        source[i] = pivot;
        // 比基准元素小的序列,左边序列,进行快排
        sort(source, begin, i - 1);
        // 比基准元素大的序列,右边序列,进行快排
        sort(source, i + 1, end);
    }
}

public static void main(String[] args) {
    Integer[] array = new Integer[] {38, 55, 65, 97, 27, 76, 27, 13, 19};
    System.out.println("before: " + Arrays.asList(array));
    new QuickSort().quickSort(array);
    System.out.println("after: " + Arrays.asList(array));
}

两端扫描交换方式

两端扫描交换方式是左右两边分别扫描并和基准元素进行比较,然后将这两个元素位置进行交换。算法描述如下:

  • 选择一个基准值,一般是左边第一个元素。
  • 从左边开始,往右找到一个比基准大的元素,接着从右边开始,往左找到一个比基准小或者等于基准的元素。
  • 找到了两个元素后,将两个元素位置交换。
  • 如果左右两个指针交错了,需要将基准值交换到中心位置。
/**
 * 快速排序
 * 两端扫描交换方式
 * 从左边开始扫描,找到一个比基准大的元素,接着从右边开始扫描,找到一个比基准小的元素,
 * 将这两个元素进行交换。
 * @param source 待排序数组
 */
public void quickSort(Integer[] source) {
    sort(source, 0, source.length - 1);
}

private void sort(Integer[] source, int begin, int end) {
    if (begin < end) {
        // 基准值
        Integer pivot = source[begin];
        // 序列左边
        int i = begin + 1;
        // 序列右边
        int j = end;
        while (i <= j) {
            // 从左边开始找,找比基准大的元素
            while (i <= j && source[i] < pivot) {
                i++;
            }

            // 从左边找到了比基准大的元素之后,开始从右到左找比基准小或相等的元素
            while (i <= j && source[j] >= pivot) {
                j--;
            }

            // 此时在左边找到了比基准大的元素,在右边找到了比基准小的元素
            if (i <= j) {
                // 交换两个元素位置
                Integer temp = source[j];
                source[j] = source[i];
                source[i] = temp;
            }
        }

        // i < j,说明交错了,将基准交换到中心位置
        Integer temp = source[begin];
        source[begin] = source[j];
        source[j] = temp;

        // 比基准元素小的序列,左边序列,进行快排
        sort(source, begin, j - 1);
        // 比基准元素大的序列,右边序列,进行快排
        sort(source, j + 1, end);
    }
}

public static void main(String[] args) {
    Integer[] array = new Integer[] {38, 55, 65, 97, 27, 76, 27, 13, 19};
    System.out.println("before: " + Arrays.asList(array));
    new QuickSort().quickSort(array);
    System.out.println("after: " + Arrays.asList(array));
}

单向扫描划分

单向扫描划分是将序列进行划分成多个子序列,并从一端进行扫描即可完成排序。算法描述如下:

  • 选择基准值,一般选择最左边的元素作为基准值。
  • 将序列划分为:基准 + 比基准小的序列 + 比基准大的序列 + 待排序序列
  • 从待排序序列最左边开始往右遍历,如果找到了比基准大的元素,不做操作继续遍历;
  • 如果找到了比基准小的元素,需要将此元素和比基准大的序列的最左边元素交换。
  • 扫描完后序列划分变为:基准 + 比基准小的序列 + 比基准大的序列,此时需要将基准元素和比基准小的序列的最右端进行交换,让基准元素处于中间。

代码示例如下:

/**
 * 快速排序
 * 单向扫描划分
 * 将序列分成:基准 + 比基准小的序列 + 比基准大的序列 + 待排序列
 * 扫描比基准大的序列,如果元素比基准小,则将这个元素和比基准大的序列的最左端交换,
 * 并让这个最左端元素变成比基准小的序列的最右端
 * @param source 待排序数组
 */
public void quickSort(Integer[] source) {
    sort(source, 0, source.length - 1);
}

private void sort(Integer[] source, int begin, int end) {
    if (begin < end) {
        // 基准值
        Integer pivot = source[begin];
        // 序列左边
        int i = begin;
        // 序列右边
        int j = begin + 1;

        while (j <= end) {
            // 右边序列元素比基准小,需要将这个元素和右边序列最左边元素进行交换,
            // 并将右边元素最左边元素这个位置变为左边序列的元素
            if (source[j] < pivot) {
                i++;
                Integer temp = source[j];
                source[j] = source[i];
                source[i] = temp;
            }
            j++;
        }

        // 扫描完后,现在变成了:基准元素+比基准小的序列+比基准大的序列
        // 此时需要把基准元素和比基准小的序列的最右端元素进行交换,让基准元素变成中间
        source[begin] = source[i];
        source[i] = pivot;

        // 比基准元素小的序列,左边序列,进行快排
        sort(source, begin, i - 1);
        // 比基准元素大的序列,右边序列,进行快排
        sort(source, i + 1, end);
    }
}

public static void main(String[] args) {
    Integer[] array = new Integer[] {38, 55, 65, 97, 27, 76, 27, 13, 19};
    System.out.println("before: " + Arrays.asList(array));
    new QuickSort().quickSort(array);
    System.out.println("after: " + Arrays.asList(array));
}

三分单向扫描

三分单向扫描和单向划分扫描类似,只不过序列划分不太一样,增加了一个等于基准值的序列。算法描述如下:

  • 选择基准值,一般是选择左边第一个元素。
  • 将序列划分为:比基准小的序列 + 等于基准的序列 + 待排序序列 + 比基准大的序列
  • 从左向右遍历元素,找到比基准小的元素,和等于基准元素的序列中的最左边元素进行交换。
  • 如果找到比基准大的元素,和待排序序列的最右边元素进行交换。
  • 如果找到和基准元素相等的,不做操作继续遍历。

代码示例如下:

/**
 * 快速排序
 * 三分单向扫描
 * 将序列分为:小于基准序列 + 等于基准序列 + 待排序序列 + 大于基准序列
 * 需要三个指针,i指向等于基准序列的最左边元素,k指向待排序序列的最左边,j指向待排序序列的最右边
 * @param source 待排序数组
 */
public void quickSort(Integer[] source) {
    sort(source, 0, source.length - 1);
}

private void sort(Integer[] source, int begin, int end) {
    if (begin < end) {
        Integer pivot = source[begin];

        int i = begin;
        int j = end;
        int k = begin + 1;
        while (k <= j) {
            // 比基准小
            if (source[k] < pivot) {
                swap(source, i, k);
                i++;
                k++;
            }
            // 比基准大
            else if (source[k] > pivot) {
                swap(source, k, j);
                j--;
            }
            // 等于基准
            else {
                k++;
            }
        }

        // 小于基准的序列,快速排序
        sort(source, begin, i - 1);

        // 大于基准的序列,快速排序
        sort(source, j + 1, end);
    }
}

private void swap(Integer[] source, int i, int j) {
    Integer temp = source[i];
    source[i] = source[j];
    source[j] = temp;
}

public static void main(String[] args) {
    Integer[] array = new Integer[] {38, 55, 65, 97, 27, 76, 27, 13, 19};
    System.out.println("before: " + Arrays.asList(array));
    new QuickSort().quickSort(array);
    System.out.println("after: " + Arrays.asList(array));
}

三分双向扫描

三分双向扫描和三分单向扫描划分一样,只是变成了两端进行扫描。算法描述如下:

  • 选取基准值,一般为左边第一个元素。
  • 将序列划分为:比基准小的序列 + 等于基准的序列 + 待排序序列 + 比基准大的序列
  • 从左到右进行遍历,如果找到比基准小的元素,和等于基准的序列的最左边元素交换。
  • 如果找到比基准大的元素,需要从待排序的序列的右边开始遍历找比基准小或者和基准相等的元素。如果找到比基准小的,需要将这个元素进行两次交换;如果找到和基准相等的元素,直接交换。
  • 如果找到等于基准的元素,不做处理继续遍历。

代码示例如下:

/**
 * 快速排序
 * 三分双向扫描
 * 将序列分为:小于基准序列 + 等于基准序列 + 待排序序列 + 大于基准序列
 * 需要三个指针,i指向等于基准序列的最左边元素,k指向待排序序列的最左边,j指向待排序序列的最右边
 * @param source 待排序数组
 */
public void quickSort(Integer[] source) {
    sort(source, 0, source.length - 1);
}

private void sort(Integer[] source, int begin, int end) {
    if (begin < end) {
        Integer pivot = source[begin];

        int i = begin;
        int j = end;
        int k = begin + 1;
        outer: while (k <= j) {
            // 比基准小
            if (source[k] < pivot) {
                swap(source, i, k);
                i++;
                k++;
            }
            // 比基准大
            else if (source[k] > pivot) {
                // j向左扫描,找到比pivot小的或者等于pivot的元素
                while (source[j] > pivot) {
                    j--;
                    // 说明待排元素全部比pivot大
                    if (j < k) {
                        break outer;
                    }
                }

                // 待排序中找到了比pivot的元素
                if (source[j] < pivot) {
                    // 将这个元素和k交换
                    swap(source, j, k);
                    // k当前元素比pivot小,和i进行交换
                    swap(source, i, k);
                    i++;
                }
                // 和pivot相等,直接和k交换
                else {
                    swap(source, j, k);
                }

                k++;
                j--;
            }
            // 等于基准
            else {
                k++;
            }
        }

        // 小于基准的序列,快速排序
        sort(source, begin, i - 1);

        // 大于基准的序列,快速排序
        sort(source, j + 1, end);
    }
}

private void swap(Integer[] source, int i, int j) {
    Integer temp = source[i];
    source[i] = source[j];
    source[j] = temp;
}

public static void main(String[] args) {
    Integer[] array = new Integer[] {38, 55, 65, 97, 27, 76, 27, 13, 19};
    System.out.println("before: " + Arrays.asList(array));
    new QuickSort().quickSort(array);
    System.out.println("after: " + Arrays.asList(array));
}

双轴快排算法介绍

双轴快排是对快排的改进,和三分单向扫描以及三分双向扫描类似,也需要将序列分成若干段。双轴快排需要取两个基准点,假设基准点为pivot1和pivot2,并且pivot2大于等于pivot1,双轴快排分为:pivot1 + 小于pivot1的序列 + 大于等于pivot1并且小于pivot2的序列 + 待排元素序列 + 大于pivot2的序列 + pivot2。双轴快排是双向扫描,算法描述如下:

  • 确定两个基准点,一般选择头尾两个元素,pivot1和pivot2,确保pivot2大于等于pivot1
  • 先从左到右扫描待排序元素,如果元素比pivot1小,将该元素和大于等于pivot1并且小于pivot2的序列中的最左边元素交换;如果元素小于等于pivot2,则不作处理,继续扫描。
  • 如果元素大于pivot2,则从右向左扫描待排序元素,如果找到了待排序元素小于基准1,则和左边大于pivot2的元素交换,然后再和大于等于pivot1并且小于pivot2的序列中的最左边元素交换;如果大于等于pivot1或者小于等于pivot2,则直接和大于pivot2的元素进行交换。
  • 遍历完后,将pivot1和小于pivot1序列最右端元素进行交换,将pivot2和大于pivot2序列最左端元素进行交换。
  • 在分别将三个序列递归进行双轴快排。

双轴快排代码示例

/**
     * 快速排序
     * 双轴快排
     * 取两个基准:基准1 pivot1和基准2 pivot2,并且pivot1 <= pivot2
     * 将序列分为:基准1 + 小于基准1的序列 + 大于等于基准1并且小于等于基准2的序列 + 待排序序列 + 大于基准2的序列 + 基准2
     * @param source 待排序数组
     */
    public void quickSort(Integer[] source) {
        sort(source, 0, source.length - 1);
    }

    private void sort(Integer[] source, int begin, int end) {
        if (begin < end) {
            // 确保基准1比基准2小
            if (source[begin] > source[end]) {
                swap(source, begin, end);
            }

            Integer pivot1 = source[begin];
            Integer pivot2 = source[end];

            int i = begin;
            int j = end;
            int k = begin + 1;
            outer: while (k < j) {
                // 比基准1小
                if (source[k] < pivot1) {
                    i++;
                    // 将k位置元素交换到小于基准1的序列中
                    swap(source, i, k);
                    k++;
                }
                // 小于等于基准2
                else if (source[k] <= pivot2) {
                    k++;
                }
                // 大于基准2
                else {
                    // 从右向左扫描待排序元素
                    while (source[--j] > pivot2) {
                        if (j <= k) {
                            break outer;
                        }
                    }

                    // 小于基准1
                    if (source[j] < pivot1) {
                        swap(source, j, k);
                        i++;
                        swap(source, i, k);
                    }
                    // 大于等于基准1或者小于等于基准2
                    else {
                        swap(source, j, k);
                    }

                    k++;
                }
            }

            // 将基准1和基准2交换到中间
            swap(source, begin, i);
            swap(source, end, j);

            // 小于基准1的序列,快速排序
            sort(source, begin, i - 1);

            // 大于等于基准1,小于等于基准2,快速排序
            sort(source, i + 1, j - 1);

            // 大于基准2的序列,快速排序
            sort(source, j + 1, end);
        }
    }

    private void swap(Integer[] source, int i, int j) {
        Integer temp = source[i];
        source[i] = source[j];
        source[j] = temp;
    }

    public static void main(String[] args) {
        Integer[] array = new Integer[] {38, 55, 65, 97, 27, 76, 27, 13, 19};
        System.out.println("before: " + Arrays.asList(array));
        new QuickSort().quickSort(array);
        System.out.println("after: " + Arrays.asList(array));
    }

双轴快排更好的原因

很多文章说双轴快排更好的原因是因为考虑了CPU和内存速度不匹配的原因,就是内存墙的问题。可以参考这篇文章说的:https://www.sakuratears.top/blog/%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95%EF%BC%88%E4%B8%83%EF%BC%89-%E5%8F%8C%E8%BD%B4%E5%BF%AB%E9%80%9F%E6%8E%92%E5%BA%8F.html

有点不太明白,个人猜测理解应该是双轴快排能更好地利用到CPU高速缓存,不知道对不对。

参考内容