首页 > 代码库 > 快排实现
快排实现
思想：
对于一个未排序数列a, 令key=a[left](可以是其他任意元素） 我们通过操作(1)将小于key的元素置于它左边，大于key的元素置于它的右边；
再递归对其右边和左边区间进行如上操作；
操作(1)的具体步奏如下：
对于当前数列a[left...right]：
1：将key从数列中挖出，此时a[left]有一个坑；
2：从key右边往左找出一个小于key的元素，挖了填a[left]，此时右边有一个坑；
3：从key左边找一个大于key的元素，挖了填右边，此时左边又有一个坑；
4：依次重复步奏2,3直至当前坑左边全为不大于key的元素，右边全为不小于key的元素，再将key填入此坑；
代码：
1 #include <bits/stdc++.h> 2 #define MAXN 100000+10 3 using namespace std; 4 5 //************快排实现************************** 6 7 int quick_sort(int* a, int left, int right){ 8 if(left<=right){ 9 int key=a[left], i=left, j=right;10 while(i<j){11 for(; i<j&&key<=a[j]; j--);12 a[i]=a[j];13 for(; i<j&&a[i]<=key; i++);14 a[j]=a[i];15 }16 a[i]=key;17 quick_sort(a, left, i-1);18 quick_sort(a, i+1, right);19 }20 }21 22 int main(void){23 int n, a[MAXN], t[MAXN];24 cin >> n;25 for(int i=0; i<n; i++){26 cin >> a[i];27 }28 quick_sort(a, 0, n);29 for(int i=0; i<n; i++){30 cout << a[i] << " ";31 }32 cout << endl;33 return 0;34 }
快排实现
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。