本文详细叙述和实现了快速排序算法,冒泡排序 选择排序 插入排序比较简单,原理在这里不再详述,直接用代码进行了实现。
快速排序法(quicksort)是目前所公认最快的排序方法之一(视解题的对象而定),虽然快速排序法在最差状况下可以达O(n2),但是在多数的情况下,快速排序法的效率表现是相当不错的。快速排序法的基本精神是在数列中找出适当的轴心,然后将数列一分为二,分别对左边与右边数列进行排序,而影响快速排序法效率的正是轴心的选择。
这边所介绍的第一个快速排序法版本,是在多数的教科书上所提及的版本,因为它最容易理解,最符合轴心分割与左右进行排序的概念,适合对初学者进行讲解。
解法这边所介绍的快速演算如下:将最左边的数设定为轴,并记录其值为s
廻圈处理:
令索引i 从数列左方往右方找,直到找到大于s 的数
令索引j 从数列左右方往左方找,直到找到小于s 的数
如果i>=j,则离开回圈
如果i<j,则交换索引i与j两处的值
将左侧的轴与j 进行交换
对轴左边进行递回
对轴右边进行递回
透过以下演算法,则轴左边的值都会小于s,轴右边的值都会大于s,如此再对轴左右两边进行
递回,就可以对完成排序的目的,例如下面的实例,*表示要交换的数,[]表示轴:
[41] 24 76* 11 45 64 21 69 19 36*
[41] 24 36 11 45* 64 21 69 19* 76
[41] 24 36 11 19 64* 21* 69 45 76
[41] 24 36 11 19 21 64 69 45 76
21 24 36 11 19 [41] 64 69 45 76
算法实现c/c++版:
/*快速排序法
sort 函数说明,添加者 Steve;
left:数组a的最小下标;
right:数组a的最大下标;
a[]:数组;
N:数组长度
*/
void sort(int left,int right ,int a[],int N)
{
if (left<right)
{
int al=left;
int ar=right+1;
int aleft=a[left];
while(1)
{
while((al+1<N)&&(aleft>a[++al]));
while((ar-1>-1)&&(aleft<a[--ar]));
if (al>=ar)
{
break;
}
int temp=a[al];
a[al]=a[ar];
a[ar]=temp;
}
a[left]=a[ar];
a[ar]=aleft;
sort(left,ar-1,a,N);
sort(ar+1,right,a,N);
}
}
//冒泡排序法
void bufferSort(int a[],int N)
{
for (int i=0;i<N-1;i++)
for(int j=0;j<N-i-1;j++)
{
if (a[j]>a[j+1])
{
int temp=a[j];
a[j]=a[j+1];
a[j+1]=temp;
}
}
}
//选择排序法
void SelectSort(int a[],int N)
{
for (int i=0;i<N-1;i++)
{
int Min=a[i];
int index=i;
for(int j=i+1;j<N;j++)
if (Min>a[j])
{
Min=a[j];
index=j;
}
a[index]=a[i];
a[i]=Min;
}
}
//插入排序法
void inserSort(int a[],int N)
{
for ( int i=1;i<N;i++ )
{
int temp=a[i];
int j=i-1;
while(temp<a[j])
{
a[j+1]=a[j];
j--;
if(j<0)
break;
}
a[j+1]=temp;
}
}
int _tmain(int argc, _TCHAR* argv[])
{
int a[]={-2,3,4,-9};
cout<<" 排序前"<<endl;
for (int i=0;i<4;i++)
{
cout<<a[i]<<" ";
}
cout<<endl<<"排序后"<<endl;
//sort(0,3,a,4);//快速排序
// bufferSort(a,4);//冒泡排序
// SelectSort(a,4);//选择排序
inserSort(a,4);
for (int i=0;i<4;i++)
{
cout<<a[i]<<" ";
}
return 0;
}
如果有更好的排序思想,欢迎交流