 |
大学毕业了，之前说把数据结构书里的算法都写一遍，最后也不了了之。。
从学会用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);
}
}
作者：sunrise
| |
