/* * quick_sort.cpp * * Created on: 2016-3-21 * Author: Lv_Lang */ //快速排序 #include <iostream> using namespace std; int a[100];//全局定义数组,方便函数使用 void swap(int i,int j) { int temp = a[i]; a[i] = a[j]; a[j] = temp; } /*快速排序解释: 核心思想是找一个基准元素(一般选取首位元素), 然后遍历元素,比基准小的放左边,比基准大的放右边。 但其实按这个思想来写代码其实比较难写的, 所以说的更通俗一点就是:先把首位的拿出来被比较, 用一个哨兵j从数组最右边开始扫描,如果有小于基准的,先停下来; 然后哨兵i开始从数组最左边开始扫描,如果有大于基准的,也停下来; 此时左边有个比基准大的,右边有个比基准小的,交换二者就行了。 最后当两个哨兵相遇时,证明左右都扫了一遍了, 然后把他们相遇的那个点的元素跟基准元素互换位置,这就得到了一个初步排序的序列。 然后把刚才得到的序列切成两半(不含基准元素), 基准前面的元素是一半,基准后面的元素是另一半,对这两个子序列重复刚才的那个步骤。 递归一下,就能最终得到排好序的序列了。*/ void quick_sort(int left,int right) { if(left >= right)//递归临界条件 return; int i,j,temp; i = left; j = right; temp = a[left]; while(i < j) { while(a[j] >= temp && i < j) j--; while(a[i] <= temp && i < j) i++; swap(i,j); } swap(left,i); quick_sort(left,i-1); quick_sort(i+1,right); } int main() { int n; cin>>n; for(int i=0;i < n;i++) cin>>a[i]; quick_sort(0,5); for(int i=0;i<5;i++) cout<<a[i]<<" "; cout<<a[5]<<endl; return 0; }
另外,这篇博客写的挺好的,形象易懂: