You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.

86 lines
3.1 KiB

This file contains ambiguous Unicode characters!

This file contains ambiguous Unicode characters that may be confused with others in your current locale. If your use case is intentional and legitimate, you can safely ignore this warning. Use the Escape button to highlight these characters.

#include <bits/stdc++.h>
using namespace std;
//数组打印
void P(int a[], int n) {
for (int i = 0; i < n; i++)
cout << a[i] << " ";
cout << endl;
}
/*
快速排序算法
1.从数列中挑出一个元素,称为 “基准”pivot
2.重新排序数列,所有元素比基准值小的摆放在基准前面,所有元素比基准值大的摆在基准的后面(相同的数可以到任一边)。
在这个分区退出之后该基准就处于数列的中间位置。这个称为分区partition操作
3.递归地recursive把小于基准值元素的子数列和大于基准值元素的子数列排序。
*/
// 下面的方法其实是用的左右指针
int partition(int *s, int l, int r) {
//左边第一个默认是基准元素
int i = l, j = r, x = s[l]; //将最左元素记录到x中,x是一个备份
//i,j应该是双指针的意思
while (i < j) {
// 从右向左找第一个<x的数,注意这里面的i<j,防止j--后j<=i.
while (i < j && s[j] >= x)
j--;
//j还在i的右边的话
if (i < j)
s[i++] = s[j]; //直接替换掉最左元素已在x中存有备份
// 从左向右找第一个>x的数
while (i < j && s[i] <= x)
i++;
if (i < j)
//替换掉最右元素(已在最左元素中有备份)
//最左元素一定被覆盖过,若没有,则表明右侧所有元素都>x那么算法将终止
s[j--] = s[i];
}
s[i] = x; //i的位置放了x所以其左侧都小于x右侧y都大于x
return i;
}
// 图解快速排序quick sort
// https://haokan.baidu.com/v?vid=190736151353458762&pd=bjh&fr=bjhauthor&type=video
// 实现 Partion (升序) 快慢指针
// https://blog.csdn.net/qq_43763344/article/details/89409246?utm_medium=distribute.pc_aggpage_search_result.none-task-blog-2~all~sobaiduend~default-2-89409246.nonecase&utm_term=%E5%BF%AB%E9%80%9F%E6%8E%92%E5%BA%8F%E5%BF%AB%E6%85%A2%E6%8C%87%E9%92%88&spm=1000.2123.3001.4430
int partition2(int *array, int left, int right) {
// 最后一个值作为基准值.
int key = array[right - 1];
int pre = left - 1;
for (int cur = left; cur < right; ++cur) {
if (array[cur] < key && ++pre != cur) {
swap(array[cur], array[pre]);
}
}
swap(array[++pre], array[right - 1]);
return pre;
}
//递归的快速排序
void quickSort(int s[], int l, int r) {
//l,r-->从l到r
//数组左界<右界才有意义,否则说明都已排好,直接返回即可
if (l >= r) {
return;
}
// 划分,返回基准点位置
int mid = partition2(s, l, r);
// 递归处理左右两部分mid处为分界点不用管mid了
quickSort(s, l, mid - 1);
quickSort(s, mid + 1, r);
}
int main() {
int a[] = {72, 6, 57, 88, 60, 42, 83, 73, 48, 85};
//输出一维数组
P(a, 10);
//快速排序
quickSort(a, 0, 9);//注意最后一个参数是n-1
//再次输出一维数组
P(a, 10);
return 0;
}