首页 > > 程序设计 > C/C++ >

快速排序

2018-07-12 07:32:42来源：博客园阅读 ()

总共大致分为几种，包括选择排序法，冒泡排序法，插入排序法，快速排序法和堆排序。

其中比较简单的是选择冒泡和插入，比较抽象的就是快排和堆排。这里先讲快排，因为这也是比较常用的算法，包含在algorithm头文件里面。

关于快排实际上就是分治思想和递归思想的结合。快排的函数是一个递归函数，其中将排序数组分治成为两块。

每次都分治成为两块，然后将其中的第一个数作为标准值，大的放在标准值的后面，小的放在标准值的前面，最后将中间的数值和标准值交换位置。

这实际上就是设置一个中间量，交换原数组中比标准值大的数和比标准值小的数的位置的事情，因为标准值是一个虚拟放在中间的数，最后将标准值放置到位。

还有要利用的是数组的双排思想。什么叫数组的双排思想呢，说的就是数组里面不仅仅是元素，还有它的标号。通过标号来一个一个的寻找比较。

这个思想解释的比较好的有一个网站，这里罗列下：算法 3：最常用的排序--快速排序。

#include <iostream>
int a[100],n;
using namespace std;
void quicksort(int left,int right);
int main()
{
　　cin>>n;
　　for(int i=0;i<n;i++) {
　　cin>>a[i];
}
quicksort(0,n-1);
for(int i=0;i<n;i++) {
　　cout<<a[i]<<" ";
}
return 0;
}
void quicksort(int left,int right)
{
　　int i,j,temp,t;
　　if(left<right) {
　　return;
}
i=left;
j=right;
temp=a[left];
while(i!=j) {
while(temp>a[j]&&i<j) {
　　j--;
}
　　while(temp<a[i]&&i<j) {
　　i++;
}
t=a[j];
a[j]=a[i];
a[i]=t;
}
a[left]=a[i];
a[i]=temp;
quicksort(left,i-1);
quicksort(i+1;right);
}