Обмен технологиями

한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina

Предисловие: В этой статье представлены подробные ответы на некоторые сомнения по поводу раннего изучения алгоритма быстрой сортировки, а также представлена ​​оптимизированная версия базового алгоритма быстрой сортировки.

1. Давайте еще раз поговорим о быстрой сортировке

Основой алгоритма быстрой сортировки является分治思想Стратегия «разделяй и властвуй» делится на следующие три этапа:

1. Декомпозиция: разложите исходную проблему на несколько похожих, меньших подзадач.
2. Решение: если подзадача небольшая, решите ее напрямую, в противном случае решите подзадачу рекурсивно;
3. Слияние: Решение исходной проблемы равно слиянию решений нескольких подзадач.

Применительно к алгоритму быстрой сортировки:

1. Декомпозиция: Алгоритм быстрой сортировки хочет отсортировать весь массив, но масштаб велик, поэтому ему необходимо найти способ уменьшить масштаб. Его стратегия решения — «выбрать контрольный элемент и разделить массив на; две части, причем элементы слева меньше эталонного элемента, все элементы справа больше эталонных элементов». Повторив описанный выше процесс, вы можете завершить сортировку всего массива. После завершения этой операции один раз для всего массива выполните описанную выше процедуру для левого и правого интервалов соответственно.
2. Быстрая рекурсивная сортировка двух подмассивов до тех пор, пока длина каждого подмассива не станет равна 0 или 1, после чего массивы сортируются.
3. Поскольку во время рекурсии подмассивы сортировались отдельно, дополнительный этап слияния не требуется.

2. Реализация кода и подробное объяснение

Код ключа для быстрой сортировки:如何根据基准元素划分数组区间(parttion), существует множество методов декомпозиции, здесь представлен только один метод.挖坑法
Код:

class Solution {
    public int[] sortArray(int[] nums) {
        quick(nums, 0, nums.length - 1);
        return nums;
    }

    private void quick(int[] arr, int start, int end) {
        if(start >= end) return;// 递归结束条件
        int pivot = parttion(arr, start, end);
		
		// 递归解决子问题
        quick(arr, start, pivot - 1);
        quick(arr, pivot + 1, end);
    }

	
	// 挖坑法进行分解
    private int parttion(int[] arr, int left, int right) {
        int key = arr[left];
        while(left < right) {
            while(left < right && arr[right] >= key) right--;
            arr[left] = arr[right];
            while(left < right && arr[left] <= key) ++left;
            arr[right] = arr[left];
        }
        arr[left] = key;
        return left;
    }
    
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

---

Подробные ответы:
1. Почемуstart>=endЭто конечное условие рекурсии?

Непрерывная декомпозиция подзадачи. Конечный размер подзадачи равен 1, то есть существует только один элемент. На данный момент нет необходимости продолжать декомпозицию. Указатели начала и конца указывают на элемент одновременно. время.

2. Почему первыми должны идти правые, а не левые?

Это зависит от того, кто пойдет первым基准元素的位置В приведенном выше коде базовый элемент (ключ) является самым левым элементом, если он перемещается первым.left, left сначала встречает элемент, больший, чем базовый элемент, а затем выполняетarr[right] = arr[left], из-за отсутствия сохраненияarr[right], этот элемент будет потерян
Если вы сначала пойдете вправо, right сначала встретит элемент, меньший, чем базовый элемент, а затем выполнитarr[left]=arr[right], поскольку в это время левая сторона не двигалась, она все еще является опорной, но опорная точка была сохранена нами с помощью ключа.

3.Почему arr[right]>=key?>Разве это невозможно?

Больше или равно в основном предназначено для обработки重复元素问题
Например, есть массив[6,6,6,6,6]Если это >, правый указатель не будет перемещаться, и левый указатель тоже не будет перемещаться, и он застрянет в бесконечном цикле.

4. Почему этот метод называется методом рытья ямы?

Когда указатель r встречает первыйarr[r] = arr[l], в это время позиция l пуста, образуя ямку.

---

3. Оптимизация быстрой сортировки

Существует два основных направления оптимизации:

1. Выбор опорного значения может доказать, что, когда эталонное значение выбирается случайным образом, временная сложность быстрой сортировки приближается к нулю.O(N*logN), то есть лучшая временная сложность
2. Обработка повторяющихся элементов: если в интервале имеется большое количество повторяющихся элементов, приведенная выше версия алгоритма быстрой сортировки будет повторять одни и те же элементы несколько раз, чтобы уменьшить количество избыточных операций;数组分三块В то же время, если вы встретите специальные тестовые случаи (последовательный массив или обратный массив), временная сложность ухудшится доO(N^2)

Во-первых, на основе вопроса (сортировать по цвету) понять, что такое数组分三块
анализировать

Код:

class Solution {
    public void sortColors(int[] nums) {
        // 分治 --
        // 1.定义三指针
        int i = 0;// 遍历整个数组
        int l = -1, r = nums.length;

        while(i < r) {
            if(nums[i] == 0) swap(nums,++l,i++);
            else if(nums[i] == 1) i++;
            else swap(nums,--r,i);
        }
        return;
    }

    private void swap(int[] nums,int x,int y) {
        int tmp = nums[x]; nums[x] = nums[y]; nums[y] = tmp;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

• Уведомлениеl,r的起始位置, первый элемент и последний элемент принадлежат未处理状态, поэтому `l, r не могут указывать на эти два элемента и должны находиться вне интервала
• Так называемый массив делится на три части, что означает использование三个指针去分别维护四个区间, один из интервалов未处理区间, поскольку указатель cur продолжает двигаться, обрабатываются все интервалы, и, наконец, остается только три интервала.

Примените приведенные выше идеи к快速排序的parttion中, конечный результат разбивается на три интервала

Код:

class Solution {
    // 快速排序优化版
    // 分解--解决--合并
    public int[] sortArray(int[] nums) {
        qsort(nums, 0, nums.length - 1);
        return nums;
    }

    private void qsort(int[] nums, int start, int end) {
        if(start >= end) return;// 递归结束条件
        // 分解
        int pivot = nums[start];
        int l = start - 1, r = end + 1, i = start;
        while(i < r) {
            int cur = nums[i];
            if(cur < pivot) swap(nums, ++l, i++);
            else if(cur == pivot) ++i;
            else swap(nums, --r, i);
        }

        // [start, l]  [l+1, r-1]  [r, end]
        // 递归解决
        qsort(nums, start, l);
        qsort(nums, r, end);
    }

    private void swap(int[] nums,int i, int j) {
        int tmp = nums[i];  nums[i] = nums[j]; nums[j] = tmp;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

2. Случайным образом выберите базовое значение.
Случайным образом выберите базовое значение, используя случайные числа.

        int pivot = nums[start + new Random().nextInt(end - start + 1)];
        //               起始位置      随机产生的偏移量

1
2
3

Полный улучшенный код:

class Solution {
    // 快速排序优化版
    // 分解--解决--合并
    public int[] sortArray(int[] nums) {
        qsort(nums, 0, nums.length - 1);
        return nums;
    }

    private void qsort(int[] nums, int start, int end) {
        if(start >= end) return;// 递归结束条件
        // 分解
        int pivot = nums[start + new Random().nextInt(end - start + 1)];
        int l = start - 1, r = end + 1, i = start;
        while(i < r) {
            int cur = nums[i];
            if(cur < pivot) swap(nums, ++l, i++);
            else if(cur == pivot) ++i;
            else swap(nums, --r, i);
        }

        // [start, l]  [l+1, r-1]  [r, end]
        // 递归解决
        qsort(nums, start, l);
        qsort(nums, r, end);
    }

    private void swap(int[] nums,int i, int j) {
        int tmp = nums[i]; 
        nums[i] = nums[j]; 
        nums[j] = tmp;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

• Эффективность значительно повысилась

4. Алгоритм быстрого выбора

Алгоритм быстрого выбора:基于快速排序优化版本Временная сложностьO(N)Алгоритм выбора, сценарий использования:第K大/前K大проблемы выбора, такие как

01.K-й по величине элемент массива.
Ссылка: https://leetcode.cn/problems/kth-largest-element-in-an-array/
анализировать

• Решение грубой силы — использовать его напрямую.sortОтсортируйте и затем вернитесь к K-му крупнейшему
• временная сложность:O(N*logN)
• Пространственная сложность:O(logN)Вызовы стека, генерируемые рекурсией

Далее используется алгоритм быстрого выбора для реализацииO(N)Временная сложность
Код:

class Solution {
    public int findKthLargest(int[] nums, int k) {
        return qsort(nums, 0, nums.length - 1, k);
    }

    private int qsort(int[] nums, int start, int end, int k) {
        if(start >= end) return nums[start];
        int pivot = nums[start + new Random().nextInt(end - start + 1)];
		
		// 数组分三块  <pivot  ==pivot  >pivot
        int l = start - 1, r = end + 1, i = start;
        while(i < r) {
            if(nums[i] < pivot) swap(nums, ++l, i++);
            else if(nums[i] == pivot) ++i;
            else swap(nums, --r, i);
        }

        // [start, l]  [l+1, r - 1]  [r, end]
        int c = end - r + 1, b = r - 1 - (l + 1) + 1, a = l - start + 1;
        // 分情况讨论  进行选择
        if(c >= k) return qsort(nums, r, end, k);
        else if(b + c >= k) return pivot;
        else return qsort(nums, start, l, k - b - c);// 找较小区间的第(k-b-c)大
    }

    private void swap(int[] arr, int i, int j) {
        int tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

• Идея алгоритма быстрого выбора очень похожа на идею быстрой сортировки. Разница в том, что алгоритм быстрого выбора рекурсирует только часть интервала каждого результата разделения, а не рекурсирует весь интервал, как быстрая сортировка. Снижается временная сложность алгоритма быстрого выбора.O(N)