住建局网站官网,江西景德镇建设厅网站,湖南乔口建设公司网站,网址大全2345qiren个人主页#xff1a;仍有未知等待探索_C语言疑难,数据结构,小项目-CSDN博客 专题分栏#xff1a;算法_仍有未知等待探索的博客-CSDN博客 快速排序的思想——分治
目录 一、引言
二、讲解
1、步骤
2、代码
1.以左边界作为基准
2.以右边界作为基准
3.以中心点作为基准 … 个人主页仍有未知等待探索_C语言疑难,数据结构,小项目-CSDN博客 专题分栏算法_仍有未知等待探索的博客-CSDN博客 快速排序的思想——分治
目录 一、引言
二、讲解
1、步骤
2、代码
1.以左边界作为基准
2.以右边界作为基准
3.以中心点作为基准 一、引言
快速排序是对冒泡排序的一种改进。它的基本思想在于划分首先选一个基准x让x的左边都小于x让x的右边都大于x。然后通过递归一直将数组分成两个或一个元素。
二、讲解
1、步骤 1、将确定分界点。 2、调整范围——让基准x的左边都小于x让x的右边都大于x。 3、递归分治。 注意边界问题 如果arr数组为【01】 基准点为左边界。 x0i-1j2 因为i先自增arr[0]0,退出循环.。 j先自减arr[j]0,继续进入循环j--arr[j]0,退出循环。 如果 quick(arr,l,i-1); quick(arr,i,r); 这样分治的话第一个递归进入后会立刻退出来因为分治的区间没有元素。第二个递归进入后要进行划分的区间仍然是【01】将会死循环栈溢出。 所以分边界点的话要用j进行区分。 2、代码
1.以左边界作为基准
#includeiostream
using namespace std;
#includecstdio
const int N 1e5 5;
int arr[N], n;
void quick_sort(int arr[], int l, int r) {if (l r) {return;}//基准x是arr数组的左边界int i l - 1, j r 1, x arr[l];while (i j) {do {i;} while (arr[i] x);do {j--;} while (arr[j] x);if (i j) {int temp;temp arr[i];arr[i] arr[j];arr[j] temp;}}//这块要配合着基准x为arr的左边界下边的j不能换成i//如果要换成i的话基准x也要跟着变quick_sort(arr, l, j);quick_sort(arr, j 1, r);
}
int main() {scanf(%d, n);for (int i 0; i n; i) {scanf(%d, arr[i]);}quick_sort(arr, 0, n - 1);for (int i 0; i n; i) {printf(%d , arr[i]);}return 0;
}
2.以右边界作为基准
#includeiostream
using namespace std;
#includecstdio
const int N 1e5 5;
int arr[N], n;
void quick_sort(int arr[], int l, int r) {if (l r) {return;}int i l - 1, j r 1, x arr[r];while (i j) {do {i;} while (arr[i] x);do {j--;} while (arr[j] x);if (i j) {int temp;temp arr[i];arr[i] arr[j];arr[j] temp;}}quick_sort(arr, l, i-1);quick_sort(arr, i, r);
}
int main() {scanf(%d, n);for (int i 0; i n; i) {scanf(%d, arr[i]);}quick_sort(arr, 0, n - 1);for (int i 0; i n; i) {printf(%d , arr[i]);}return 0;
}
3.以中心点作为基准
#includeiostream
using namespace std;
#includecstdio
const int N 1e5 5;
int arr[N], n;
void quick_sort(int arr[], int l, int r) {if (l r) {return;}int i l - 1, j r 1, x arr[(lr)/2];while (i j) {do {i;} while (arr[i] x);do {j--;} while (arr[j] x);if (i j) {int temp;temp arr[i];arr[i] arr[j];arr[j] temp;}}quick_sort(arr, l, j);quick_sort(arr, j1, r);
}
int main() {scanf(%d, n);for (int i 0; i n; i) {scanf(%d, arr[i]);}quick_sort(arr, 0, n - 1);for (int i 0; i n; i) {printf(%d , arr[i]);}return 0;
}
