分治法 快速排序

分治法 快速排序

1.力扣题目编号：912

2.算法思想

快速排序是基于分治策略的一种排序算法，主要思想是先设置一个基准元素，通过划分将待排序的序列分成前后两部分，其中前一部分的数据都比基准元素要小，后一部分的数据都比基准元素要大，然后再递归调用，对两部分的序列分别进行快速排序，以此使整个序列达到有序。

3.算法步骤

  1. 对于待排序数组a[left, right]，以a[mid]为基准元素将a[left, right]分为a[left, mid-1]，a[mid]，a[mid+1, right]3部分，使a[left, mid-1]的所有元素小于等于a[mid]，a[mid+1, right]的所有元素大于等于a[mid]。
  2. 递归调用快排算法，分别对a[left, mid-1]和a[mid+1, right]进行排序。

4.完整代码

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
53
54
55
56
57
58
#include<bits/stdc++.h>
using namespace std;

const int MAX = 1e3+7;
int a[MAX];
int N;

int partition(int a[], int left, int right){
    int i = left;
    int j = right+1;
    int x = a[i];
    while(true)
    {
        while(a[++i] < x && i < right);
        while(a[--j] > x );
        if(i >= j)
        {
            break;
        }
        swap(a[i], a[j]); 
    }
    a[left] = a[j];
    a[j] = x;
    return j;
}

void quickSort(int a[], int left, int right){
    if(left < right)
    {
        int mid = partition(a, left, right);
        quickSort(a, left, mid-1);
        quickSort(a, mid+1, right);
    }
}

int main(){
    cin >> N;
    int num;
    for(int i = 0; i < N; i++)
    {
        cin >> num;
        a[i] = num;
    }

    quickSort(a, 0, N-1);

    cout << "快速排序后：";
    for(int i = 0; i < N; i++)
    {
        cout << a[i] << " ";
    }
}

/*
15
12 38 1 3 89 100 2 7 29 28 43 78 28 11 4
*/