当前位置：首页 > news >正文

数据结构与算法(java版)第二季 - 4 快速、希尔排序(未完)

news 来源：原创 2024/11/10 15:24:26

快速排序（Quick Sort）

希尔排序（Shell Sort）

快速排序（Quick Sort）

◼ 1960年由查尔斯·安东尼·理查德·霍尔（Charles Antony Richard Hoare，缩写为C. A. R. Hoare）提出

 昵称为东尼·霍尔（Tony Hoare）

快速排序 – 执行流程

①从序列中选择一个轴点元素（pivot）
✓ 假设每次选择0位置的元素为轴点元素

② 利用 pivot 将序列分割成 2 个子序列

✓ 将小于 pivot 的元素放在pivot前面（左侧）

✓ 将大于 pivot 的元素放在pivot后面（右侧）

✓ 等于pivot的元素放哪边都可以

③ 对子序列进行 ① ② 操作

✓ 直到不能再分割（子序列中只剩下1个元素）

这里快速排序的本质是逐渐将每一个元素转换为轴点元素坐标。就是进行一个逐渐递归的过程，每个元素成为轴点的过程都是差不多的。一般的begin和end是左闭右开的。

上述的扫描过程：

①首先将6a进行一个备份；
②首先将end-1，扫描到7，其大于6，将end--；
③发现end的这个位置的数字是比原来的6a小的，将5覆盖掉原来的begin位置，在这个时候将begin进行一个++操作；
依次进行上述的操作，注意：这里我们将两个相同的元素之中，将一样的元素看成是比原来的元素小的，为什么这样做呢？后面会说到的。

从左往右进行扫描，如果要是扫描到比轴点坐标小于等于的，则不发生改变，要是扫描到比轴点大，那么就是会发生一个位置的调换。同理，从右往左进行相应的扫描。

代码如下所示：

package com.mj.sort.cmp;

import com.mj.sort.Sort;

public class QuickSort1<T extends Comparable<T>> extends Sort<T> {
    @Override
    protected void sort() {
        sort(0, array.length);
    }

    /*
    对于[begin,end)之中的元素进行相应的
     */
    private void sort(int begin, int end) {
        if (end - begin < 2) return;

        // 确定轴点位置 O(n)
        int mid = pivotIndex(begin, end);

        // 对子序列进行快速排序
        sort(begin, mid);
        sort(mid + 1, end);
    }

    /**
     * 构造出 [begin, end) 范围的轴点元素
     *
     * @return 轴点元素的最终位置
     */
    private int pivotIndex(int begin, int end) {
        // 随机选择一个元素跟begin位置进行交换
        swap(begin, begin + (int) (Math.random() * (end - begin)));

        // 备份begin位置的元素---这里就是在图示之中的6a
        T pivot = array[begin];

        // end指向最后一个元素---将最后的一个位置进行--操作
        end--;

        //下面是两种操作,分情况进行讨论
        while (begin < end) {
            while (begin < end) {
                if (cmp(pivot, array[end]) < 0) { // 右边元素 > 轴点元素
                    end--;
                } else { // 右边元素 <= 轴点元素 右边的元素是小于或者等于轴点的大小的时候,将右边的值之间进行覆盖掉左边的begin位置的值
                    array[begin++] = array[end];
                    break;
                }
            }
            //下面是进行掉头的一段代码,使用的是进行掉头的方式.
            while (begin < end) {
                if (cmp(pivot, array[begin]) > 0) { // 左边元素 < 轴点元素
                    begin++;
                } else { // 左边元素 >= 轴点元素
                    array[end--] = array[begin];
                    break;
                }
            }
        }

        //使用备份的轴点元素放入到最终的位置之中
        array[begin] = pivot;
        //返回轴点元素
        return begin;
    }
}

这里注意上面代码之中的等于的情况: