一、何为算法
1、算法(Algorithm),是程序设计的灵魂,它是利用系统的方法描述解决问题策略的机制。
2、正确算法应满足的性质:
- 输入:有零个或多个输入
- 输出:至少有一个输出
- 确定性:组成算法的每条指令清晰,无歧义。
- 有限性:一个算法在执行有限步骤后必须结束,即计算步骤是有限的。
3、描述算法可以有多种方式,如自然语言、流程图、伪代码、程序设计语言,算法设计就是针对具体的问题,设计出良好的能使计算机解决问题的算法。
同一个问题可以采用不同的算法实现,不同的算法时间、空间上也往往不同,一个算法的好坏可以用时间复杂度和空间复杂度来衡量。
二、排序算法
通过特定的算法因式将一组或多组数据按照既定模式进行重新排序,这种新序列遵循着一定的规则,体现出一定的规律,因此,经处理后的数据便于筛选和计算,大大提高了计算效率。
三、快速排序算法
1、快速排序简单解释
快速算法其实也可以通过递归调用来实现,排序的过程其实就是不断对元素序列进行划分,
直到每一个部分不能划分时即完成快速排序。
2、算法思想
速排序算法是对冒泡排序算法的改进,也属于交换类排序算法。它的基本算法思想如下:
假设待排持序元素个数为n,分别存放在数组a[1…n]中,令第1个元素为参考轴无素),pot=a[1]
,初始时,i=1,j=n
,然后按照以下方法操作:
(1)从第个元素开始向前依次将每个元素与轴元素pot比较。如果当前元素大于等于pot,
则比较前一个元素与pot,即比较a[j-1]与pot;否则,将当前元素移动到第i个位置并执行步骤(2)。
(2)从第1个元素开始向后依次将每个元素与轴元素pot比较。如果当前元素小于pot,
则比较后个元素与pot,即比较a[i+1]与pot;否则,将当前元素移动到第j个位置并执行步骤(3)。
(3)重复执行步骤(1)和(2),直到出现i≥j,将轴元素pot移动到a[i]中。
此时,整个元素序列被划分为两个部分,第i个位置前的元素都小于a[i],第i个位置后的无素都大于等于a[i]。
至此,就完成了一次快速排序。按照以上方法,将每个部分都进行类似的划分操作,直到每个部分都只有一个元素为止,这样整个元素序列就构成了一个有序的序列。
3、C语言实现快速排序
#include <stdio.h>
void DisArray(int a[], int n);
void DisArray2(int a[], int n, int pot, int count);
void Qsort(int a[], int n, int low, int high);
void QuickSort(int a[], int n);
int Partition(int a[], int low, int high);
void main()
{
int a[]= {23,12,54,2,65,90,67,99,32,15};
int n= sizeof(a)/sizeof(a[0]);
printf("快速排序前:");
DisArray(a, n);
QuickSort(a, n);
printf("快速排序结果:");
DisArray(a, n);
}
void Qsort(int a[], int n, int low, int high)
{
int pot;
static count= 1;
if(low<high)
{
pot= Partition(a, low, high);
DisArray2(a, n, pot, count);
count++;
Qsort(a, n, low, pot-1);
Qsort(a, n, pot+1, high);
}
}
void QuickSort(int a[], int n)
{
Qsort(a, n, 0, n-1);
}
int Partition(int a[], int low, int high)
{
int t, pot;
pot= a[low];
t= a[low];
while(low<high)
{
while(low<high && a[high]>=pot)
high--;
if(low<high)
{
a[low]= a[high];
low++;
}
while(low<high && a[low]<=pot)
low++;
if(low<high)
{
a[high]= a[low];
high--;
}
a[low]= t;
}
return low;
}
void DisArray2(int a[], int n, int pot, int count)
{
int i;
printf("第%d次划分的结果:[",count);
for(i=0; i<pot; i++)
printf("%4d",a[i]);
printf("]");
printf("%3d",a[pot]);
printf("[");
for(i=pot+1; i<n; i++)
printf("%4d",a[i]);
printf("]\n");
}
void DisArray(int a[], int n)
{
int i;
for(i=0; i<n; i++)
printf("%-4d", a[i]);
printf("\n");
}
4、快速排序的用途
快速排序是对冒泡排序的改进,它的实现比较复杂,它主要用在数量比较大的排序中,它的时间效率要远高于冒泡排序。
5、快速排序复杂度
参考文献:《The Function and Algorithm of Program Language C/C++》
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)