下面这个代码可能是最简单的快速排序了,采用递归的思想,每次都把基准值选为第一个元素,把小于基准值的元素放在B数组中,把大于基准值的元素放在C数组中,然后再对B数组进行快速排序,对C数组进行快速排序。当B,C数组均有序后,将B数组(全部小于基准值)+基准值+C数组(全部大于基准值)拼接成A数组即可。
// ConsoleApplication1.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//
#include "pch.h"
#include <iostream>
using namespace std;
void Swap(int *a,int *b)
{
int temp = *b;
*b = *a;
*a = temp;
}
void QSort(int A[],int Left,int Right)
{
int pivot;
int i = 0;
int j = 0;
int k = 0;
int B[100];
int C[100];
if (Left >= Right)
{
return; //只有一个元素返回即可
}
if (Left == Right - 1) //只有两个元素 检查是否有序 无序就排序
{
if (A[Left] > A[Right])
{
Swap(&A[Left],&A[Right]);
return;
}
}
pivot = A[0]; //总是选取第一个元素作为主元
for (i = 1;i <= Right;i++)
{
if (A[i] <= pivot)
{
B[j] = A[i];
j++;
}
if (A[i] > pivot)
{
C[k] = A[i];
k++;
}
}
QSort(B,0,j - 1); //B中的元素都比基准值小
QSort(C,0,k - 1); //C中的元素都比基准值大
//排序好的顺序为: B + 基准 + C
for (i = 0; i < j;i++)
{
A[i] = B[i];
}
A[j] = pivot; //基准
//集合C
for (i = 0; i < k; i++)
{
A[j+1] = C[i];
j++;
}
}
void QuickSort(int A[],int N)
{
QSort(A,0,N-1);
}
int main()
{
int a[] = {5,10,8,6,3,2};
int len = sizeof(a) / sizeof(int);
QuickSort(a,len);
for (int i = 0;i < len;i++)
{
cout << a[i] << " ";
}
}
以上的代码有很大的优化空间。
- 参考资料:
1 《算法图解》 Aditya Bhargava 著 袁国忠译
- 优化以上代码可以参考的资料:
1 《知无涯之std::sort源码剖析》 http://feihu.me/blog/2014/sgi-std-sort/#背景
2 《【数据结构】八大排序之快速排序(递归和非递归方法)》 https://blog.csdn.net/alidada_blog/article/details/82724802
3 《快速排序的递归方式和非递归方式》 https://www.cnblogs.com/ljy2013/p/4003412.html