c/c++ 算法之快速排序法 冒泡排序法,选择排序法,插入排序法
本文详细叙述和实现了快速排序算法,冒泡排序 选择排序 插入排序比较简单,原理在这里不再详述,直接用代码进行了实现。
快速排序法(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;
}
如果有更好的排序思想,欢迎交流
相关文章
- C++的黑科技(深入探索C++对象模型)
- C/C++中内嵌汇编(Visual Studio 2019)
- 【C++】STL中sort算法使用了什么排序算法?
- 91 C++ - 常用算数生成算法
- 88 C++ - 常用查找算法
- C++程序设计课程同步项目——循环结构程序设计项目任务二
- c++ bitset二进制位有序集
- C++ 排列最优解算法思想
- 《C++面向对象高效编程(第2版)》——3.4 赋值操作符
- 《C++面向对象高效编程(第2版)》——第4章
- 基于QT(C++)+SQL Server 2008 实现相机租赁系统【100010742】
- 基于QT(C++)实现查找算法图形化(数据结构课程设计)【100010640】
- 基于C++实现⾃然连接操作算法【100010157】
- 【C++】STL常用算法
- Visual Studio 不同版本对C++11的支持进度
- C/C++_排序算法
- C++算法学习资料整理
- 187、【栈与队列】leetcode ——42. 接雨水(C++版本)
- 138、【贪心算法】leetcode ——452. 用最少数量的箭引爆气球(贪心区间重叠问题)(C++版本)
- 137、【贪心算法】leetcode ——406. 根据身高重建队列(多维度贪心)(C++版本)
- 118、【回溯算法】leetcode ——40. 组合总和 II:回溯法+剪枝优化(C++版本)
- 【C++快速上手】五、inline学习笔记
- 在devc++中使用to_string
- C/C++ 八大排序算法