余姚网站建设 熊掌号,河北建设机械协会网站,制作app费用,十个免费软件不收费快速排序
算法原理 1. 取一个元素p(第一个元素#xff0c;最后一个元素#xff0c;中间元素#xff0c;随机 都可以)#xff0c;使元素p归位。 2. 列表被p分成两部分#xff0c;左边都比p小#xff0c;右边都比p大。 3. 递归完成排序。 动态演示 python代码实现
import…快速排序
算法原理 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;
}
