首页 > 代码库 > 丰富自己的代码库-快速排序
丰富自己的代码库-快速排序
一些常用的代码,和demo一定要保留,对于一个程序员的成长就是不断 学习,实践,积累,除了少数的天才外, 绝大多数程序员的发展都要经历的几步,这里重点说一下积累,看到一些好的代码活着功能复杂的算法,方法,就把它收到自己的代码库里,至于自己的代码库 其实就是个本地文件夹,级别上应该跟 你自己的代码平级,建议存成.hpp文件,即头文件里包含实现,这样既保留了源码,也可以快速引用。同时这个文件夹最好添加的环境变量中,以便使用的时候直接引用
下面来说说放入代码库的第一个算法程序,快速排序,网上对于这个解释很多,其中有些是大而化之,看了根本不知所谓,学习算法还是重点了解过程,编码终究是个小事儿。
快速排序 的过程其实很简单,
用我自己理解的方式解释就是
首先 以第一个节点为准(key),以某种手段让key交换到自己排序后应该在的位置上,同时保证左边的数都小于这个key,右边的数都大于这个key(如果是从大到小排序则是左边的都大于key右边的都小于key)
如 集合 {3,1,5,2,4} 经过上述处理就回得到结果 {1,2,3,5,4} 也就是说3(key)已经抵达正确为止,同时把比三小的都放到了左边,比三大的都放到了右边
递归key的左边 子集 直至剩下一个元素为止
递归key的右边 子集 直至剩下一个元素为止
以下为代码实现
template <typename T>
void QuickSort(T a[],int low,int high)
{
if(low >= high)return;
if(!a)return;
int first = low;
int last = high;
int key = a[first];
while(last>first)
{
while(last>first&&a[last]>=key)
{
last--;
}
a[first] = a[last];
while(last>first&&a[first]<=key)
{
first++;
}
a[last] = a[first];
}
a[first]=key;
QuickSort(a,low,first-1);
QuickSort(a,first+1,high);
}
丰富自己的代码库-快速排序