大学毕业了,之前说把数据结构书里的算法都写一遍,最后也不了了之。。
从学会用STL中的sort的后,再也没有写过快排。在以后的时间中想慢慢的去把这些再写写。。一步一步慢慢的走下去。
#include<cstdio>
/*快速排序采用分治思想,设两个指针left和right,
* 一个从左往右扫描,一个从右往左扫描;
* 对于左指针,如果左指针所指的元素的值小于或者等于基准值,
* 那么指针往右移一位,如果大于基准值,则和基准值交换;
* 同理,对于右指针,如果右指针所指的元素的值大于或者等于基准值,
* 那么指针往左移一位,如果小于基准值,则和基准值交换。*/
//对序列进行分区
int Part(int array[],int left,int right)
{
int flag = array[left]; //基准
while(right > left)
{
while(right > left && array[right] >= flag)
{
right--;
}
array[left] = array[right];
while(right > left && array[left] <= flag)
{
left++;
}
array[right] = array[left];
}
array[left] = flag;
return left;
}
//运用递归进行排序
int quicksort(int array[],int low,int high)
{
int flag;
if (low < high)
{
flag = Part(array,low,high);
quicksort(array,low,flag - 1);
quicksort(array,flag + 1,high);
}
}