c++快速排序详解
快速排序,实际中最常用的一种排序算法,速度快,效率高,下面是小编分享的c++快速排序详解,一起来看一下吧。
基本思想:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分所有数据要小,然后再按此方法对这两部分数据分别进行快速排序。整个排序过程可以递归进行,以此达到整个数据变成有序序列。
将数列变成上述形式,这一步很关键,做好这一步,才能对主元左右的部分进行递归调用。以下是实现这一部分的代码:
int partition_sort(int arr[],int l,int r)//l是数组最左边,r为最右边
{
int j=l;//设计标记
int t=arr[l];//设置主元
for(int i=l+1;i<=r;i++)
{
if(arr[i]<t){
swap(arr[j+1],arr[i]);
j++;
}
}
swap(arr[l],arr[j]);
return j;
}
上述代码中,我把最左边的元素当作主元,这样的代码对大多数排序都很高效,但是不排除个别情况(当数组近乎有序或者当数组内有大量重复元素),这时,我们的.排序算法相比于归并排序显得并不是那么高效,这和我们的排序算法原理密不可分,细细分析,当数组近乎有序时,我们的快速排序竟然退化到了O(n^2)级别,这显然是非常不高效的。
要想实现上述不足的优化,我们可以将主元随机选择,或者采用其他方式的快速排序(双路快速排序,三路快速排序),本篇内容仅作为学习快排的基本思想和基本实现,不深入涉及,有兴趣的读者可查阅资料了解。
下面是全部的实现代码:
#include <iostream>
#include <math.h>
using namespace std;
//实现函数,用于partition的递归
int partition_sort(int arr[],int l,int r)//l是数组最左边,r为最右边
{
int j=l;//设计标记
int t=arr[l];//设置主元
for(int i=l+1;i<=r;i++)
{
if(arr[i]<t){
swap(arr[j+1],arr[i]);
j++;
}
}
swap(arr[l],arr[j]);
return j;
}
//实现递归的调用函数
void partition(int arr[],int l,int r)
{
if(l>=r)return ;
int p=partition_sort(arr,l,r);
partition(arr,l,p-1);
partition(arr,p+1,r);
}
int main()
{
int a[5];
for(int i=0;i<5;i++)
{
cin>>a[i];
}
partition(a,0,4);
for(int i=0;i<5;i++)
{
cout<<a[i]<<" ";
}
return 0;
}
-
为什么入门首选C语言?
C语言的设计目标是提供一种能以简易的方式编译、处理低级存储器、产生少量的机器码以及不需要任何运行环境支持便能运行的编程语言。对于大部分程序员,C语言是学习编程的第一门语言,很少有不了解C的程序员。那么为什么入门首选C语言呢,下面小编为大家介绍一下吧!C...
-
直接插入排序(C语言实现)
直接插入排序方法:仅有一个记录的表总是有序的,因此,对于有n个记录的表,可以从第二个记录开始直到第n个记录逐个有序的向有序表中进行插入操作,从而得到n个记录按关键字有序的表。下面一起跟着小编学习一下吧!实现一个直接插入排序的`C语言函数,要求对要排序的元素按...
-
Mac系统怎样使用终端编写c语言程序
C语言是目前较为普遍的程序语言,它功能丰富、表达能力强、使用灵活方便、目标程序效率高,适合编制一般应用软件。下面是应届毕业生小编收集整理的Mac系统怎样使用终端编写c语言程序,希望对大家有帮助~~Mac系统使用终端编写c语言程序的'方法工具/原料Mac系统,终...
-
c语言中多个if的用法
c语言中多个if的用法的用法你知道吗?下面小编就跟你们详细介绍下c语言中多个if的用法的用法,希望对你们有用。c语言中多个if的用法的用法如下:用if语句可以构成分支结构。它根据给定的条件进行判断,以决定执行某个分支程序段。C语言的if语句有三种基本形式。语句的...