分而治之策略-快速排序(c++、java、python)_给定n个待排序的元素,请列出使用分治策略

作者：花生_TL007 | 2024-04-19 01:36:57

踩

给定n个待排序的元素,请列出使用分治策略

快速排序

问题

给定一个无序数组 $a r r$ ，对其排序。

分析

类似于归并排序在于都是使用分而治之思想，借由递归与合并的方式完成。
1. 数组划分，即对于待排序的数组，从中任意选取一个元素作为主元素，并以该元素为分割，使得它左侧的元素均小于它，它右侧的元素均大于它（左右测元素无需有序），具体步骤为
  1. 随机选取一个元素作为主元素 $main\_element$ ，将其放在数组最后（或最前，下面以最后为例）。
  2. 定义索引下标 $i$ , $j$ ， $i$ 指向第一个元素前面一个位置， $j$ 指向第一个元素，通过 $j$ 从第一个元素顺序遍历当前数组除主元素外的所有元素，当该元素 $a r r [j]$ 小于等于主元素 $main\_element$ ，则交换 $a r r [i + 1]$ 与 $a r r [j]$ ，并使 $i$ 自增1，即始终保持 $\le{i}$ 索引的元素均小于主元素，遍历完成后，使得小于等于主元素的元素全部位于 $i$ 左侧（包括 $i$ ），大于主元素的元素全部位于 $i$ 右侧。
  3. 将尾部的主元素 $main\_element$ 与第一个大于它的元素 $a r r [i + 1]$ 交换，使得主元素左侧元素均大于他，右侧元素均小于他。
2. 借助递归，分别再将主元素左侧和右侧的元素进行数组划分。
不同于归并排序在于，归并排序是先分解，合并时求解，算法侧重于合并。快速排序是分解时解决问题，然后再简单合并，算法侧重于分解。从递归角度看，归并排序是在“归”的过程中逐步求解问题，而快速排序是在“递”的过程中解决。

时间复杂度

快速排序的时间复杂度在于数组划分与递归次数两部分.

数组划分每次遍历当前数组长度，为线形时间复杂度 $O (n)$ .
递归次数取决于每次划分时主元素的大小位置，并不像归并排序是固定二分的。
1. 考虑最坏情况每次主元素均为最大或最小元素，设数组长度为 $n$ ，则每次需要划分的数组长度为 $n, n - 1, n - 2, . . ., 1$ ，则递归次数为 $n$ ，递归的时间复杂度为 $O (n)$ .
2. 考虑最好情况每次元素均为中间大小值的元素，即每次主元素将左右数组等分，此时递归次数与归并排序相同，时间复杂度为 $O (l o g n)$ .
3. 可知递归的时间复杂度 $T^{'} (n)$ 满足： $\le T'(n) \le O(n)$
可得快速排序的时间复杂度 $T (n)$ 满足： $\le T(n) \le O(n^2)$

空间复杂度

快速排序的空间复杂度为 $O (1)$

代码

c++

#include <exception>
#include <vector>
#include <ctime>
using std::vector;
using std::exception;
using std::rand;
using std::srand;

class QuickSort {
public :
	// 排序过程中指向被排序数组，减少递归传参
	vector<int>* parr = nullptr; 
	void quick_sort(vector<int>& arr) {
		if (arr.size() == 0) // 数组判空
			throw exception("arr cannot be empty!");
		this->parr = &arr;
		this->_quick_sort(0, this->parr->size());
		this->parr = nullptr; // 排序完成后置空
	}
private :
	void _quick_sort(int left, int right) {
		if (left + 1 == right)
			return;
		// 随机选取主元素，与尾元素交换
		srand(time(nullptr));
		int pos = rand() % (right - left) + left;
		int main_element = (*this->parr)[pos];
		(*this->parr)[pos] = (*this->parr)[right - 1];
		(*this->parr)[right - 1] = main_element;
		// 遍历除主元素外的所有元素，数组划分
		int i = left - 1, j = left, temp = 0;
		for ( ; j < right - 1; j++) {
			if (this->parr->at(j) < main_element) {
				temp =(*this->parr)[i+1];
				(*this->parr)[i + 1] = (*this->parr)[j];
				(*this->parr)[j] = temp;
				i++;
			}
		}
		// 将主元素交换到中间，使其左侧元素小于它，右侧元素大于它
		temp = (*this->parr)[i + 1];
		(*this->parr)[i + 1] = main_element;
		(*this->parr)[right - 1] = temp;
		i++; // 使i指向主元素
		// 当主元素左侧存在元素时进行子数组排序
		if (left < i)
			this->_quick_sort(left, i);
		// 当主元素右侧存在元素时进行子数组排序
		if (i + 1 < right)
			this->_quick_sort(i + 1, right);
	}
};
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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

java

import java.lang.RuntimeException;
import java.util.Random;

public class QuickSort{
    public void quick_sort(int[] arr){
        if (arr.length == 0)
            throw new RuntimeException("arr cannot be empty!");
        this.arr = arr;
        this._quick_sort(0, arr.length);
        this.arr = null; // 排序完成后置空临时引用
    }
    private int[] arr = null; // 排序中指向被排序数组，减少递归传参
    private void _quick_sort(int left, int right){
        if (left + 1 == right)
            return;
        // 随机选取主元素，与尾元素交换
        Random rdm = new Random();
        int pos = rdm.nextInt(right-left) + left;
        int main_element = this.arr[pos];
        this.arr[pos] = this.arr[right - 1];
        this.arr[right - 1] = main_element;
        // 数组划分，遍历除主元素外的所有元素，使小于主元素的位于左侧，大于主元素的位于右侧
        int i = left - 1, j = left, temp = 0;
        for (; j < right - 1; j++){
            if (this.arr[j] < main_element){
                temp = this.arr[i+1];
                this.arr[i+1] = this.arr[j];
                this.arr[j] = temp;
                i++;
            }
        }
        // 将主元素交换到中间，使左侧元素小于它，右侧元素大于它
        temp = main_element;
        this.arr[right-1] = this.arr[i+1];
        this.arr[i+1] = temp;
        i++; // 使i指向主元素
        // 主元素左侧存在元素则进行左侧子数组排序
        if (left < i)
            this._quick_sort(left, i);
        // 主元素右侧存在元素则进行右侧子数组排序
        if (i + 1 < right)
            this._quick_sort(i + 1, right);
    }
}
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
33
34
35
36
37
38
39
40
41
42
43
44

python

class QuickSort:
    def quick_sort(self, arr: list) -> None:
        if len(arr) == 0 : # 数组判空
            raise Exception("arrr cannot be empty!")
        else : 
            self.__arr = arr # 用类成员指向待排序数组，替代传参
            self.__quick_sort(0, len(self.__arr))
            self.__arr = None # 重置成员数组
        
    def __quick_sort(self, left: int, right: int) -> None:
        if left + 1 == right: # 仅有一个元素时终止递归
            return None
        # 1. 定位主元素，放在数组最后
        pos = randint(left, right - 1)
        main_element = self.__arr[pos]
        self.__arr[pos] = self.__arr[right - 1]
        self.__arr[right - 1] = main_element
        # 2. 数组划分，使小于主元素的元素位于主元素左侧，大于主元素的元素位于主元素右侧
        i = left - 1 # <=i索引为小于等于主元素的元素，>i索引为大于主元素的元素
        j = left # j为遍历索引
        while j < right - 1:
            if self.__arr[j] <= main_element:
                temp = self.__arr[i+1]
                self.__arr[i+1] = self.__arr[j]
                self.__arr[j] = temp
                i += 1
            j += 1
        temp = self.__arr[i+1]
        self.__arr[i+1] = self.__arr[right-1]
        self.__arr[right-1] = temp
        i += 1 # 使i指向主元素
        # 3. 左侧子数组快速排序
        if i > left : # 主元素左侧还存在元素时才排序
            self.__quick_sort(left, i)
        # 4. 右侧子数组快速排序
        if i + 1 < right: # 主元素右侧还存在元素时才排序
         self.__quick_sort(i+1, right)
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
33
34
35
36
37

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/花生_TL007/article/detail/449292