一、快速排序
- 基本思想：通过一组排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据小，然后再按此方法对这部分数据分别进行快速排序，整个排序过程可以递归进行，以此使所有数据变成有序序列。
- 算法思想：基于分治策略
- 分解：先从数列中取出一个元素作为基准元素。以此基准元素为标准，将序列分解为两个子序列，使小于或等于基准元素的子序列在左侧，大于等于基准子序列的在右侧
- 治理：对两个子序列进行快速快速排序
- 合并：将排好序的的两个子序列合并在一起
- 时间复杂度：n log n
二、AcWing模板
模板题：AcWing 785. 快速排序
//
// Created by zk on 2021/6/1.
//
#include <iostream>
using namespace std;
const int N = 1000010;
int n;
int q[N], tmp[N];
void merge_sort(int q[], int l, int r){
if (l >= r) return;
int mid = l + r >> 1;
merge_sort(q, l, mid);
merge_sort(q, mid+1, r);
int k = 0;
int i = l;
int j = mid + 1;
while(i <= mid && j <= r)
if (q[i] <= q[j]) tmp[k++] = q[i++];
else tmp[k ++] = q[j++];
while(i <= mid) tmp[k ++] = q[i++];
while(j <= r) tmp[k++] = q[j++];
for(i=l, j=0; i<=r; i++, j++) q[i] = tmp[j];
}
int main(){
scanf("%d", &n);
for(int i=0; i<n; i++) scanf("%d", &q[i]);
merge_sort(q, 0, n-1);
for(int i=0; i<n; i++) printf("%d ", q[i]);
return 0;
}
三、趣学数据结构版
#include<iostream>
using namespace std;
int Partition(int r[],int low,int high)//划分函数
{
int i=low,j=high,pivot=r[low];//基准元素
while(i<j)
{
while(i<j&&r[j]>pivot) j--;//向左扫描
if(i<j)
swap(r[i++],r[j]);//r[i]和r[j]交换后i+1右移一位
while(i<j&&r[i]<=pivot) i++;//向右扫描
if(i<j)
swap(r[i],r[j--]);//r[i]和r[j]交换 后j-1左移一位
}
return i;//返回最终划分完成后基准元素所在的位置
}
int Partition2(int r[],int low,int high)//划分函数
{
int i=low,j=high,pivot=r[low];//基准元素
while(i<j)
{
while(i<j&&r[j]>pivot) j--;//向左扫描
while(i<j&&r[i]<=pivot) i++;//向右扫描
if(i<j)
swap(r[i++],r[j--]);//r[i]和r[j]交换
}
if(r[i]>pivot)
{
swap(r[i-1],r[low]);//r[i-1]和r[low]交换
return i-1;//返回最终划分完成后基准元素所在的位置
}
swap(r[i],r[low]);//r[i]和r[low]交换
return i;//返回最终划分完成后基准元素所在的位置
}
void QuickSort(int R[],int low,int high)//实现快排算法
{
int mid;
if(low<high)
{
mid=Partition(R,low,high); //基准位置
// for(int i=low;i<=high;i++)
// cout<<R[i]<<" ";
// cout<<endl;
QuickSort(R,low,mid-1);//左区间递归快排
QuickSort(R,mid+1,high);//右区间递归快排
}
}
int main()
{
int a[100];
int i,n;
cout<<"请先输入要排序的数据的个数：";
cin>>n;
cout<<"请输入要排序的数据：";
for(i=0;i<n;i++)
cin>>a[i];
cout<<endl;
QuickSort(a,0,n-1);
cout<<"排序后的序列为："<<endl;
for(i=0;i<n;i++)
cout<<a[i]<<" " ;
cout<<endl;
return 0;
}
四、陈越版
更加专业
- 直接调用库函数
/* 快速排序 - 直接调用库函数 */
#include <stdlib.h>
/*---------------简单整数排序--------------------*/
int compare(const void *a, const void *b)
{ /* 比较两整数。非降序排列 */
return (*(int*)a - *(int*)b);
}
/* 调用接口 */
qsort(A, N, sizeof(int), compare);
/*---------------简单整数排序--------------------*/
/*--------------- 一般情况下，对结构体Node中的某键值key排序 ---------------*/
struct Node {
int key1, key2;
} A[MAXN];
int compare2keys(const void *a, const void *b)
{ /* 比较两种键值：按key1非升序排列；如果key1相等，则按key2非降序排列 */
int k;
if ( ((const struct Node*)a)->key1 < ((const struct Node*)b)->key1 )
k = 1;
else if ( ((const struct Node*)a)->key1 > ((const struct Node*)b)->key1 )
k = -1;
else { /* 如果key1相等 */
if ( ((const struct Node*)a)->key2 < ((const struct Node*)b)->key2 )
k = -1;
else
k = 1;
}
return k;
}
/* 调用接口 */
qsort(A, N, sizeof(struct Node), compare2keys);
/*--------------- 一般情况下，对结构体Node中的某键值key排序 ---------------*/
- 自实现
/* 快速排序 */
ElementType Median3( ElementType A[], int Left, int Right )
{
int Center = (Left+Right) / 2;
if ( A[Left] > A[Center] )
Swap( &A[Left], &A[Center] );
if ( A[Left] > A[Right] )
Swap( &A[Left], &A[Right] );
if ( A[Center] > A[Right] )
Swap( &A[Center], &A[Right] );
/* 此时A[Left] <= A[Center] <= A[Right] */
Swap( &A[Center], &A[Right-1] ); /* 将基准Pivot藏到右边*/
/* 只需要考虑A[Left+1] … A[Right-2] */
return A[Right-1]; /* 返回基准Pivot */
}
void Qsort( ElementType A[], int Left, int Right )
{ /* 核心递归函数 */
int Pivot, Cutoff, Low, High;
if ( Cutoff <= Right-Left ) { /* 如果序列元素充分多，进入快排 */
Pivot = Median3( A, Left, Right ); /* 选基准 */
Low = Left; High = Right-1;
while (1) { /*将序列中比基准小的移到基准左边，大的移到右边*/
while ( A[++Low] < Pivot ) ;
while ( A[--High] > Pivot ) ;
if ( Low < High ) Swap( &A[Low], &A[High] );
else break;
}
Swap( &A[Low], &A[Right-1] ); /* 将基准换到正确的位置 */
Qsort( A, Left, Low-1 ); /* 递归解决左边 */
Qsort( A, Low+1, Right ); /* 递归解决右边 */
}
else InsertionSort( A+Left, Right-Left+1 ); /* 元素太少，用简单排序 */
}
void QuickSort( ElementType A[], int N )
{ /* 统一接口 */
Qsort( A, 0, N-1 );
}
五、 可视化展示
-
Data Structure Visualization: https://www.cs.usfca.edu/~galles/visualization/Algorithms.html
quick sort
Data Structure Visualization.png -
VisuAlgo: https://visualgo.net/zh
quick sort
VisuAlgo.png
- algorithm-visualizer: https://algorithm-visualizer.org/
Quicksort
algorithm-visualizer.png
