算法思想


如图序列,我们先设置一个基准,假设基准是第一个元素49,每次扫描都将序列变成[比49小的...49...比49大的]这种形式,然后在分别递归地对49左右两边的
序列进行相同操作,相当于递归的每次调用都确定了一个元素的相对位置(基准),所有元素的相对位置都确定了下来,则序列就排好了序.

现在假设两根指针(标记,其实不是指针)分别指向头和尾, 设基准元素为low指向元素.

  1. 先让high移动直到找到比基准元素49(0)小的元素,即27(6);将其移到low所指位置即0,原来的元素49已经保存在基准当中;
  2. 再让low移动直到找到比基准元素49大的元素,即65(2);将其移动到high所指位置即6,该位置已经空出;
  3. 1、2步交替进行, 直到low与high指针相遇,此时将基准元素放到该位置; 然后进入递归下一层,即分别对基准元素左右序列进行上述操作直到子序列长度为1.

C++实现


代码:

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
59
60
61
62
#include <map>
#include <set>
#include <ctime>
#include <stack>
#include <cmath>
#include <queue>
#include <bitset>
#include <string>
#include <vector>
#include <cstdio>
#include <cctype>
#include <fstream>
#include <cstdlib>
#include <sstream>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define LL long long
#define up(x) for(int i=0;i<x;i++)
#define rson mid+1,r,rt<<1|1
#define lson l,mid,rt<<1

const int INF = 0x3f3f3f3f;     ///1 061 109 567
const int negative_infinite = 0xcfcfcfcf;   ///-808 464 433

void quickSort(int *L,int low,int high)
{
    if(high<=low)
        return;

    int l=low,h=high;
    int cp = L[low];
    while(low<high)
    {
        while(low<high&&L[high]>=cp)
            --high;
        L[low]=L[high];
        while(low<high&&L[low]<cp)
            ++low;
        L[high]=L[low];
    }
    L[low] = cp;
    quickSort(L,l,low-1);
    quickSort(L,high+1,h);
    return;
}


int main()
{
    //ios::sync_with_stdio(false);
    //cin.tie(NULL);
    int n;
    cin>>n;
    int a[n];
    up(n)cin>>a[i];
    quickSort(a,0,n-1);
    cout<<"---------"<<endl;
    up(n)cout<<a[i]<<" ";
    return 0;
}

Python实现


Code:

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
# -*- coding: utf-8 -*-
# @Time    : 6/21/2021 20:32 PM
# @Author  : Chen0495
# @Email   : 1346565673@qq.com|chenweiin612@gmail.com
# @File    : test.py.py
# @Software: PyCharm

def quickSort(L, low, high):
    if (low >= high): return
    l = low
    h = high
    point = L[low]
    while (low < high):
        while (low < high and L[high] >= point): high -= 1
        L[low] = L[high]
        while (low < high and L[low] <= point): low += 1
        L[high] = L[low]
    L[low] = point
    quickSort(L, l, low - 1)
    quickSort(L, low + 1, h)
    return


if __name__ == "__main__":
    List = list(map(int, input().split()))
    quickSort(List, 0, len(List) - 1)
    print(List)