基础算法--快速排序

快速排序

算法原理

1. 取一个元素p(第一个元素，最后一个元素，中间元素，随机 都可以)，使元素p归位。

2. 列表被p分成两部分，左边都比p小，右边都比p大。

3. 递归完成排序。

动态演示

python代码实现

import sys
import time# 修改递归最大深度
sys.setrecursionlimit(100000)def partition(li, left, right):# 先把最左边的值拿出来，放入tmp变量临时存储tmp = li[left]# 循环条件 左边指针一直小于右边指针while left < right:# 从最右边找比tmp小的数，放入tmp位置while left < right and li[right] >= tmp:right -= 1# 把右边的值写道左边空位上li[left] = li[right]while left < right and li[left] <= tmp:left += 1# 把左边的值写道右边的空位上li[right] = li[left]# 当左右指针相等，就是碰头了，把最左边取出来的值，放入中间左右指针碰头的地方li[left] = tmp  # 把tmp归位return leftdef quick_sort(li, left, right):# 至少两个元素if left < right:mid = partition(li, left, right)quick_sort(li, left, mid - 1)quick_sort(li, mid + 1, right)li = [5, 7, 4, 6, 3, 1, 2, 9, 8]
print(li)
quick_sort(li, 0, len(li) - 1)
print(li)

C++代码实现 同上方python代码

#include <iostream>
using namespace std;const int N = 1000010;
int a[N];int partition(int a[], int left, int right)
{int tmp = a[left];while(left < right){while(left < right && a[right] >= tmp) {right --;}a[left] = a[right];while(left < right && a[left] <= tmp) {left ++;}a[right] = a[left];}a[left] = tmp;return left;
}void quick_sort(int a[],int left,int right)
{if(left < right){  int mid = partition(a, left, right);quick_sort(a, mid + 1, right);quick_sort(a, left, mid - 1);}
}
int main()
{int n;scanf("%d", &n);for(int i = 0; i < n; i++) scanf("%d", &a[i]);quick_sort(a, 0, n - 1);for(int i = 0; i < n; i++) printf("%d ", a[i]);return 0;
}

C++代码实现 acwing模板

#include <iostream>
using namespace std;const int N = 1000010;
int a[N];void quick_sort(int a[],int left,int right)
{if(left >= right) return;int tmp = a[(left + right) / 2], q = left - 1, e = right + 1;while(q < e){do q++;while(a[q] < tmp);do e--;while(a[e] > tmp);if(q < e) swap(a[q], a[e]);}quick_sort(a, left, e);quick_sort(a, e + 1, right);
}int main()
{int n;scanf("%d", &n);for(int i = 0; i < n; i++) scanf("%d", &a[i]);quick_sort(a, 0, n - 1);for(int i = 0; i < n; i++) printf("%d ", a[i]);return 0;
}